Reinforcement Learning for Finding Large Sets in Extremal Combinatorics

Abstract

In this talk, we present our work done in building a reinforcement learning framework for generating large sets for three problems in extremal combinatorics; i. generating large isosceles-free subsets of an integer lattice, ii. generating the same for an integer lattice embedded on a torus, and iii. generating coliniear-triple-free subsets of an integer lattice. Generating these by brute force is super-exponential in time complexity, but we can achieve state-of-the-art results through traditional a reinforcement learning framework. We explore our methodology, results, and future directions for this work.

Karan Srivastava

PhD Student, Mathematics

My research interests include machine learning, reinforcement learning, combinatorics, and algebraic geometry