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

Showing cs.DSShow all

17 papers · 1 filter

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.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…

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).…

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…

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…

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…

cs.DS2022

Low-Rank Approximation with $1/ ε^{1/3}$ Matrix-Vector Products

Ainesh Bakshi, Kenneth L. Clarkson, David P. Woodruff

We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten- $p$ norm. Here, given access to a matrix $A$ through matrix-vector products, an a…

cs.DS2020

Testing Positive Semi-Definiteness via Random Submatrices

Ainesh Bakshi, Nadiia Chepurko, Rajesh Jayaram

We study the problem of testing whether a matrix $A \in R^{n \times n}$ with bounded entries ( $∥ A ∥_{\infty} \leq 1$ ) is positive semi-definite (PSD), or…

cs.DS2020★ 16 cited

Outlier-Robust Clustering of Non-Spherical Mixtures

Ainesh Bakshi, Pravesh Kothari

We give the first outlier-robust efficient algorithm for clustering a mixture of $k$ statistically separated d-dimensional Gaussians (k-GMMs). Concretely, our algorithm takes input…

cs.DS2020★ 3 cited

List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Time

Ainesh Bakshi, Pravesh K. Kothari

In list-decodable subspace recovery, the input is a collection of $n$ points $α n$ (for some $α ≪ 1/2$ ) of which are drawn i.i.d. from a distribution $D$ with a isotropic…

cs.DS2019

Robust and Sample Optimal Algorithms for PSD Low-Rank Approximation

Ainesh Bakshi, Nadiia Chepurko, David P. Woodruff

Recently, Musco and Woodruff (FOCS, 2017) showed that given an $n \times n$ positive semidefinite (PSD) matrix $A$ , it is possible to compute a $(1 + ε)$ -approximate relative-error l…

cs.DS2019

Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams

Ainesh Bakshi, Nadiia Chepurko, David P. Woodruff

We study the Maximum Independent Set problem for geometric objects given in the data stream model. A set of geometric objects is said to be independent if the objects are pairwise…

cs.DS2018★ 11 cited

Learning Two Layer Rectified Neural Networks in Polynomial Time

Ainesh Bakshi, Rajesh Jayaram, David P. Woodruff

Consider the following fundamental learning problem: given input examples $x \in R^{d}$ and their vector-valued labels, as defined by an underlying generative neural network…

cs.DS2018★ 11 cited

Sublinear Time Low-Rank Approximation of Distance Matrices

Ainesh Bakshi, David P. Woodruff

Let $P = {p_{1}, p_{2}, \dots p_{n}}$ and $Q = {q_{1}, q_{2} \dots q_{m}}$ be two point sets in an arbitrary metric space. Let $A$ represent the $m \times n$ …

cs.DS2016★ 1 cited

Polynomial Time Algorithm for $2$ -Stable Clustering Instances

Ainesh Bakshi, Nadiia Chepurko

Clustering with most objective functions is NP-Hard, even to approximate well in the worst case. Recently, there has been work on exploring different notions of stability which len…