I am a fifth year ph.D. student in the Theory of Computation group of Harvard University, advised by Prof. Jelani Nelson. You can contact me at vasileiosnakos AT g DOT harvard DOT edu, if you have interest or questions in any of my papers.
My research focuses on the following set of questions.
(Sparse Fourier Transform) Under which structural assumptions and under which error guarantees can we design algorithms that outperform the Fast Fourier Transform?
(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?
How fast can we solve classical problems such as polynomial multiplication, Subset Sum, Knapsack, etc ?
(author names in alphabetical order, except where *)
(Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless
Vasileios Nakos, Zhao Song, Zhengyu Wang