research
∙
07/12/2021
Noisy searching: simple, fast and correct
This work revisits the multiplicative weights update technique (MWU) whi...
share
research
∙
06/04/2021
A time and space optimal stable population protocol solving exact majority
We study population protocols, a model of distributed computing appropri...
research
∙
05/13/2021
The Dynamic k-Mismatch Problem
The text-to-pattern Hamming distances problem asks to compute the Hammin...
research
∙
11/14/2020
Time and Space Optimal Exact Majority Population Protocols
In this paper we study population protocols governed by the random sched...
research
∙
08/17/2020
Cardinality estimation using Gumbel distribution
Cardinality estimation is the task of approximating the number of distin...
research
∙
07/17/2020
All-Pairs LCA in DAGs: Breaking through the O(n^2.5) barrier
Let G=(V,E) be an n-vertex directed acyclic graph (DAG). A lowest common...
research
∙
06/24/2020
Improved Circular k-Mismatch Sketches
The shift distance 𝗌𝗁(S_1,S_2) between two strings S_1 and S_2 of the sa...
research
∙
04/30/2020
An Efficient Noisy Binary Search in Graphs via Median Approximation
Consider a generalization of the classical binary search problem in line...
research
∙
03/13/2020
Robust Comparison in Population Protocols
There has recently been a surge of interest in the computational and com...
research
∙
02/09/2020
Approximating Text-to-Pattern Distance via Dimensionality Reduction
Text-to-pattern distance is a fundamental problem in string matching, wh...
research
∙
07/09/2019
L_p Pattern Matching in a Stream
We consider the problem of computing distance between a pattern of lengt...
research
∙
05/03/2019
RLE edit distance in near optimal time
We show that the edit distance between two run-length encoded strings of...
research
∙
02/19/2019
Hardness of exact distance queries in sparse graphs through hub labeling
A distance labeling scheme is an assignment of bit-labels to the vertice...
research
∙
10/03/2018
Approximating Approximate Pattern Matching
Given a text T of length n and a pattern P of length m, the approximate ...
research
∙
07/16/2018
Faster Algorithms for All-Pairs Bounded Min-Cuts
Given a directed graph, the vertex connectivity from u to v is the maxim...
research
∙
04/05/2018
A Framework for Searching in Graphs in the Presence of Errors
We consider two types of searching models, where the goal is to design a...
research
∙
02/19/2018
Population Protocols Are Fast
A population protocol describes a set of state change rules for a popula...
research
∙
02/19/2018
Population Protocols Made Easy
We put forward a simple high-level framework for describing a population...
research
∙
02/19/2018
Almost logarithmic-time space optimal leader election in population protocols
The model of population protocols refers to a large collection of simple...
research
∙
01/28/2018
Faster Approximate(d) Text-to-Pattern L1 Distance
The problem of finding distance between pattern of length m and text of ...
research
∙
11/10/2017
Hamming distance completeness and sparse matrix multiplication
We investigate relations between (+,) vector products for binary integer...
research
∙
09/28/2017