Vasileios Nakos

Assistant Professor · National and Kapodistrian University of Athens

I am an Assistant Professor in the Department of Informatics and Telecommunications at the National and Kapodistrian University of Athens.

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.

I have also spent five years at RelationalAI, where I worked on database-related problems in an industrial setting.

My research focuses on algorithms and the theoretical foundations of computer science. I am particularly interested in high-dimensional data, sparse recovery, sketching, and related areas of theoretical computer science.

Email: vasilisnak AT di DOT uoa DOT gr

CV DBLP

Teaching

Courses taught at NKUA.

Selected Papers

A selection of representative papers.

  1. ℓ2/ℓ2 Sparse Recovery via Weighted Hypergraph Peeling FOCS 2025
    Nick Fischer, Vasileios Nakos
  2. Beating Bellman's Algorithm for Subset Sum SODA 2025
    Karl Bringmann, Nick Fischer, Vasileios Nakos
  3. 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
  4. Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime STOC 2022
    Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos
  5. Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution SODA 2022
    Karl Bringmann, Nick Fischer, Vasileios Nakos
  6. Sparse Nonnegative Convolution is Equivalent to Dense Nonnegative Convolution STOC 2021
    Karl Bringmann, Nick Fischer, Vasileios Nakos
  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. Top-k Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum STOC 2020
    Karl Bringmann, Vasileios Nakos
  10. (Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless FOCS 2019
    Vasileios Nakos, Zhao Song, Zhengyu Wang
  11. Stronger L2/L2 Compressed Sensing; Without Iterating STOC 2019
    Vasileios Nakos, Zhao Song

Research Papers

Author names in alphabetical order, except where marked otherwise.

2025

  1. ℓ2/ℓ2 Sparse Recovery via Weighted Hypergraph Peeling FOCS 2025
    Nick Fischer, Vasileios Nakos
  2. Robustifying Sparse Matrix Multiplication
    Karl Bringmann, Nick Fischer, Vasileios Nakos
  3. Information Theory Strikes Back: New Development in the Theory of Cardinality Estimation SIGMOD Record 2025
    Mahmoud Abo Khamis, Vasileios Nakos, Dan Olteanu, Dan Suciu
  4. Beating Bellman's Algorithm for Subset Sum SODA 2025
    Karl Bringmann, Nick Fischer, Vasileios Nakos
  5. Targeted Least Cardinality Candidate Key for Relational Databases ICDT 2025
    Vasileios Nakos, Hung Ngo, Charalampos Tsourakakis

2024

  1. Join Size Bounds using Lp-Norms on Degree Sequences PODS 2024
    Mahmoud Abo Khamis, Vasileios Nakos, Dan Olteanu, Dan Suciu

2023

  1. 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

2022

  1. On (1+ε)-Block Sparse Recovery ISIT 2022
    Baris Can Esmer, Vasileios Nakos
  2. Improved Sublinear-Time Edit Distance for Preprocessed Strings ICALP 2022
    Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos
  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

2021

  1. Fast n-Fold Boolean Convolution via Additive Combinatorics ICALP 2021
    Karl Bringmann, Vasileios Nakos
  2. On the Approximability of Multistage Min-Sum Set Cover ICALP 2021
    Dimitris Fotakis, Panagiotis Kostopanagiotis, Vasileios Nakos, Georgios Piliouras, Stratis Skoulakis
  3. Sparse Nonnegative Convolution is Equivalent to Dense Nonnegative Convolution STOC 2021
    Karl Bringmann, Nick Fischer, Vasileios Nakos
  4. Fast and Simple Modular Subset Sum SOSA@SODA 2021
    Kyriakos Axiotis, Arturs Backurs, Karl Bringmann, Ce Jin, Vasileios Nakos, Christos Tzamos, Hongxun Wu
    (Shared talk slot with Cardinal & Iacono)
  5. A Fine-Grained Perspective on Approximating Subset Sum and Partition SODA 2021
    Karl Bringmann, Vasileios Nakos

2020

  1. Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time FOCS 2020
    Mahdi Cheraghchi, Vasileios Nakos
  2. Deterministic Sparse Fourier Transform with an L∞ Guarantee ICALP 2020
    Yi Li, Vasileios Nakos
  3. Nearly Optimal Sparse Polynomial Multiplication IEEE TIT 2020
    Vasileios Nakos
  4. Sublinear-Time Algorithms for Compressive Phase Retrieval IEEE TIT 2020
    Yi Li, Vasileios Nakos (Preliminary version in ISIT 2018)
  5. Predicting Positive and Negative Links with Noisy Queries: Theory & Practice Internet Mathematics 2020
    Charalampos Tsourakakis, Michael Mitzenmacher, Kasper Green Larsen, Jarosław Błasiok, Ben Lawson, Preetum Nakkiran, Vasileios Nakos
  6. Top-k Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum STOC 2020
    Karl Bringmann, Vasileios Nakos

2019

  1. (Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless FOCS 2019
    Vasileios Nakos, Zhao Song, Zhengyu Wang
  2. Stronger L2/L2 Compressed Sensing; Without Iterating STOC 2019
    Vasileios Nakos, Zhao Song
  3. One-Bit ExpanderSketch for One-Bit Compressed Sensing ISIT 2019
    Vasileios Nakos

2018

  1. Improved Algorithms for Adaptive Compressed Sensing ICALP 2018
    Vasileios Nakos, Xiaofei Shi, David Woodruff, Hongyang Zhang
  2. On Low-Risk Heavy Hitters and Sparse Recovery Schemes RANDOM/APPROX 2018
    Yi Li, Vasileios Nakos, David Woodruff
  3. Deterministic Heavy Hitters with Sublinear Query Time RANDOM/APPROX 2018
    Yi Li, Vasileios Nakos

2017

  1. Almost Optimal Phaseless Compressed Sensing with Sublinear Decoding Time ISIT 2017
    Vasileios Nakos
  2. On Fast Decoding of High-Dimensional Signals from One-Bit Measurements ICALP 2017
    Vasileios Nakos