Vasileios Nakos

SODA Conference 2025 Conference Paper

Beating Bellman's Algorithm for Subset Sum

• Karl Bringmann
• Nick Fischer
• Vasileios Nakos

FOCS Conference 2025 Conference Paper

ℓ2/ℓ2 Sparse Recovery via Weighted Hypergraph Peeling

• Nick Fischer
• Vasileios Nakos

We demonstrate that the best k-sparse approximation of a length- $\boldsymbol{n}$ vector can be recovered within a $(1+\boldsymbol{\epsilon})$-factor approximation in $O((k / \epsilon) \log n)$ time using a non-adaptive linear sketch with $O((k / \epsilon) \log n)$ rows and $O(\log n)$ column sparsity. This improves the running of the fastest-known sketch [Nakos, Song; STOC ‘19] by a factor of $\log n$, and is optimal for a wide range of parameters. Our algorithm is simple and likely to be practical, with the analysis built on a new technique we call weighted hypergraph peeling. Our method naturally extends known hypergraph peeling processes (as in the analysis of Invertible Bloom Filters) to a setting where edges and nodes have (possibly correlated) weights.

SODA Conference 2023 Conference Paper

Traversing the FFT Computation Tree for Dimension-Independent Sparse Fourier Transforms

• Karl Bringmann
• Michael Kapralov
• Mikhail Makarov
• Vasileios Nakos
• Amir Yagudin
• Amir Zandieh

We are interested in the well-studied Sparse Fourier transform problem, where one aims to quickly recover an approximately Fourier k -sparse domain vector from observing its time domain representation x. In the exact k -sparse case the best known dimension-independent algorithm runs in near cubic time in k and it is unclear whether a faster algorithm like in low dimensions is possible. Beyond that, all known approaches either suffer from an exponential dependence of their runtime on the dimension d or can only tolerate a trivial amount of noise. This is in sharp contrast with the classical FFT algorithm of Cooley and Tukey, which is stable and completely insensitive to the dimension of the input vector: its runtime is O ( N log N ) in any dimension d for N = n d. Our work aims to address the above issues. First, we provide a translation/reduction of the exactly k -sparse Sparse FT problem to a concrete tree exploration task which asks to recover k leaves in a full binary tree under certain exploration rules. Subsequently, we provide (a) an almost quadratic in k time algorithm for the latter task, and (b) evidence that obtaining a strongly subquadratic time for Sparse FT via this approach is likely to be impossible. We achieve the latter by proving a conditional quadratic time lower bound on sparse polynomial multipoint evaluation (the classical non-equispaced sparse Fourier transform problem) which is a core routine in the aforementioned translation. Thus, our results combined can be viewed as an almost complete understanding of this approach, which is the only known approach that yields sublinear time dimension-independent Sparse FT algorithms. Subsequently, we provide a robustification of our algorithm, yielding a robust cubic time algorithm under bounded ℓ 2 noise. This requires proving new structural properties of the recently introduced adaptive aliasing filters combined with a variety of new techniques and ideas. Lastly, we provide a preliminary experimental evaluation comparing the runtime of our algorithm to FFTW and SFFT 2. 0.

STOC Conference 2022 Conference Paper

Almost-optimal sublinear-time edit distance in the low distance regime

• Karl Bringmann
• Alejandro Cassis
• Nick Fischer
• Vasileios Nakos

We revisit the task of computing the edit distance in sublinear time. In the ( k , K )-gap edit distance problem we are given oracle access to two strings of length n and the task is to distinguish whether their edit distance is at most k or at least K . It has been established by Goldenberg, Krauthgamer and Saha (FOCS ’19), with improvements by Kociumaka and Saha (FOCS ’20), that the ( k , k 2 )-gap problem can be solved in time O ( n / k + poly( k )). One of the most natural questions in this line of research is whether the ( k , k 2 )-gap is best-possible for the running time O ( n / k + poly( k )).

SODA Conference 2022 Conference Paper

Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution

• Karl Bringmann
• Nick Fischer
• Vasileios Nakos

