1 citations · 4 across the 29 of their papers we have counts for
31 papers
Optimal Algorithms and Hardness for Max-Cut in Bounded Degree Graphs
Rares-Darius Buhai, Suprovat Ghoshal, Pravesh Kothari +4
We give a polynomial-time algorithm that achieves an -approximation for Max 2-LIN(2) in weighted instances where each vertex appears in at most constrain…
Strongly Refuting Semirandom Linear Systems in Subexponential Time
Pravesh K. Kothari, Andrew D. Lin, Peter Manohar
In this paper, we consider the problem of refuting -linear equations with random right-hand sides. Formally, we give a sub-exponential -time randomiz…
An Approximate Cauchy-Schwarz Inequality and Improved Bounds for Sherali-Adams Refutation of Semirandom CSPs
Pravesh K. Kothari, Andrew D. Lin
We formulate an approximate Cauchy-Schwarz inequality and show that it is satisfied by solutions to the Sherali-Adams linear programming hierarchy (interpreted as ``pseudo-distribu…
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
We study the Sachdev-Ye-Kitaev (SYK) Hamiltonian on Majorana modes with -body interactions, and prove that $\mathbb{E}\|H_{\operatorname{SYK}}\|_{\o…
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…
On Brouwer's Laplacian conjecture
Pravesh K. Kothari, Stefan Tudose
Brouwer's Laplacian conjecture states that the sum of the largest eigenvalues of a graph's Laplacian is less than or equal to the number of edges plus . We give…
Quantum Cut Sparsifiers
Arpon Basu, Joshua Brakensiek, Pravesh K. Kothari +1
In this paper, we continue a line of research initiated by Basu, Brakensiek, and Putterman [2026] studying the sparsifiability of Hamiltonians. We focus particularly on the sparsif…
Kikuchi Graphs of Random Hypergraphs are Approximately Johnson
Pravesh K. Kothari
We prove that level- Kikuchi graphs of random -uniform hypergraphs spectrally approximate the Kikuchi graph of the complete -uniform hypergraph at a sampling rate tha…
The Grothendieck Constant is Less Than
Alan Li, Rahul Saha, Anton Xue +4
We prove that the Grothendieck constant . This improves on the work of Braverman, Makarychev, Makarychev, and Naor (2011), who proved…
Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut
Ainesh Bakshi, Arpon Basu, Pravesh Kothari +1
We prove that the maximum eigenvalue of the (both signed and unsigned) Laplacian of level Kikuchi graph of any graph with edges is at most . This confirms four rec…
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…
Rigorous Implications of the Low-Degree Heuristic
Jun-Ting Hsieh, Daniel M. Kane, Pravesh K. Kothari +3
Over the past decade, the low-degree heuristic has been used to estimate the algorithmic thresholds for a wide range of average-case planted vs null distinguishing problems. Such r…
Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms
Alkis Kalavasis, Pravesh K. Kothari, Shuchen Li +1
In this work, we give a time and sample algorithm for efficiently learning the parameters of a mixture of spherical distributions in dimensions. Unlike al…
Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices
Pravesh K. Kothari, Jeff Xu
In this work, we revisit algorithms for Tensor PCA: given an order- tensor of the form where is a random symmetric Gaussian tensor with unit var…
Sparsifying Sums of Positive Semidefinite Matrices
Arpon Basu, Pravesh K. Kothari, Yang P. Liu +1
In this paper, we revisit spectral sparsification for sums of arbitrary positive semidefinite (PSD) matrices. Concretely, for any collection of PSD matrices $\mathcal{A} = \{A_1, A…
The Quasi-Polynomial Low-Degree Conjecture is False
Rares-Darius Buhai, Jun-Ting Hsieh, Aayush Jain +1
There is a growing body of work on proving hardness results for average-case estimation problems by bounding the low-degree advantage (LDA) - a quantitative estimate of the closene…
Sum-Of-Squares To Approximate Knapsack
Pravesh K. Kothari, Sherry Sarkar
These notes give a self-contained exposition of Karlin, Mathieu and Nguyen's tight estimate of the integrality gap of the sum-of-squares semidefinite program for solving the knapsa…
Improved Lower Bounds for all Odd-Query Locally Decodable Codes
Arpon Basu, Jun-Ting Hsieh, Pravesh K. Kothari +1
We prove that for every odd , any -query binary, possibly non-linear locally decodable code (-LDC) must satisfy $k \leq \tilde{…
Overcomplete Tensor Decomposition via Koszul-Young Flattenings
Pravesh K. Kothari, Ankur Moitra, Alexander S. Wein
Motivated by connections between algebraic complexity lower bounds and tensor decompositions, we investigate Koszul-Young flattenings, which are the main ingredient in recent lower…
Dimension Reduction via Sum-of-Squares and Improved Clustering Algorithms for Non-Spherical Mixtures
Prashanti Anderson, Mitali Bafna, Rares-Darius Buhai +2
We develop a new approach for clustering non-spherical (i.e., arbitrary component covariances) Gaussian mixture models via a subroutine, based on the sum-of-squares method, that fi…
Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs
Pravesh Kothari, Aaron Potechin, Jeff Xu
We prove that for every , and large enough constant , with high probability over the choice of , the \Erdos-\Renyi random graph distribution, t…