research
∙
08/29/2023
On k-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction
The goal of the trace reconstruction problem is to recover a string x∈{0...
share
research
∙
07/06/2023
Approximation Algorithms for Directed Weighted Spanners
In the pairwise weighted spanner problem, the input consists of an n-ver...
research
∙
10/07/2022
How to Make Your Approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable Approximation Algorithms of Functions with Low Sensitivity
We develop a framework for efficiently transforming certain approximatio...
research
∙
09/21/2022
Learning-Augmented Algorithms for Online Linear and Semidefinite Programming
Semidefinite programming (SDP) is a unifying framework that generalizes ...
research
∙
09/19/2022
On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors
Locally Decodable Codes (LDCs) are error-correcting codes C:Σ^n→Σ^m with...
research
∙
08/19/2022
On computing Discretized Ricci curvatures of graphs: local algorithms and (localized) fine-grained reductions
Characterizing shapes of high-dimensional objects via Ricci curvatures p...
research
∙
02/11/2022
Privately Estimating Graph Parameters in Sublinear time
We initiate a systematic study of algorithms that are both differentiall...
research
∙
12/27/2021
Differentially-Private Sublinear-Time Clustering
Clustering is an essential primitive in unsupervised machine learning. W...
research
∙
11/01/2021
Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions
Locally Decodable Codes (LDCs) are error-correcting codes for which indi...
research
∙
10/01/2021
Fixed-Parameter Algorithms for Longest Heapable Subsequence and Maximum Binary Tree
A heapable sequence is a sequence of numbers that can be arranged in a "...
research
∙
03/08/2021
Online Directed Spanners and Steiner Forests
We present online algorithms for directed spanners and Steiner forests. ...
research
∙
11/27/2020
Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Distance
Trace reconstruction considers the task of recovering an unknown string ...
research
∙
10/22/2020
Locally Decodable/Correctable Codes for Insertions and Deletions
Recent efforts in coding theory have focused on building codes for inser...
research
∙
09/17/2019
The Maximum Binary Tree Problem
We introduce and investigate the approximability of the maximum binary t...
research
∙
05/01/2018
Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows
We study the distinct elements and ℓ_p-heavy hitters problems in the sli...
research
∙
03/15/2018
Relaxed Locally Correctable Codes in Computationally Bounded Channels
Error-correcting codes that admit local decoding and correcting algorith...
research
∙
02/20/2018
Periodicity in Data Streams with Wildcards
We investigate the problem of detecting periodic trends within a string ...
research
∙
12/22/2017
Lattice-based Locality Sensitive Hashing is Optimal
Locality sensitive hashing (LSH) was introduced by Indyk and Motwani (ST...
research
∙
11/12/2017