Ainesh Bakshi

collaborators

13 papers

cs.CC2026

On the Approximability of Boolean Max- $k$ -CSP

Ainesh Bakshi

Consider the problem of maximizing the number of satisfied constraints of an arbitrary boolean constraint satisfaction problem with arity $k$ . We obtain a polynomial time algorithm…

quant-ph2026

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 $k$ Kikuchi graph of any graph $G$ with $m$ edges is at most $m + k$ . This confirms four rec…

quant-ph2026

Learning quantum Hamiltonians at any temperature in polynomial time

Ainesh Bakshi, Allen Liu, Ankur Moitra +1

We study the problem of learning a local quantum Hamiltonian $H$ given copies of its Gibbs state $I ¨ = e^{- I^^{2} H} / tr (e^{- I^^{2} H})$ at a known inverse temperature $I^^{2} > 0$ . Anshu,…

quant-ph2026

Structure learning of Hamiltonians from real-time evolution

Ainesh Bakshi, Allen Liu, Ankur Moitra +1

We study the problem of Hamiltonian structure learning from real-time evolution: given the ability to apply $e^{- i H t}$ for an unknown local Hamiltonian $H = \sum_{a = 1}^…

cs.DS2026

Entrywise Low-Rank Approximation and Matrix $p \to q$ Norms via Global Correlation Rounding

Prashanti Anderson, Ainesh Bakshi, Samuel B. Hopkins

Given a matrix $A$ , the goal of the entrywise low-rank approximation problem is to find $argmin ∥ A - B ∥_{p}$ over all rank- $k$ matrices $B$ , where $∥ \cdot ∥_{p}$ is t…

quant-ph2026

Rapid mixing for high-temperature Gibbs states with arbitrary external fields

Ainesh Bakshi, Xinyu Tan

Gibbs states are a natural model of quantum matter at thermal equilibrium. We investigate the role of external fields in shaping the entanglement structure and computational comple…

On the Approximability of Boolean Max-k-CSP

Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut

Learning quantum Hamiltonians at any temperature in polynomial time

Structure learning of Hamiltonians from real-time evolution

Entrywise Low-Rank Approximation and Matrix p→q Norms via Global Correlation Rounding

Rapid mixing for high-temperature Gibbs states with arbitrary external fields

On the Approximability of Boolean Max- $k$ -CSP

Entrywise Low-Rank Approximation and Matrix $p \to q$ Norms via Global Correlation Rounding