research
∙
06/20/2023
Data Structures for Density Estimation
We study statistical/computational tradeoffs for the following density e...
share
research
∙
11/24/2022
Communication Complexity of Inner Product in Symmetric Normed Spaces
We introduce and study the communication complexity of computing the inn...
research
∙
12/09/2021
Estimating the Longest Increasing Subsequence in Nearly Optimal Time
Longest Increasing Subsequence (LIS) is a fundamental statistic of a seq...
research
∙
08/11/2021
Learning to Hash Robustly, with Guarantees
The indexing algorithms for the high-dimensional nearest neighbor search...
research
∙
05/12/2021
From Average Embeddings To Nearest Neighbor Search
In this note, we show that one can use average embeddings, introduced re...
research
∙
07/07/2020
Streaming Complexity of SVMs
We study the space complexity of solving the bias-regularized SVM proble...
research
∙
05/15/2020
Edit Distance in Near-Linear Time: it's a Constant Factor
We present an algorithm for approximating the edit distance between two ...
research
∙
11/05/2019
Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators
We present a (1+ε)-approximate parallel algorithm for computing shortest...
research
∙
05/02/2019
Log Diameter Rounds Algorithms for 2-Vertex and 2-Edge Connectivity
Many modern parallel systems, such as MapReduce, Hadoop and Spark, can b...
research
∙
11/09/2018
Two Party Distribution Testing: Communication and Security
We study the problem of discrete distribution testing in the two-party s...
research
∙
09/09/2018
On Solving Linear Systems in Sublinear Time
We study sublinear algorithms that solve linear systems locally. In the ...
research
∙
07/23/2018
Batch Sparse Recovery, or How to Leverage the Average Sparsity
We introduce a batch version of sparse recovery, where the goal is to re...
research
∙
06/26/2018
Approximate Nearest Neighbor Search in High Dimensions
The nearest neighbor problem is defined as follows: Given a set P of n p...
research
∙
06/17/2018
Subspace Embedding and Linear Regression with Orlicz Norm
We consider a generalization of the classic linear regression problem to...
research
∙
05/08/2018