I am a fourth year ph.D. student in the Theory of Computation group of Harvard University, advised by Prof. Jelani Nelson. My research till now has been focused on compressed sensing and streaming algorithms. I am mostly interested in algorithmic problems with high-dimensional geometry flavor. I encourage you to contact me if you have interest in any of my papers.


  1. Improved Algorithms for Adaptive Compressed Sensing (Manuscript)
    Vasileios Nakos, Xiaofei Shi, David Woodruff, Hongyang Zhang
  2. Deterministic Heavy Hitters with Sublinear Query Time. (Manuscript)
    Yi Li, Vasileios Nakos
  3. Low-Space Sparse Recovery Tasks with Optimized Update and Decoding Time. (Manuscript)
    Vasileios Nakos, Zhao Song, Zhengyu Wang
  4. One-Bit ExpanderSketch for One-Bit Compressed Sensing. (Manuscript)
    Vasileios Nakos
  5. Predicting Positive and Negative Links with Noisy Queries: Theory & Practice. (Manuscript)
    Charalampos E. Tsourakakis, Michael Mitzenmacher, Jarosław Błasiok, Ben Lawson, Preetum Nakkiran, Vasileios Nakos
  6. Sublinear-Time Algorithms for Compressive Phase Retrieval. (Manuscript)
    Yi Li, Vasileios Nakos
  7. On Low-Risk Heavy Hitters and Sparse Recovery Schemes. (Manuscript)
    Yi Li, Vasileios Nakos, David Woodruff
  8. Almost Optimal Phaseless Compressed Sensing with Sublinear Decoding Time. (Proceedings of the 2017 IEEE International Symposium on Information Theory ISIT, Aachen, Germany, June 25-30)
    Vasileios Nakos
  9. On Fast Decoding of High-Dimensional Signals from One-Bit Measurements. (Proceedings of the 44th International Colloquium on Automata, Languages, and Programming ICALP, Warsaw, Poland, 10–14 July 2017)
    Vasileios Nakos