
From Average Embeddings To Nearest Neighbor Search
In this note, we show that one can use average embeddings, introduced re...
read it

Streaming Complexity of SVMs
We study the space complexity of solving the biasregularized SVM proble...
read it

Edit Distance in NearLinear Time: it's a Constant Factor
We present an algorithm for approximating the edit distance between two ...
read it

Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators
We present a (1+ε)approximate parallel algorithm for computing shortest...
read it

Log Diameter Rounds Algorithms for 2Vertex and 2Edge Connectivity
Many modern parallel systems, such as MapReduce, Hadoop and Spark, can b...
read it

Two Party Distribution Testing: Communication and Security
We study the problem of discrete distribution testing in the twoparty s...
read it

On Solving Linear Systems in Sublinear Time
We study sublinear algorithms that solve linear systems locally. In the ...
read it

Batch Sparse Recovery, or How to Leverage the Average Sparsity
We introduce a batch version of sparse recovery, where the goal is to re...
read it

Approximate Nearest Neighbor Search in High Dimensions
The nearest neighbor problem is defined as follows: Given a set P of n p...
read it

Subspace Embedding and Linear Regression with Orlicz Norm
We consider a generalization of the classic linear regression problem to...
read it

Parallel Graph Connectivity in Log Diameter Rounds
We study graph connectivity problem in MPC model. On an undirected graph...
read it
Alexandr Andoni
is this you? claim profile