-
Fast and Simple Modular Subset Sum
We revisit the Subset Sum problem over the finite cyclic group ℤ_m for s...
08/24/2020 ∙ by Kyriakos Axiotis, et al. ∙
0
∙
share
read it
-
Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time
In the long-studied problem of combinatorial group testing, one is asked...
06/15/2020 ∙ by Mahdi Cheraghchi, et al. ∙
0
∙
share
read it
-
(Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless
In this paper, we consider the extensively studied problem of computing ...
09/24/2019 ∙ by Vasileios Nakos, et al. ∙
0
∙
share
read it
-
Stronger L2/L2 Compressed Sensing; Without Iterating
We consider the extensively studied problem of ℓ_2/ℓ_2 compressed sensin...
03/07/2019 ∙ by Vasileios Nakos, et al. ∙
0
∙
share
read it
-
Deterministic Sparse Fourier Transform with an ell_infty Guarantee
In this paper we revisit the deterministic version of the Sparse Fourier...
03/03/2019 ∙ by Yi Li, et al. ∙
0
∙
share
read it
-
Nearly Optimal Sparse Polynomial Multiplication
In the sparse polynomial multiplication problem, one is asked to multipl...
01/27/2019 ∙ by Vasileios Nakos, et al. ∙
0
∙
share
read it
-
Improved Algorithms for Adaptive Compressed Sensing
In the problem of adaptive compressed sensing, one wants to estimate an ...
04/25/2018 ∙ by Vasileios Nakos, et al. ∙
0
∙
share
read it
-
Deterministic Heavy Hitters with Sublinear Query Time
This paper studies the classic problem of finding heavy hitters in the t...
12/05/2017 ∙ by Yi Li, et al. ∙
0
∙
share
read it
-
One-Bit ExpanderSketch for One-Bit Compressed Sensing
Is it possible to obliviously construct a set of hyperplanes H such that...
11/11/2017 ∙ by Vasileios Nakos, et al. ∙
0
∙
share
read it
-
Predicting Positive and Negative Links with Noisy Queries: Theory & Practice
Social networks and interactions in social media involve both positive a...
09/19/2017 ∙ by Charalampos E. Tsourakakis, et al. ∙
0
∙
share
read it
