From the 1 of 19 linked papers with an AI index.
21 papers
Long-Horizon AI Research for Grothendieck Constant: A Case Study in Human-AI Mathematical Collaboration
Alan Li, Rahul Saha, Anton Xue +4
AI agents are increasingly used in mathematics research, but it is often unclear how to use them effectively. Towards this, we present an extensive case study of how AI was used to…
New Lower and Upper Bounds for the Grothendieck Constant
Rahul Saha, Alan Li, Anton Xue +4
We establish new bounds on the Grothendieck constant : \[ \frac{6π}{11} \le K_G \le \fracπ{2\log(1+\sqrt2)} - 10^{-4}. \] Methodologically, our lower bound approach differs fr…
Sharp Bounds on Ground State Energy of the SYK Model
Arpon Basu, Pravesh K. Kothari, Siddhant Midha
The paper derives precise asymptotic bounds for the operator norm (ground state energy) of the SYK Hamiltonian with k-body interactions, confirming earlier predictions and showing…
A Polynomial-Time Algorithm for Coloring Perfect Graphs Based on Walk Counting
Amir Ali Ahmadi, Pravesh K. Kothari, Yukai Tang
We present a polynomial-time algorithm for optimally coloring perfect graphs that is based entirely on graph-theoretic operations. At its core, the algorithm decides whether a perf…
Optimal Sparsifiers for Abelian Cayley Graphs
Arpon Basu, Pravesh K. Kothari, Raghu Meka +1
We prove that for every Cayley graph over any finite abelian group , there is a weighted Cayley graph with generators that is a spectral sparsifier f…
Improved Certificates for Independence Number in Semirandom Hypergraphs
Pravesh Kothari, Anand Louis, Rameesh Paul +1
We study the problem of efficiently certifying upper bounds on independence number of -uniform hypergraphs in semirandom models. This is a notoriously hard problem, with effi…