Showing 2025Show all
3 papers · 1 filter
cs.LG2025
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…
cs.CC2025
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…
quant-ph2025
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…