Computing the convolution A∗B of two length- n integer vectors A, B is a core problem in several disciplines. It frequently comes up as a subroutine in various problem domains, e. g. in algorithms for Knapsack, k -SUM, All-Pairs Shortest Paths, and string pattern matching problems. For these applications it typically suffices to compute convolutions of nonnegative vectors. This problem can be classically solved in time O ( n log n ) using the Fast Fourier Transform. However, in many applications the involved vectors are sparse and hence one could hope for output-sensitive algorithms to compute nonnegative convolutions. This question was raised by Muthukrishnan and solved by Cole and Hariharan (STOC '02) by a randomized algorithm running in near-linear time in the (unknown) output-size t and recently improved by Bringmann, Fischer and Nakos (STOC '21) in O ( k log k ) Monte Carlo time. Chan and Lewenstein (STOC '15) presented a deterministic algorithm with a overhead in running time and the additional assumption that a small superset of the output is given; this assumption was later removed by Bringmann and Nakos (ICALP '21). In this paper we present the first deterministic near-linear-time algorithm for computing sparse nonnegative convolutions. This immediately gives improved deterministic algorithms for the state-of-the-art of output-sensitive Subset Sum, block-mass pattern matching, N -fold Boolean convolution, and others, matching up to log-factors the fastest known randomized algorithms for these problems. Our algorithm is a blend of algebraic and combinatorial ideas and techniques. Additionally, we provide two fast Las Vegas algorithms for computing sparse nonnegative convolutions. In particular, we present a simple O ( t log 2 t ) time algorithm, which is an accessible alternative to Cole and Hariharan's algorithm. Subsequently, we further refine this new algorithm to run in Las Vegas time O(t log t · log log t ), which matches the running time of the dense case apart from the log log t factor.

SODA Conference 2021 Conference Paper

A Fine-Grained Perspective on Approximating Subset Sum and Partition

• Karl Bringmann
• Vasileios Nakos

