research
∙
06/24/2023
Join Size Bounds using Lp-Norms on Degree Sequences
Estimating the output size of a join query is a fundamental yet longstan...
share
research
∙
04/29/2022
Improved Sublinear-Time Edit Distance for Preprocessed Strings
We study the problem of approximating the edit distance of two strings i...
research
∙
02/16/2022
Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime
We revisit the task of computing the edit distance in sublinear time. In...
research
∙
07/28/2021
On the Approximability of Multistage Min-Sum Set Cover
We investigate the polynomial-time approximability of the multistage ver...
research
∙
07/28/2021
Top-k-Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum
In the classical Subset Sum problem we are given a set X and a target t,...
research
∙
07/15/2021
Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution
Computing the convolution A⋆ B of two length-n integer vectors A,B is a ...
research
∙
07/15/2021
Sparse Fourier Transform by traversing Cooley-Tukey FFT computation graphs
Computing the dominant Fourier coefficients of a vector is a common task...
research
∙
05/12/2021
Sparse Nonnegative Convolution Is Equivalent to Dense Nonnegative Convolution
Computing the convolution A⋆ B of two length-n vectors A,B is an ubiquit...
research
∙
05/09/2021
Fast n-fold Boolean Convolution via Additive Combinatorics
We consider the problem of computing the Boolean convolution (with wrapa...
research
∙
08/24/2020
Fast and Simple Modular Subset Sum
We revisit the Subset Sum problem over the finite cyclic group ℤ_m for s...
research
∙
06/15/2020
Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time
In the long-studied problem of combinatorial group testing, one is asked...
research
∙
09/24/2019
(Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless
In this paper, we consider the extensively studied problem of computing ...
research
∙
03/07/2019
Stronger L2/L2 Compressed Sensing; Without Iterating
We consider the extensively studied problem of ℓ_2/ℓ_2 compressed sensin...
research
∙
03/03/2019
Deterministic Sparse Fourier Transform with an ell_infty Guarantee
In this paper we revisit the deterministic version of the Sparse Fourier...
research
∙
01/27/2019
Nearly Optimal Sparse Polynomial Multiplication
In the sparse polynomial multiplication problem, one is asked to multipl...
research
∙
04/25/2018
Improved Algorithms for Adaptive Compressed Sensing
In the problem of adaptive compressed sensing, one wants to estimate an ...
research
∙
12/05/2017
Deterministic Heavy Hitters with Sublinear Query Time
This paper studies the classic problem of finding heavy hitters in the t...
research
∙
11/11/2017
One-Bit ExpanderSketch for One-Bit Compressed Sensing
Is it possible to obliviously construct a set of hyperplanes H such that...
research
∙
09/19/2017