5 citations · 19 across the 20 of their papers we have counts for
4 papers · 1 filter
(Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless
Vasileios Nakos, Zhao Song, Zhengyu Wang
In this paper, we consider the extensively studied problem of computing a -sparse approximation to the -dimensional Fourier transform of a length signal. Our algorithm us…
Stronger L2/L2 Compressed Sensing; Without Iterating
Vasileios Nakos, Zhao Song
We consider the extensively studied problem of compressed sensing. The main contribution of our work is an improvement over [Gilbert, Li, Porat and Strauss, STOC 20…
Deterministic Sparse Fourier Transform with an ell_infty Guarantee
Yi Li, Vasileios Nakos
In this paper we revisit the deterministic version of the Sparse Fourier Transform problem, which asks to read only a few entries of and design a recovery algo…
Nearly Optimal Sparse Polynomial Multiplication
Vasileios Nakos
In the sparse polynomial multiplication problem, one is asked to multiply two sparse polynomials f and g in time that is proportional to the size of the input plus the size of the…