9 papers
Optimal Sparsifiers for Minkowski Sums and Sums of Seminorms
Arpon Basu, Joshua Brakensiek, Yeyuan Chen +3
We extend the recent work of Reis and Rothvoss on sparsifying sums of norms to the more general task of sparsifying (Minkowski) sums of centrally symmetric, convex sets. A…
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…
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…
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…
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…
Many Hamiltonians Are Sparsifiable
Arpon Basu, Joshua Brakensiek, Aaron Putterman
We study the problem of Hamiltonian sparsification: given a parameter and an -qubit Hamiltonian which is the sum of -local positive semi-definite…
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…
Solving Random Planted CSPs below the Threshold
Arpon Basu, Jun-Ting Hsieh, Andrew D. Lin +1
We present a family of algorithms to solve random planted instances of any -ary Boolean constraint satisfaction problem (CSP). A randomly planted instance of a Boolean CSP is ge…
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{…