7 papers
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 $…
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…
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…
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…
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…