Bio

I am an Assistant Professor in the National and Kapodistrian University of Athens, Department of Informatics and Telecommunications. I received my Ph.D. from Harvard University and my undergraduate degree from the National Technical University of Athens, School of Electrical and Computer Engineering.

You can reach me at vasilisnak AT di DOT uoa DOT gr.

Selected Papers

1. Beating Bellman's Algorithm for Subset Sum SODA 2025
   Karl Bringmann, Nick Fischer, Vasileios Nakos
   
2. 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
   
3. Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime STOC 2022
   Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos
   
4. Deterministic and Las Vegas algorithms for Sparse Nonnegative Convolution SODA 2022
   Karl Bringmann, Nick Fischer, Vasileios Nakos
   
5. Sparse Nonnegative Convolution is Equivalent to Dense Nonnegative Convolution STOC 2021
   Karl Bringmann, Nick Fischer, Vasileios Nakos
   
6. A Fine-Grained Perspective on Approximating Subset Sum and Partition SODA 2021
   Karl Bringmann, Vasileios Nakos
   
7. Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time FOCS 2020
   Mahdi Cheraghchi, Vasileios Nakos
   
8. Top-k Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum STOC 2020
   Karl Bringmann, Vasileios Nakos
   
9. (Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless FOCS 2019
   Vasileios Nakos, Zhao Song, Zhengyu Wang
   
10. Stronger L2/L2 Compressed Sensing; Without Iterating. STOC 2019
    Vasileios Nakos, Zhao Song
    

Research Papers

(author names in alphabetical order, except where *)

1. Beating Bellman's Algorithm for Subset Sum SODA 2025
   Karl Bringmann, Nick Fischer, Vasileios Nakos
   
2. Targeted Least Cardinality Candidate Key for Relational Databases ICDT 2025
   Vasileios Nakos, Hung Ngo, Charalampos Tsourakakis
   
3. Join Size Bounds using Lp-Norms on Degree Sequences PODS 2024
   Mahmoud Abo Khamis, Vasileios Nakos, Dan Olteanu, Dan Suciu
   
4. 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
   
5. On (1+eps)-block sparse recovery ISIT 2022
   Baris Can Esmer, Vasileios Nakos
   
6. Improved Sublinear-Time Edit Distance for Preprocessed Strings ICALP 2022
   Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos
   
7. Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime STOC 2022
   Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos
   
8. Deterministic and Las Vegas algorithms for Sparse Nonnegative Convolution SODA 2022
   Karl Bringmann, Nick Fischer, Vasileios Nakos
   
9. Fast n-fold Boolean Convolution via Additive Combinatorics ICALP 2021
   Karl Bringmann, Vasileios Nakos
   
10. On the Approximability of Multistage Min-Sum Set Cover ICALP 2021
    Dimitris Fotakis, Panagiotis Kostopanagiotis, Vasileios Nakos, Georgios Piliouras, Stratis Skoulakis
    
11. Sparse Nonnegative Convolution is Equivalent to Dense Nonnegative Convolution STOC 2021
    Karl Bringmann, Nick Fischer, Vasileios Nakos
    
12. 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)
    
13. A Fine-Grained Perspective on Approximating Subset Sum and Partition SODA 2021
    Karl Bringmann, Vasileios Nakos
    
14. Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time FOCS 2020
    Mahdi Cheraghchi, Vasileios Nakos
    
15. Deterministic Sparse Fourier Transform with an L_infty Guarantee. ICALP 2020
    Yi Li, Vasileios Nakos
    
16. Nearly Optimal Sparse Polynomial Multiplication. IEEE Trans. on Info Theory 2020
    Vasileios Nakos
    
17. Sublinear-Time Algorithms for Compressive Phase Retrieval. IEEE Trans. on Info Theory 2020
    Preliminary version in ISIT 2018
    Yi Li, Vasileios Nakos
    
18. 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
    
19. Top-k Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum STOC 2020
    Karl Bringmann, Vasileios Nakos
    
20. (Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless FOCS 2019
    Vasileios Nakos, Zhao Song, Zhengyu Wang
    
21. Stronger L2/L2 Compressed Sensing; Without Iterating. STOC 2019
    Vasileios Nakos, Zhao Song
    
22. One-Bit ExpanderSketch for One-Bit Compressed Sensing. ISIT 2019
    Vasileios Nakos
    
23. Improved Algorithms for Adaptive Compressed Sensing ICALP 2018
    Vasileios Nakos, Xiaofei Shi, David Woodruff, Hongyang Zhang
    
24. On Low-Risk Heavy Hitters and Sparse Recovery Schemes. RANDOM/APPROX 2018
    Yi Li, Vasileios Nakos, David Woodruff
    
25. Deterministic Heavy Hitters with Sublinear Query Time. RANDOM/APPROX 2018
    Yi Li, Vasileios Nakos
    
26. Almost Optimal Phaseless Compressed Sensing with Sublinear Decoding Time.ISIT 2017
    Vasileios Nakos
    
27. On Fast Decoding of High-Dimensional Signals from One-Bit Measurements. ICALP 2017
    Vasileios Nakos