4 papers
Reinforced Generation of Combinatorial Structures: Ramsey Numbers
Ansh Nagda, Prabhakar Raghavan, Abhradeep Thakurta
We present improved lower bounds for nine classical Ramsey numbers: is increased from to , from to , …
Reinforced Generation of Combinatorial Structures: Hardness of Approximation
Ansh Nagda, Prabhakar Raghavan, Abhradeep Thakurta
Can AI based methods help us make advances in complexity theory? We provide evidence towards answering this in the affirmative, using AlphaEvolve (an LLM code mutation agent) to ob…
On optimal distinguishers for Planted Clique
Ansh Nagda, Prasad Raghavendra
In a distinguishing problem, the input is a sample drawn from one of two distributions and the algorithm is tasked with identifying the source distribution. The performance of a di…
Improved approximation algorithms for the EPR Hamiltonian
Nathan Ju, Ansh Nagda
The EPR Hamiltonian is a family of 2-local quantum Hamiltonians introduced by King (arXiv:2209.02589). We introduce a polynomial time -approximat…