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 at Max Planck Institute for Informatics in Saarbrücken, Germany. Before, I was a postdoc at INSAIT, and before that a postdoc at Weizmann Institute of Science, hosted by Amir Abboud. I completed my PhD and undergrad 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
Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems
Aaron Bernstein, Sayan Bhattacharya, Nick Fischer, Peter Kiss, Thatchaphol Saranurak
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
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
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
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
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