research
∙
11/03/2021
An Improved Algorithm for The k-Dyck Edit Distance Problem
A Dyck sequence is a sequence of opening and closing parentheses (of var...
share
research
∙
07/05/2021
Incremental Edge Orientation in Forests
For any forest G = (V, E) it is possible to orient the edges E so that n...
research
∙
05/22/2021
Support Optimality and Adaptive Cuckoo Filters
Filters (such as Bloom Filters) are data structures that speed up networ...
research
∙
11/25/2020
An O(log^3/2n) Parallel Time Population Protocol for Majority with O(log n) States
In population protocols, the underlying distributed network consists of ...
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/27/2020
The Streaming k-Mismatch Problem: Tradeoffs between Space and Total Time
We revisit the k-mismatch problem in the streaming model on a pattern of...
research
∙
04/17/2020
Contention Resolution Without Collision Detection
This paper focuses on the contention resolution problem on a shared comm...
research
∙
01/01/2020
Approximating Text-to-Pattern Hamming Distances
We revisit a fundamental problem in string matching: given a pattern of ...
research
∙
11/14/2019
{-1,0,1}-APSP and (min,max)-Product Problems
In the {-1,0,1}-APSP problem the goal is to compute all-pairs shortest p...
research
∙
07/25/2019
The Strong 3SUM-INDEXING Conjecture is False
In the 3SUM-Indexing problem the goal is to preprocess two lists of elem...
research
∙
05/16/2018