5 citations · 19 across the 20 of their papers we have counts for
29 papers
Fast Quantized JohnsonLindenstrauss Transforms
Angelos Korakitis, Vasileios Nakos
Quantization has emerged as one of the primary techniques for reducing the memory footprint of large language models during inference. A prominent example is Quantized JohnsonLi…
Robustifying Sparse Matrix Multiplication
Karl Bringmann, Nick Fischer, Vasileios Nakos
In the seminal sparse matrix multiplication problem the goal is to compute the product of two matrices when the matrices are sparse, i.e., when the number of nonzeros…
Listing Even Cycles Faster than the Submodular-Width Barrier
Vasileios Nakos, Hung Q. Ngo, Andreas Panayi
A classic result of Alon, Yuster, and Zwick (AYZ, Algorithmica 1997) shows that all -cycles in an -edge graph can be listed in time, where is the…
Sparse Recovery via Weighted Hypergraph Peeling
Nick Fischer, Vasileios Nakos
We demonstrate that the best -sparse approximation of a length- vector can be recovered within a -factor approximation in time using a non-adaptive l…
Information Theory Strikes Back: New Development in the Theory of Cardinality Estimation
Mahmoud Abo Khamis, Vasileios Nakos, Dan Olteanu +1
Estimating the cardinality of the output of a query is a fundamental problem in database query processing. In this article, we overview a recently published contribution that casts…
Beating Bellman's Algorithm for Subset Sum
Karl Bringmann, Nick Fischer, Vasileios Nakos
Bellman's algorithm for Subset Sum is one of the earliest and simplest examples of dynamic programming, dating back to 1957. For a given set of integers and a target , i…
Targeted Least Cardinality Candidate Key for Relational Databases
Vasileios Nakos, Hung Q. Ngo, Charalampos E. Tsourakakis
Functional dependencies (FDs) are a central theme in databases, playing a major role in the design of database schemas and the optimization of queries. In this work, we introduce t…
Improved Sublinear-Time Edit Distance for Preprocessed Strings
Karl Bringmann, Alejandro Cassis, Nick Fischer +1
We study the problem of approximating the edit distance of two strings in sublinear time, in a setting where one or both string(s) are preprocessed, as initiated by Goldenberg, Rub…
Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime
Karl Bringmann, Alejandro Cassis, Nick Fischer +1
We revisit the task of computing the edit distance in sublinear time. In the -gap edit distance problem the task is to distinguish whether the edit distance of two strings i…
On the Approximability of Multistage Min-Sum Set Cover
Dimitris Fotakis, Panagiotis Kostopanagiotis, Vasileios Nakos +2
We investigate the polynomial-time approximability of the multistage version of Min-Sum Set Cover (), a natural and intriguing generalization of the classical List U…
Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution
Karl Bringmann, Nick Fischer, Vasileios Nakos
Computing the convolution of two length- integer vectors is a core problem in several disciplines. It frequently comes up in algorithms for Knapsack, -SUM, A…
Top-k-Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum
Karl Bringmann, Vasileios Nakos
In the classical Subset Sum problem we are given a set and a target , and the task is to decide whether there exists a subset of which sums to . A recent line of rese…
Traversing the FFT Computation Tree for Dimension-Independent Sparse Fourier Transforms
Karl Bringmann, Michael Kapralov, Mikhail Makarov +3
We consider the well-studied Sparse Fourier transform problem, where one aims to quickly recover an approximately Fourier -sparse vector from…
Sparse Nonnegative Convolution Is Equivalent to Dense Nonnegative Convolution
Karl Bringmann, Nick Fischer, Vasileios Nakos
Computing the convolution of two length- vectors is an ubiquitous computational primitive. Applications range from string problems to Knapsack-type problems, an…
Fast -fold Boolean Convolution via Additive Combinatorics
Karl Bringmann, Vasileios Nakos
We consider the problem of computing the Boolean convolution (with wraparound) of ~vectors of dimension , or, equivalently, the problem of computing the sumset $A_1+A_2+\ldot…
Fast and Simple Modular Subset Sum
Kyriakos Axiotis, Arturs Backurs, Karl Bringmann +4
We revisit the Subset Sum problem over the finite cyclic group for some given integer . A series of recent works has provided near-optimal algorithms for this pro…
Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time
Mahdi Cheraghchi, Vasileios Nakos
In the long-studied problem of combinatorial group testing, one is asked to detect a set of defective items out of a population of size , using disjunctive measure…
(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…
Improved Algorithms for Adaptive Compressed Sensing
Vasileios Nakos, Xiaofei Shi, David P. Woodruff +1
In the problem of adaptive compressed sensing, one wants to estimate an approximately -sparse vector from linear measurements …
Deterministic Heavy Hitters with Sublinear Query Time
Yi Li, Vasileios Nakos
This paper studies the classic problem of finding heavy hitters in the turnstile streaming model. We give the first deterministic linear sketch that has $O(ε^{-2} \log n \cdot \log…
One-Bit ExpanderSketch for One-Bit Compressed Sensing
Vasileios Nakos
Is it possible to obliviously construct a set of hyperplanes H such that you can approximate a unit vector x when you are given the side on which the vector lies with respect to ev…