Vasileios Nakos

Nick Fischer

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

On (1 + ϵ)-Approximate Block Sparse Recovery.

[BibT_eX]

[DOI]

Baris Can Esmer

Proceedings of the IEEE International Symposium on Information Theory, 2022

Improved Sublinear-Time Edit Distance for Preprocessed Strings.

[BibT_eX]

[DOI]

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

2021

Sparse Fourier Transform by traversing Cooley-Tukey FFT computation graphs.

[BibT_eX]

[DOI]

CoRR, 2021

Sparse nonnegative convolution is equivalent to dense nonnegative convolution.

[BibT_eX]

[DOI]

Nick Fischer

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Fast and Simple Modular Subset Sum.

[BibT_eX]

[DOI]

Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021

A Fine-Grained Perspective on Approximating Subset Sum and Partition.

[BibT_eX]

[DOI]

Panagiotis Kostopanagiotis

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

On the Approximability of Multistage Min-Sum Set Cover.

[BibT_eX]

[DOI]

Dimitris Fotakis

Georgios Piliouras

Stratis Skoulakis

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Fast n-Fold Boolean Convolution via Additive Combinatorics.

[BibT_eX]

[DOI]

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2020

Nearly Optimal Sparse Polynomial Multiplication.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2020

Sublinear-Time Algorithms for Compressive Phase Retrieval.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2020

Top-k-convolution and the quest for near-linear output-sensitive subset sum.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Deterministic Sparse Fourier Transform with an ℓ∞ Guarantee.

[BibT_eX]

[DOI]

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time.

[BibT_eX]

[DOI]

Mahdi Cheraghchi

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Stronger L2/L2 Compressed Sensing; Without Iterating.

[BibT_eX]

[DOI]

Zhao Song

CoRR, 2019

Deterministic Sparse Fourier Transform with an ell_infty Guarantee.

[BibT_eX]

[DOI]

CoRR, 2019

Stronger l2/l2 compressed sensing; without iterating.

[BibT_eX]

[DOI]

Zhao Song

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

One-Bit ExpanderSketch for One-Bit Compressed Sensing.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Symposium on Information Theory, 2019

(Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless.

[BibT_eX]

[DOI]

Zhao Song

Zhengyu Wang

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

Improved Algorithms for Adaptive Compressed Sensing.

[BibT_eX]

[DOI]

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

On Low-Risk Heavy Hitters and Sparse Recovery Schemes.

[BibT_eX]

[DOI]

David P. Woodruff

Proceedings of the Approximation, 2018

Deterministic Heavy Hitters with Sublinear Query Time.

[BibT_eX]

[DOI]

Charalampos E. Tsourakakis

Proceedings of the Approximation, 2018

2017

Predicting Positive and Negative Links with Noisy Queries: Theory & Practice.

[BibT_eX]

[DOI]

CoRR, 2017

Almost optimal phaseless compressed sensing with sublinear decoding time.

[BibT_eX]

[DOI]

Proceedings of the 2017 IEEE International Symposium on Information Theory, 2017

On Fast Decoding of High-Dimensional Signals from One-Bit Measurements.

[BibT_eX]

[DOI]

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

On Fast Decoding of Noiseless Signals from One-Bit or Phaseless Measurements.

[BibT_eX]

[DOI]