1 citations · 1 across the 5 of their papers we have counts for
8 papers
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…
Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time
Nick Fischer, Leo Wennmann
In this work we revisit the elementary scheduling problem . The goal is to select, among jobs with processing times and due dates, a subset of jobs with maximu…
Deterministic Sparse Pattern Matching via the Baur-Strassen Theorem
Nick Fischer
How fast can you test whether a constellation of stars appears in the night sky? This question can be modeled as the computational problem of testing whether a set of points ca…