5 citations · 19 across the 20 of their papers we have counts for
20 papers · 1 filter
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…
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…
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…
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…
(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…
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…
Predicting Positive and Negative Links with Noisy Queries: Theory & Practice
Charalampos E. Tsourakakis, Michael Mitzenmacher, Kasper Green Larsen +4
Social networks involve both positive and negative relationships, which can be captured in signed graphs. The {\em edge sign prediction problem} aims to predict whether an interact…
On Low-Risk Heavy Hitters and Sparse Recovery Schemes
Yi Li, Vasileios Nakos, David Woodruff
We study the heavy hitters and related sparse recovery problems in the low-failure probability regime. This regime is not well-understood, and has only been studied for non-adaptiv…
Sublinear-Time Algorithms for Compressive Phase Retrieval
Yi Li, Vasileios Nakos
In the compressive phase retrieval problem, or phaseless compressed sensing, or compressed sensing from intensity only measurements, the goal is to reconstruct a sparse or approxim…