Nick Fischer

Postdoc in Computer Science

INSAIT
nick.fischer@insait.ai

About

I am a researcher broadly interested in theoretical computer science. My specific research interests include fine-grained complexity and algorithm design, computational problems related to additive combinatorics, string algorithms, and algebraic methods.

Currently, I am a postdoc at INSAIT, Bulgaria. Before, I was a postdoc at Weizmann Institute of Science, where I was hosted by Amir Abboud. Before that, I completed my undergrad and PhD at Saarland University and Max Planck Institute for Informatics, advised by Karl Bringmann.

Publications

A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection

Amir Abboud, Shyan Akmal, Nick Fischer

l2/l2 Sparse Recovery via Weighted Hypergraph Peeling

Nick Fischer, Vasileios Nakos

A Simple Algorithm for Trimmed Multipoint Evaluation

Nick Fischer, Melvin Kallmayer, Leo Wennmann

Hardness of Median and Center in the Ulam Metric

Nick Fischer, Elazar Goldenberg, Mursalin Habib, Karthik C.S.

Near-Optimal Directed Low-Diameter Decompositions

Karl Bringmann, Nick Fischer, Bernhard Haeupler, Rustam Latypov

The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs

Nick Fischer, Marvin Künnemann, Mirza Redzic, Julian Stieß

All-Pairs Shortest Paths with Few Weights per Node

Amir Abboud, Nick Fischer, Ce Jin, Virginia Vassilevska Williams, Zoe Xi

A Faster Algorithm for Constrained Correlation Clustering

Nick Fischer, Evangelos Kipouridis, Jonas Klausen, Mikkel Thorup

Recognizing Sumsets is NP-Complete

Amir Abboud, Nick Fischer, Ron Safier, Nathan Wallheimer

Beating Bellman's Algorithm for Subset Sum

Karl Bringmann, Nick Fischer, Vasileios Nakos

Sumsets, 3SUM, Subset Sum: Now for Real!

Nick Fischer

New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching

Nick Fischer, Ce Jin, Yinzhan Xu

A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths

Nick Fischer, Bernhard Haeupler, Rustam Latypov, Antti Roeyskoe, Aurelio L. Sulser

Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time

Nick Fischer, Leo Wennmann

New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms

Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka

Faster Combinatorial k-Clique Algorithms

Amir Abboud, Nick Fischer, Yarin Shechter

Deterministic 3SUM-Hardness

Nick Fischer, Piotr Kaliciak, Adam Polak

The Time Complexity of Fully Sparse Matrix Multiplication

Amir Abboud, Karl Bringmann, Nick Fischer, Marvin Künnemann

Faster Sublinear-Time Edit Distance

Karl Bringmann, Alejandro Cassis, Nick Fischer, Tomasz Kociumaka

Dynamic Dynamic Time Warping

Karl Bringmann, Nick Fischer, Ivor van der Hoog, Evangelos Kipouridis, Tomasz Kociumaka, Eva Rotenberg

The Effect of Sparsity on k-Dominating Set and Related First-Order Graph Properties

Nick Fischer, Marvin Künnemann, Mirza Redzic

Deterministic Sparse Pattern Matching via the Baur-Strassen Theorem

Nick Fischer

Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!

Karl Bringmann, Alejandro Cassis, Nick Fischer

Can You Solve Closest String Faster than Exhaustive Search?

Amir Abboud, Nick Fischer, Elazar Goldenberg, Karthik C.S., Ron Safier

Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics

Amir Abboud, Karl Bringmann, Nick Fischer

A Structural Investigation of the Approximability of Polynomial-Time Problems

Karl Bringmann, Alejandro Cassis, Nick Fischer, Marvin Künnemann

Improved Sublinear-Time Edit Distance for Preprocessed Strings

Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos

Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime

Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos

Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution

Karl Bringmann, Nick Fischer, Vasileios Nakos

Fine-Grained Completeness for Optimization in P

Karl Bringmann, Alejandro Cassis, Nick Fischer, Marvin Künnemann

Sparse Nonnegative Convolution Is Equivalent to Dense Nonnegative Convolution

Karl Bringmann, Nick Fischer, Vasileios Nakos

Faster Minimization of Tardy Processing Time on a Single Machine

Karl Bringmann, Nick Fischer, Danny Hermelin, Dvir Shabtay, Philip Wellnitz

The Computational Complexity of Plethysm Coefficients

Nick Fischer, Christian Ikenmeyer

A Fine-Grained Analogue of Schaefer’s Theorem in P: Dichotomy of ∃ᵏ∀-Quantified First-Order Graph Properties

Karl Bringmann, Nick Fischer, Marvin Künnemann

Axiomatising Infinitary Probabilistic Weak Bisimilarity of Finite-State Behaviours

Nick Fischer, Rob van Glabbeek