research
∙
07/14/2023
Fast Algorithms for a New Relaxation of Optimal Transport
We introduce a new class of objectives for optimal transport computation...
share
research
∙
06/30/2023
Breaking the Metric Voting Distortion Barrier
We consider the following well studied problem of metric distortion in s...
research
∙
05/20/2023
Distortion in metric matching with ordinal preferences
Suppose that we have n agents and n items which lie in a shared metric s...
research
∙
11/07/2022
A Characterization of List Learnability
A classical result in learning theory shows the equivalence of PAC learn...
research
∙
10/13/2022
On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood
We provide an efficient unified plug-in approach for estimating symmetri...
research
∙
06/10/2022
On the Complexity of Sampling Redistricting Plans
A crucial task in the political redistricting problem is to sample redis...
research
∙
05/07/2022
Almost 3-Approximate Correlation Clustering in Constant Rounds
We study parallel algorithms for correlation clustering. Each pair among...
research
∙
05/01/2022
The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction
We study the effect of Johnson-Lindenstrauss transforms in various Eucli...
research
∙
04/26/2022
Polylogarithmic Sketches for Clustering
Given n points in ℓ_p^d, we consider the problem of partitioning points ...
research
∙
11/05/2021
Metric Distortion Bounds for Randomized Social Choice
Consider the following social choice problem. Suppose we have a set of n...
research
∙
06/29/2021
Near-Optimal Explainable k-Means for All Dimensions
Many clustering algorithms are guided by certain cost functions such as ...
research
∙
06/10/2021
Multiway Online Correlated Selection
We give a 0.5368-competitive algorithm for edge-weighted online bipartit...
research
∙
03/02/2021
Approximation Algorithms for Orthogonal Non-negative Matrix Factorization
In the non-negative matrix factorization (NMF) problem, the input is an ...
research
∙
11/30/2020
A Model for Ant Trail Formation and its Convergence Properties
We introduce a model for ant trail formation, building upon previous wor...
research
∙
11/13/2020
Kernel Density Estimation through Density Constrained Near Neighbor Search
In this paper we revisit the kernel density estimation problem: given a ...
research
∙
11/05/2020
Instance Based Approximations to Profile Maximum Likelihood
In this paper we provide a new efficient algorithm for approximately com...
research
∙
10/27/2020
Improved Algorithms for Edge Colouring in the W-Streaming Model
In the W-streaming model, an algorithm is given O(n polylog n) space and...
research
∙
09/02/2020
Nearest Neighbor Search for Hyperbolic Embeddings
Embedding into hyperbolic space is emerging as an effective representati...
research
∙
07/28/2020
A Simple Sublinear Algorithm for Gap Edit Distance
We study the problem of estimating the edit distance between two n-chara...
research
∙
04/06/2020
The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications for Profile Maximum Likelihood
In this paper we consider the problem of computing the likelihood of the...
research
∙
03/02/2020
A General Framework for Symmetric Property Estimation
In this paper we provide a general framework for estimating symmetric pr...
research
∙
02/08/2020
Storyboard: Optimizing Precomputed Summaries for Aggregation
An emerging class of data systems partition their data and precompute ap...
research
∙
01/05/2020
New lower bounds for Massively Parallel Computation from query complexity
Roughgarden, Vassilvitskii, and Wang (JACM 18) recently introduced a nov...
research
∙
10/01/2019
Retrieving Top Weighted Triangles in Graphs
Pattern counting in graphs is a fundamental primitive for many network a...
research
∙
05/21/2019
Efficient Profile Maximum Likelihood for Universal Symmetric Property Estimation
Estimating symmetric properties of a distribution, e.g. support size, co...
research
∙
03/08/2019
The One-Way Communication Complexity of Dynamic Time Warping Distance
We resolve the randomized one-way communication complexity of Dynamic Ti...
research
∙
12/27/2018
Hierarchical Clustering for Euclidean Data
Recent works on Hierarchical Clustering (HC), a well-studied problem in ...
research
∙
10/31/2018
Recovery Guarantees for Quadratic Tensors with Limited Observations
We consider the tensor completion problem of predicting the missing entr...
research
∙
10/01/2018
A sampling framework for counting temporal motifs
Pattern counting in graphs is fundamental to network science tasks, and ...
research
∙
09/20/2018
Local Density Estimation in High Dimensions
An important question that arises in the study of high dimensional vecto...
research
∙
08/30/2018
Hashing-Based-Estimators for Kernel Density in High Dimensions
Given a set of points P⊂R^d and a kernel k, the Kernel Density Estimate ...
research
∙
08/07/2018
Hierarchical Clustering better than Average-Linkage
Hierarchical Clustering (HC) is a widely studied problem in exploratory ...
research
∙
07/19/2018
Multi-Resolution Hashing for Fast Pairwise Summations
A basic computational primitive in the analysis of massive datasets is s...
research
∙
05/24/2018
Hierarchical Clustering with Structural Constraints
Hierarchical clustering is a popular unsupervised data analysis method. ...
research
∙
04/26/2018
On Estimating Edit Distance: Alignment, Dimension Reduction, and Embeddings
Edit distance is a fundamental measure of distance between strings and h...
research
∙
02/26/2018
Multi-Commodity Flow with In-Network Processing
Modern networks run "middleboxes" that offer services ranging from netwo...
research
∙
02/18/2018
On Finding Dense Common Subgraphs
We study the recently introduced problem of finding dense common subgrap...
research
∙
11/18/2017
Fully Dynamic Almost-Maximal Matching: Breaking the Polynomial Barrier for Worst-Case Time Bounds
Despite significant research efforts, the state-of-the-art algorithm for...
research
∙
03/15/2017
Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers
We introduce a criterion, resilience, which allows properties of a datas...
research
∙
02/18/2017
A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics
We study the Stochastic Gradient Langevin Dynamics (SGLD) algorithm for ...
research
∙
11/07/2016
Learning from Untrusted Data
The vast majority of theoretical results in machine learning and statist...
research
∙
11/14/2013
