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
∙
06/10/2021
Small space and streaming pattern matching with k edits
In this work, we revisit the fundamental and well-studied problem of app...
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
∙
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
∙
10/02/2019
On the Hardness of Set Disjointness and Set Intersection with Bounded Universe
In the SetDisjointness problem, a collection of m sets S_1,S_2,...,S_m f...
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
∙
12/02/2018
Locally Consistent Parsing for Text Indexing in Small Space
We consider two closely related problems of text indexing in a sub-linea...
research
∙
07/10/2018
Improved Space-Time Tradeoffs for kSUM
In the kSUM problem we are given an array of numbers a_1,a_2,...,a_n and...
research
∙
05/16/2018
Improved Worst-Case Deterministic Parallel Dynamic Minimum Spanning Forest
This paper gives a new deterministic algorithm for the dynamic Minimum S...
research
∙
02/28/2016