8 papers · 1 filter
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…
Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems
Aaron Bernstein, Sayan Bhattacharya, Nick Fischer +2
We establish the first update-time separation between dynamic algorithms against oblivious adversaries and those against adaptive adversaries in natural dynamic graph problems, bas…
A Simple Algorithm for Trimmed Multipoint Evaluation
Nick Fischer, Melvin Kallmayer, Leo Wennmann
Evaluating a polynomial on a set of points is a fundamental task in computer algebra. In this work, we revisit a particular variant called trimmed multipoint evaluation: given an $…
Hardness of Median and Center in the Ulam Metric
Nick Fischer, Elazar Goldenberg, Mursalin Habib +1
The classical rank aggregation problem seeks to combine a set X of n permutations into a single representative "consensus" permutation. In this paper, we investigate two fundamenta…
A Faster Algorithm for Constrained Correlation Clustering
Nick Fischer, Evangelos Kipouridis, Jonas Klausen +1
In the Correlation Clustering problem we are given nodes, and a preference for each pair of nodes indicating whether we prefer the two endpoints to be in the same cluster or no…
Sumsets, 3SUM, Subset Sum: Now for Real!
Nick Fischer
We study a broad class of algorithmic problems with an "additive flavor" such as computing sumsets, 3SUM, Subset Sum and geometric pattern matching. Our starting point is that thes…