I hold a postdoc position at 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. You can contact me at vnakos AT mpi-inf DOT mpg DOT de if you have interest or questions in any of my papers.

Research Interests

My research focuses on the following set of questions.
  1. (Sparse Fourier Transform) Under which structural assumptions and under which error guarantees can we design algorithms that outperform the Fast Fourier Transform?
  2. (Compressed Sensing/ Linear Sketching) Rapidly compress a very long vector, such that a fine approximation of it can be recovered very fast given its compressed form. In each possible scenario, how many bits do you need to compress, and how fast the compression, decompression algorithms can be?
  3. (Additive Combinatorics-Inspired Algorithms) For problems like Subset Sum, Knapsack, (any sort of) convolution, how can we exploit the underlying additive structure to design faster algorithms?

Research Papers

(author names in alphabetical order, except where *)
  1. Top-k Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum (Under Submission)
    Karl Bringmann, Vasileios Nakos
  2. Fast n-fold Boolean Convolution via Additive Combinatorics (Under Submission)
    Karl Bringmann, Vasileios Nakos
  3. Deterministic Sparse Fourier Transform with an L_infty Guarantee.
    Yi Li, Vasileios Nakos
  4. Combinatorial Group Testing Schemes with Nearly Optimal Decoding Time.
    Vasileios Nakos
  5. Robust Sparse Recovery via Huber and Tukey loss
    Vasileios Nakos, Zhao Song, Zhengyu Wang
  6. Nearly Optimal Sparse Polynomial Multiplication.
    Vasileios Nakos
  7. (Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless FOCS 2019
    Vasileios Nakos, Zhao Song, Zhengyu Wang
  8. One-Bit ExpanderSketch for One-Bit Compressed Sensing. ISIT 2019
    Vasileios Nakos
  9. Stronger L2/L2 Compressed Sensing; Without Iterating. STOC 2019
    Vasileios Nakos, Zhao Song
  10. Predicting Positive and Negative Links with Noisy Queries: Theory & Practice.(*) Allerton 2018
    Charalampos E. Tsourakakis, Michael Mitzenmacher, Kasper Green Larsen, Jarosław Błasiok, Ben Lawson, Preetum Nakkiran, Vasileios Nakos
  11. Improved Algorithms for Adaptive Compressed Sensing ICALP 2018
    Vasileios Nakos, Xiaofei Shi, David Woodruff, Hongyang Zhang
  12. On Low-Risk Heavy Hitters and Sparse Recovery Schemes. RANDOM/APPROX 2018
    Yi Li, Vasileios Nakos, David Woodruff
  13. Deterministic Heavy Hitters with Sublinear Query Time. RANDOM/APPROX 2018
    Yi Li, Vasileios Nakos
  14. Sublinear-Time Algorithms for Compressive Phase Retrieval. ISIT 2018
    Yi Li, Vasileios Nakos
  15. Almost Optimal Phaseless Compressed Sensing with Sublinear Decoding Time.ISIT 2017
    Vasileios Nakos
  16. On Fast Decoding of High-Dimensional Signals from One-Bit Measurements. ICALP 2017
    Vasileios Nakos