research
∙
05/01/2023
Streaming k-edit approximate pattern matching via string decomposition
In this paper we give an algorithm for streaming k-edit approximate patt...
share
research
∙
02/09/2023
Locally consistent decomposition of strings with applications to edit distance sketching
In this paper we provide a new locally consistent decomposition of strin...
research
∙
05/14/2021
A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm
We show that for every r ≥ 2 there exists ϵ_r > 0 such that any r-unifor...
research
∙
02/19/2021
Sorting Short Integers
We build boolean circuits of size O(nm^2) and depth O(log(n) + m log(m))...
research
∙
02/18/2021
Data Structures Lower Bounds and Popular Conjectures
In this paper, we investigate the relative power of several conjectures ...
research
∙
10/16/2020
Barrington Plays Cards: The Complexity of Card-based Protocols
In this paper we study the computational complexity of functions that ha...
research
∙
04/10/2019
Constant factor approximations to edit distance on far input pairs in nearly linear time
For any T ≥ 1, there are constants R=R(T) ≥ 1 and ζ=ζ(T)>0 and a randomi...
research
∙
03/08/2019
Stronger Lower Bounds for Online ORAM
Oblivious RAM (ORAM), introduced in the context of software protection b...
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
∙
09/26/2018
Improved bounds on Fourier entropy and Min-entropy
Given a Boolean function f:{-1,1}^n→{-1,1}, the Fourier distribution ass...
research
∙
01/16/2018
Lower bounds for Combinatorial Algorithms for Boolean Matrix Multiplication
In this paper we propose models of combinatorial algorithms for the Bool...
research
∙
12/05/2017