9 papers
From Weak to Strong Testing in Gaussian Models
Ansh Nagda, Alexander S. Wein
We study the computational complexity of hypothesis testing in the spiked Wigner model, a prototypical model for detecting low-rank structure in a large random matrix. Below the "B…
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…
On approximability of the Permanent of PSD matrices
Farzam Ebrahimnejad, Ansh Nagda, Shayan Oveis Gharan
We study the complexity of approximating the permanent of a positive semidefinite matrix . 1. We design a new approximation algorithm for $\mathrm{per}…
Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries
Yu Chen, Sanjeev Khanna, Ansh Nagda
The problem of sparsifying a graph or a hypergraph while approximately preserving its cut structure has been extensively studied and has many applications. In a seminal work, Bencz…
Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs
Farzam Ebrahimnejad, Ansh Nagda, Shayan Oveis Gharan
We show that the ratio of the number of near perfect matchings to the number of perfect matchings in -regular strong expander (non-bipartite) graphs, with vertices, is a po…
Near-linear Size Hypergraph Cut Sparsifiers
Yu Chen, Sanjeev Khanna, Ansh Nagda
Cuts in graphs are a fundamental object of study, and play a central role in the study of graph algorithms. The problem of sparsifying a graph while approximately preserving its cu…