Bio

I hold a postdoc position at Saarland University and Max Planck Institute for Informatics, generously funded by Karl Bringmann's ERC starting grant . Before that, I obtained by Ph.D. from Harvard University, advised by Prof. Jelani Nelson. Even before that, I completed my undergraduate studies at the National Technical University of Athens. You can contact me at vnakos AT mpi-inf DOT mpg DOT de if you have interest or questions in any of my papers.

I primarily work on modern aspects of algorithm design, mostly under sparsity assumptions, for example compressed sesing/sparse recovery. The need for such algorithms arises across all science and engineering, for example in Machine Learning, Data Science and Signal Processing to name a few. We are organizing ADFOCS 2021 in MPII on convex optimization, see the website.

For general audience: In the theory of Algorithms and Computer Science, the most important venues are conferences and not journals. The most widely recognized and prestigious conferences in the field are FOCS (Foundations of Computer Science) and STOC (Symposium on the Theory of Computation), while the next most important conference is SODA.


Research Papers

(author names in alphabetical order, except where *)
  1. Sparse Fourier Transform by traversing Cooley-Tukey FFT computation graphs
    Karl Bringmann, Michael Kapralov, Michael Makarov, Vasileios Nakos, Amir Yagudin, Amir Zandieh
  2. Deterministic and Las Vegas algorithms for Sparse Nonnegative Convolution
    Karl Bringmann, Nick Fischer, Vasileios Nakos
  3. Fast n-fold Boolean Convolution via Additive Combinatorics ICALP 2021
    Karl Bringmann, Vasileios Nakos
  4. On the Approximability of Multistage Min-Sum Set Cover ICALP 2021
    Dimitris Fotakis, Panagiotis Kostopanagiotis, Vasileios Nakos, Georgios Piliouras, Stratis Skoulakis
  5. Sparse Nonnegative Convolution is Equivalent to Dense Nonnegative Convolution STOC 2021
    Karl Bringmann, Nick Fischer, Vasileios Nakos
  6. 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)
  7. A Fine-Grained Perspective on Approximating Subset Sum and Partition SODA 2021
    Karl Bringmann, Vasileios Nakos
  8. Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time FOCS 2020
    Mahdi Cheraghchi, Vasileios Nakos
  9. Deterministic Sparse Fourier Transform with an L_infty Guarantee. ICALP 2020
    Yi Li, Vasileios Nakos
  10. Nearly Optimal Sparse Polynomial Multiplication. IEEE Trans. on Info Theory 2020
    Vasileios Nakos
  11. Sublinear-Time Algorithms for Compressive Phase Retrieval. IEEE Trans. on Info Theory 2020
    Preliminary version in ISIT 2018
    Yi Li, Vasileios Nakos
  12. 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
  13. Top-k Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum STOC 2020
    Karl Bringmann, Vasileios Nakos
  14. (Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless FOCS 2019
    Vasileios Nakos, Zhao Song, Zhengyu Wang
  15. Stronger L2/L2 Compressed Sensing; Without Iterating. STOC 2019
    Vasileios Nakos, Zhao Song
  16. One-Bit ExpanderSketch for One-Bit Compressed Sensing. ISIT 2019
    Vasileios Nakos
  17. Improved Algorithms for Adaptive Compressed Sensing ICALP 2018
    Vasileios Nakos, Xiaofei Shi, David Woodruff, Hongyang Zhang
  18. On Low-Risk Heavy Hitters and Sparse Recovery Schemes. RANDOM/APPROX 2018
    Yi Li, Vasileios Nakos, David Woodruff
  19. Deterministic Heavy Hitters with Sublinear Query Time. RANDOM/APPROX 2018
    Yi Li, Vasileios Nakos
  20. Almost Optimal Phaseless Compressed Sensing with Sublinear Decoding Time.ISIT 2017
    Vasileios Nakos
  21. On Fast Decoding of High-Dimensional Signals from One-Bit Measurements. ICALP 2017
    Vasileios Nakos