209 citations · 414 across the 29 of their papers we have counts for
6 papers · 2 filters
Two Party Distribution Testing: Communication and Security
Alexandr Andoni, Tal Malkin, Negev Shekel Nosatzki
We study the problem of discrete distribution testing in the two-party setting. For example, in the standard closeness testing problem, Alice and Bob each have samples from, re…
On Solving Linear Systems in Sublinear Time
Alexandr Andoni, Robert Krauthgamer, Yosef Pogrow
We study \emph{sublinear} algorithms that solve linear systems locally. In the classical version of this problem the input is a matrix and a vector $b…
Batch Sparse Recovery, or How to Leverage the Average Sparsity
Alexandr Andoni, Lior Kamma, Robert Krauthgamer +1
We introduce a \emph{batch} version of sparse recovery, where the goal is to report a sequence of vectors that estimate unknown signals $A_1,\ld…
Approximate Nearest Neighbor Search in High Dimensions
Alexandr Andoni, Piotr Indyk, Ilya Razenshteyn
The nearest neighbor problem is defined as follows: Given a set of points in some metric space , build a data structure that, given any point , returns a point in…
Subspace Embedding and Linear Regression with Orlicz Norm
Alexandr Andoni, Chengyu Lin, Ying Sheng +2
We consider a generalization of the classic linear regression problem to the case when the loss is an Orlicz norm. An Orlicz norm is parameterized by a non-negative convex function…
Parallel Graph Connectivity in Log Diameter Rounds
Alexandr Andoni, Clifford Stein, Zhao Song +2
We study graph connectivity problem in MPC model. On an undirected graph with nodes and edges, round connectivity algorithms have been known for over 35 years.…