Arrow Research search

Author name cluster

Vasileios Nakos

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

11 papers
1 author row

Possible papers

11

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.

Details

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.

Details

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.

Details

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.

Details

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.

Details