research
∙
08/22/2023
Tight Lower Bound on Equivalence Testing in Conditional Sampling Model
We study the equivalence testing problem where the goal is to determine ...
share
research
∙
08/21/2023
Fair Rank Aggregation
Ranking algorithms find extensive usage in diverse areas such as web sea...
research
∙
06/17/2023
Approximate Model Counting: Is SAT Oracle More Powerful than NP Oracle?
Given a Boolean formula ϕ over n variables, the problem of model countin...
research
∙
12/04/2022
Clustering Permutations: New Techniques with Streaming Applications
We study the classical metric k-median clustering problem over a set of ...
research
∙
11/22/2022
Support Size Estimation: The Power of Conditioning
We consider the problem of estimating the support size of a distribution...
research
∙
10/22/2021
Pairwise Reachability Oracles and Preservers under Failures
In this paper, we consider reachability oracles and reachability preserv...
research
∙
07/20/2021
Approximate Trace Reconstruction via Median String (in Average-Case)
We consider an approximate version of the trace reconstruction problem, ...
research
∙
11/02/2020
Approximating the Median under the Ulam Metric
We study approximation algorithms for variants of the median string prob...
research
∙
06/24/2020
Hardness of Approximation of (Multi-)LCS over Small Alphabet
The problem of finding longest common subsequence (LCS) is one of the fu...
research
∙
04/27/2020
New Extremal bounds for Reachability and Strong-Connectivity Preservers under failures
In this paper, we consider the question of computing sparse subgraphs fo...
research
∙
10/08/2018
Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time
Edit distance is a measure of similarity of two strings based on the min...
research
∙
10/08/2018
Approximate Online Pattern Matching in Sub-linear Time
We consider the approximate pattern matching problem under edit distance...
research
∙
12/05/2017
Optimal Quasi-Gray Codes: Does the Alphabet Matter?
A quasi-Gray code of dimension n and length ℓ over an alphabet Σ is a se...
research
∙
11/13/2017