Shyam Narayanan

collaborators

6 papers

quant-ph2024

Improved algorithms for learning quantum Hamiltonians, via flat polynomials

Shyam Narayanan

We give an improved algorithm for learning a quantum Hamiltonian given copies of its Gibbs state, that can succeed at any temperature. Specifically, we improve over the work of Bak…

cs.DS2023

Massively Parallel Algorithms for High-Dimensional Euclidean Minimum Spanning Tree

Rajesh Jayaram, Vahab Mirrokni, Shyam Narayanan +1

We study the classic Euclidean Minimum Spanning Tree (MST) problem in the Massively Parallel Computation (MPC) model. Given a set $X \subset R^{d}$ of $n$ points, the goal i…

cs.LG2023

A faster and simpler algorithm for learning shallow networks

Sitan Chen, Shyam Narayanan

We revisit the well-studied problem of learning a linear combination of $k$ ReLU activations given labeled examples drawn from the standard $d$ -dimensional Gaussian measure. Chen e…

cs.DS2023

Learned Interpolation for Better Streaming Quantile Approximation with Worst-Case Guarantees

Nicholas Schiefer, Justin Y. Chen, Piotr Indyk +3

An $ε$ -approximate quantile sketch over a stream of $n$ inputs approximates the rank of any query point $q$ - that is, the number of input points less than $q$ - up to an…

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…

cs.DS2022

Bias Reduction for Sum Estimation

Talya Eden, Jakob Bæk Tejs Houen, Shyam Narayanan +2

In classical statistics and distribution testing, it is often assumed that elements can be sampled from some distribution $P$ , and that when an element $x$ is sampled, the probabil…