Approximating S ubset S um is a classic and fundamental problem in computer science and mathematical optimization. The state-of-the-art approximation scheme for S ubset S um computes a (1 – ∊ )-approximation in time [Gens, Levner'78, Kellerer et al. '97]. In particular, a (1 – 1/ n )-approximation can be computed in time. We establish a connection to Min-Plus-Convolution, a problem that is of particular interest in fine-grained complexity theory and can be solved naively in time. Our main result is that computing a (1 – 1/ n )-approximation for S ubset S um is subquadratically equivalent to Min-Plus-Convolution. Thus, assuming the Min-Plus-Convolution conjecture from fine-grained complexity theory, there is no approximation scheme for S ubset S um with strongly subquadratic dependence on n and 1/ ∊. In the other direction, our reduction allows us to transfer known lower order improvements from Min-Plus-Convolution to S ubset S um, which yields a mildly subquadratic randomized approximation scheme. This adds the first approximation problem to the list of problems that are equivalent to Min-Plus-Convolution. For the related P artition problem, an important special case of S ubset S um, the state of the art is a randomized approximation scheme running in time [Mucha et al. '19]. We adapt our reduction from S ubset S um to Min-Plus-Convolution to obtain a related reduction from P artition to Min-Plus-Convolution. This yields an improved approximation scheme for P artition running in time. Our algorithm is the first deterministic approximation scheme for P artition that breaks the quadratic barrier.

STOC Conference 2021 Conference Paper

Sparse nonnegative convolution is equivalent to dense nonnegative convolution

• Karl Bringmann
• Nick Fischer
• Vasileios Nakos

Computing the convolution A ⋆ B of two length- n vectors A , B is an ubiquitous computational primitive, with applications in a variety of disciplines. Within theoretical computer science, applications range from string problems to Knapsack-type problems, and from 3SUM to All-Pairs Shortest Paths. These applications often come in the form of nonnegative convolution, where the entries of A , B are nonnegative integers. The classical algorithm to compute A ⋆ B uses the Fast Fourier Transform (FFT) and runs in time O ( n log n ).

FOCS Conference 2020 Conference Paper

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 k defective items out of a population of size n, using m ≪ n disjunctive measurements. In the non-adaptive setting, the most widely used combinatorial objects are disjunct and list-disjunct matrices, which define incidence matrices of test schemes. Disjunct matrices allow the identification of the exact set of defectives, whereas list disjunct matrices identify a small superset of the defectives. Apart from the combinatorial guarantees, it is often of key interest to equip measurement designs with efficient decoding algorithms. The most efficient decoders should run in sublinear time in n, and ideally near-linear in the number of measurements m. In this work, we give several constructions with an optimal number of measurements and near-optimal decoding time for the most fundamental group testing tasks, as well as for central tasks in the compressed sensing and heavy hitters literature. For many of those tasks, the previous measurement-optimal constructions needed time either quadratic in the number of measurements or linear in the universe size. Among our results are the following: a construction of disjunct matrices matching the best-known construction in terms of the number of rows m, but achieving nearly linear decoding time in m; a construction of list disjunct matrices with the optimal m=O(klog(n/k) number of rows and nearly linear decoding time in m; error-tolerant variations of the above constructions; a non-adaptive group testing scheme for the “for-each” model with m=O(klogn) measurements and O(m) decoding time; a streaming algorithm for the “for-all” version of the heavy hitters problem in the strict turnstile model with near-optimal query time, as well as a “list decoding” variant obtaining also near-optimal update time and O(klog(n/k)) space usage; an l2/l2 weak identification system for compressed sensing with nearly optimal sample complexity and nearly linear decoding time in the sketch length. Most of our results are obtained via a clean and novel approach that avoids list-recoverable codes or related complex techniques that were present in almost every state-of-the-art work on efficiently decodable constructions of such objects.

STOC Conference 2020 Conference Paper

Top-k-convolution and the quest for near-linear output-sensitive subset sum

• Karl Bringmann
• Vasileios Nakos

In the classical SubsetSum problem we are given a set X and a target t , and the task is to decide whether there exists a subset of X which sums to t . A recent line of research has resulted in ( t · poly (log t ))-time algorithms, which are (near-)optimal under popular complexity-theoretic assumptions. On the other hand, the standard dynamic programming algorithm runs in time O ( n · | S ( X , t )|), where S ( X , t ) is the set of all subset sums of X that are smaller than t . All previous pseudopolynomial algorithms actually solve a stronger task, since they actually compute the whole set S ( X , t ). As the aforementioned two running times are incomparable, in this paper we ask whether one can achieve the best of both worlds: running time | S ( X , t )|· poly (log t ). In particular, we ask whether S ( X , t ) can be computed in near-linear time in the output-size. Using a diverse toolkit containing techniques such as color coding, sparse recovery, and sumset estimates, we make considerable progress towards this question and design an algorithm running in time | S ( X , t )| 4/3 · poly (log t ). Central to our approach is the study of top- k -convolution , a natural problem of independent interest: given degree- d sparse polynomials with non-negative coefficients, compute the lowest k non-zero monomials of their product. We design an algorithm running in time k 4/3 poly (log d ), by a combination of sparse convolution and sumset estimates considered in Additive Combinatorics. Moreover, we provide evidence that going beyond some of the barriers we have faced requires either an algorithmic breakthrough or possibly new techniques from Additive Combinatorics on how to pass from information on restricted sumsets to information on unrestricted sumsets.

FOCS Conference 2019 Conference Paper

(Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless

• Vasileios Nakos
• Zhao Song 0002
• Zhengyu Wang

In this paper, we consider the extensively studied problem of computing a k-sparse approximation to the d-dimensional Fourier transform of a length n signal. Our algorithm uses O(k log k log n) samples, is dimension-free, operates for any universe size, and achieves the strongest ℓ ∞ /ℓ 2 guarantee, while running in a time comparable to the Fast Fourier Transform. In contrast to previous algorithms which proceed either via the Restricted Isometry Property or via filter functions, our approach offers a fresh perspective to the sparse Fourier Transform problem.

STOC Conference 2019 Conference Paper

Stronger l 2 /l 2 compressed sensing; without iterating

• Vasileios Nakos
• Zhao Song 0002

We consider the extensively studied problem of ℓ 2 /ℓ 2 compressed sensing. The main contribution of our work is an improvement over [Gilbert, Li, Porat and Strauss, STOC 2010] with faster decoding time and significantly smaller column sparsity, answering two open questions of the aforementioned work.