Ainesh Bakshi

activity

20142026

most citedOutlier-Robust Clustering of Non-Spherical Mixtures

16 citations · 62 across the 29 of their papers we have counts for

collaborators

36 papers

quant-ph2026

One-dimensional quantum Gibbs states in constant circuit depth

Saúl Pilatowsky-Cameo, Georgios Styliaris, Ainesh Bakshi +1

We prove that the Gibbs state of any spin chain can be exactly decomposed into a mixture of product states over contiguous blocks of qubits with bounded length, at any constant tem…

quant-ph2026

Optimal spectrum estimation

Ainesh Bakshi, Apoorv Vikram Singh, Xinyu Tan

We prove that the spectrum of an unknown $d$ -dimensional quantum state can be estimated to error $ε$ in total variation distance using \[ O\!\left(d^2\min\left\{ \frac{1}…

cs.DS2026

Lower Bounds for Linear Hashing via Arithmetic Kakeya

Ainesh Bakshi, Alex Conway, Hanna Komlós +2

Affine modular linear hashing is one of the simplest classical hash families. For a prime $p > u$ , the hash function is obtained by choosing $s, t$ uniformly from $Z_{p}$ and…

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…

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

Algorithmic Aspects of the Fermi--Hubbard Model

Ainesh Bakshi, Ankur Moitra, Xinyu Tan

Preparing Gibbs states on a quantum computer offers a way to computationally probe how microscopic interactions give rise to macroscopic phenomena at finite temperature. However, a…

quant-ph2026

Entanglement in quantum spin chains is strictly finite at any temperature

Ainesh Bakshi, Soonwon Choi, Saúl Pilatowsky-Cameo

Entanglement is the hallmark of quantum physics, yet its characterization in interacting many-body systems at thermal equilibrium remains one of the most important challenges in qu…

quant-ph2025

A Dobrushin condition for quantum Markov chains: Rapid mixing and conditional mutual information at high temperature

Ainesh Bakshi, Allen Liu, Ankur Moitra +1

A central challenge in quantum physics is to understand the structural properties of many-body systems, both in equilibrium and out of equilibrium. For classical systems, we have a…

cs.DS2025

Additive Approximation Schemes for Low-Dimensional Embeddings

Prashanti Anderson, Ainesh Bakshi, Samuel B. Hopkins

We consider the task of fitting low-dimensional embeddings to high-dimensional data. In particular, we study the $k$ -Euclidean Metric Violation problem ($\textsf{$k$-EMV}$), where…

cs.DS2025

Sample-Optimal Private Regression in Polynomial Time

Prashanti Anderson, Ainesh Bakshi, Mahbod Majid +1

We consider the task of privately obtaining prediction error guarantees in ordinary least-squares regression problems with Gaussian covariates (with unknown covariance structure).…

quant-ph2024★ 1 cited

Learning the closest product state

Ainesh Bakshi, John Bostanci, William Kretschmer +5

We study the problem of finding a (pure) product state with optimal fidelity to an unknown $n$ -qubit quantum state $ρ$ , given copies of $ρ$ . This is a basic instance of a fundament…

cs.DS2024

Efficient Certificates of Anti-Concentration Beyond Gaussians

Ainesh Bakshi, Pravesh Kothari, Goutham Rajendran +2

A set of high dimensional points $X = {x_{1}, x_{2}, \dots, x_{n}} \subset R^{d}$ in isotropic position is said to be $δ$ -anti concentrated if for every direction $v$ , the fraction of poin…

quant-ph2024★ 7 cited

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}^…

quant-ph2024★ 3 cited

High-Temperature Gibbs States are Unentangled and Efficiently Preparable

Ainesh Bakshi, Allen Liu, Ankur Moitra +1

We show that thermal states of local Hamiltonians are separable above a constant temperature. Specifically, for a local Hamiltonian $H$ on a graph with degree $d$ , its G…

cs.OS2024

File System Aging

Alex Conway, Ainesh Bakshi, Arghya Bhattacharya +11

File systems must allocate space for files without knowing what will be added or removed in the future. Over the life of a file system, this may cause suboptimal file placement dec…

cs.DS2023

Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams

Ainesh Bakshi, Vincent Cohen-Addad, Samuel B. Hopkins +2

Metric embeddings are a widely used method in algorithm design, where generally a ``complex'' metric is embedded into a simpler, lower-dimensional one. Historically, the theoretica…

quant-ph2023

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 $ρ = e^{- β H} / tr (e^{- β H})$ at a known inverse temperature $β > 0$ . Anshu, Arun…

cs.LG2023

Tensor Decompositions Meet Control Theory: Learning General Mixtures of Linear Dynamical Systems

Ainesh Bakshi, Allen Liu, Ankur Moitra +1

Recently Chen and Poor initiated the study of learning mixtures of linear dynamical systems. While linear dynamical systems already have wide-ranging applications in modeling time-…

cs.DS2023★ 5 cited

A Near-Linear Time Algorithm for the Chamfer Distance

Ainesh Bakshi, Piotr Indyk, Rajesh Jayaram +2

For any two point sets $A, B \subset R^{d}$ of size up to $n$ , the Chamfer distance from $A$ to $B$ is defined as $CH (A, B) = \sum_{a \in A} min_{b \in B} d_{X} (a, b)$ , whe…

cs.DS2023

Krylov Methods are (nearly) Optimal for Low-Rank Approximation

Ainesh Bakshi, Shyam Narayanan

We consider the problem of rank- $1$ low-rank approximation (LRA) in the matrix-vector product model under various Schatten norms: $$ \min_{\|u\|_2=1} \|A (I - u u^\top)\|_{\mathcal…

quant-ph2023★ 1 cited

An Improved Classical Singular Value Transformation for Quantum Machine Learning

Ainesh Bakshi, Ewin Tang

We study quantum speedups in quantum machine learning (QML) by analyzing the quantum singular value transformation (QSVT) framework. QSVT, introduced by [GSLW, STOC'19, arXiv:1806.…

math.OC2023

A New Approach to Learning Linear Dynamical Systems

Ainesh Bakshi, Allen Liu, Ankur Moitra +1

Linear dynamical systems are the foundational statistical model upon which control theory is built. Both the celebrated Kalman filter and the linear quadratic regulator require kno…

cs.LG2022

Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation

Ainesh Bakshi, Piotr Indyk, Praneeth Kacham +2

Kernel matrices, as well as weighted graphs represented by them, are ubiquitous objects in machine learning, statistics and other related fields. The main drawback of using kernel…

One-dimensional quantum Gibbs states in constant circuit depth

Optimal spectrum estimation

Lower Bounds for Linear Hashing via Arithmetic Kakeya

On the Approximability of Boolean Max-k-CSP

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

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

Algorithmic Aspects of the Fermi--Hubbard Model

Entanglement in quantum spin chains is strictly finite at any temperature

A Dobrushin condition for quantum Markov chains: Rapid mixing and conditional mutual information at high temperature

Additive Approximation Schemes for Low-Dimensional Embeddings

Sample-Optimal Private Regression in Polynomial Time

Learning the closest product state

Efficient Certificates of Anti-Concentration Beyond Gaussians

Structure learning of Hamiltonians from real-time evolution

High-Temperature Gibbs States are Unentangled and Efficiently Preparable

File System Aging

Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams

Learning quantum Hamiltonians at any temperature in polynomial time

Tensor Decompositions Meet Control Theory: Learning General Mixtures of Linear Dynamical Systems

A Near-Linear Time Algorithm for the Chamfer Distance

Krylov Methods are (nearly) Optimal for Low-Rank Approximation

An Improved Classical Singular Value Transformation for Quantum Machine Learning

A New Approach to Learning Linear Dynamical Systems

Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation

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

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