Numerical Optimization Seminar in Max Planck Institute for Informatics

For general audience: In the theory of Algorithms and Computer Science, the most important venues are conferences and

- Traversing the FFT Computation Tree for Dimension-Independent
Sparse Fourier Transforms
**SODA 2023**

Karl Bringmann, Michael Kapralov, Mikhail Makarov, Vasileios Nakos, Amir Yagudin, Amir Zandieh - Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime
**STOC 2022**

Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos - Deterministic and Las Vegas algorithms for Sparse Nonnegative Convolution
**SODA 2022**

Karl Bringmann, Nick Fischer, Vasileios Nakos - Sparse Nonnegative Convolution is Equivalent to Dense Nonnegative Convolution
**STOC 2021**

Karl Bringmann, Nick Fischer, Vasileios Nakos - A Fine-Grained Perspective on Approximating Subset Sum and Partition
**SODA 2021**

Karl Bringmann, Vasileios Nakos - Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time
**FOCS 2020**

Mahdi Cheraghchi, Vasileios Nakos - Top-k Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum
**STOC 2020**

Karl Bringmann, Vasileios Nakos - (Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless
**FOCS 2019**

Vasileios Nakos, Zhao Song, Zhengyu Wang - Stronger L2/L2 Compressed Sensing; Without Iterating.
**STOC 2019**

Vasileios Nakos, Zhao Song

- Traversing the FFT Computation Tree for Dimension-Independent
Sparse Fourier Transforms
**SODA 2023**

Karl Bringmann, Michael Kapralov, Mikhail Makarov, Vasileios Nakos, Amir Yagudin, Amir Zandieh - On (1+eps)-block sparse recovery
**ISIT 2022**

Baris Can Esmer, Vasileios Nakos - Improved Sublinear-Time Edit Distance for Preprocessed Strings
**ICALP 2022**

Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos - Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime
**STOC 2022**

Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos - Deterministic and Las Vegas algorithms for Sparse Nonnegative Convolution
**SODA 2022**

Karl Bringmann, Nick Fischer, Vasileios Nakos - Fast n-fold Boolean Convolution via Additive Combinatorics
**ICALP 2021**

Karl Bringmann, Vasileios Nakos - On the Approximability of Multistage Min-Sum Set Cover
**ICALP 2021**

Dimitris Fotakis, Panagiotis Kostopanagiotis, Vasileios Nakos, Georgios Piliouras, Stratis Skoulakis - Sparse Nonnegative Convolution is Equivalent to Dense Nonnegative Convolution
**STOC 2021**

Karl Bringmann, Nick Fischer, Vasileios Nakos - Fast and Simple Modular Subset Sum
**SOSA@SODA 2021**

Kyriakos Axiotis, Arturs Backurs, Karl Bringmann, Ce Jin, Vasileios Nakos, Christos Tzamos, Hongxun Wu

(to be shared talk slot with this paper of Cardinal and Iacono) - A Fine-Grained Perspective on Approximating Subset Sum and Partition
**SODA 2021**

Karl Bringmann, Vasileios Nakos - Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time
**FOCS 2020**

Mahdi Cheraghchi, Vasileios Nakos - Deterministic Sparse Fourier Transform with an L_infty Guarantee.
**ICALP 2020**

Yi Li, Vasileios Nakos - Nearly Optimal Sparse Polynomial Multiplication.
**IEEE Trans. on Info Theory 2020**

Vasileios Nakos - Sublinear-Time Algorithms for Compressive Phase Retrieval.
**IEEE Trans. on Info Theory 2020**

Preliminary version in**ISIT 2018**

Yi Li, Vasileios Nakos - Predicting Positive and Negative Links with Noisy Queries: Theory & Practice.(*)
**Internet Mathematics 2020**

Charalampos E. Tsourakakis, Michael Mitzenmacher, Kasper Green Larsen, Jarosław Błasiok, Ben Lawson, Preetum Nakkiran, Vasileios Nakos - Top-k Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum
**STOC 2020**

Karl Bringmann, Vasileios Nakos - (Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless
**FOCS 2019**

Vasileios Nakos, Zhao Song, Zhengyu Wang - Stronger L2/L2 Compressed Sensing; Without Iterating.
**STOC 2019**

Vasileios Nakos, Zhao Song - One-Bit ExpanderSketch for One-Bit Compressed Sensing.
**ISIT 2019**

Vasileios Nakos - Improved Algorithms for Adaptive Compressed Sensing
**ICALP 2018**

Vasileios Nakos, Xiaofei Shi, David Woodruff, Hongyang Zhang - On Low-Risk Heavy Hitters and Sparse Recovery Schemes.
**RANDOM/APPROX 2018**

Yi Li, Vasileios Nakos, David Woodruff - Deterministic Heavy Hitters with Sublinear Query Time.
**RANDOM/APPROX 2018**

Yi Li, Vasileios Nakos - Almost Optimal Phaseless Compressed Sensing with Sublinear Decoding Time.
**ISIT 2017**

Vasileios Nakos - On Fast Decoding of High-Dimensional Signals from One-Bit Measurements.
**ICALP 2017**

Vasileios Nakos

© Vasileios Nakos 2017