Nick Fischer

Postdoc, INSAIT

About Me

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 have completed my undergrad and PhD at Saarland University and Max Planck Institute for Informatics, advised by Karl Bringmann.

Publications

Recognizing Sumsets is NP-Complete

Amir Abboud, Nick Fischer, Ron Safier, Nathan Wallheimer

SODA 2025

Beating Bellman's Algorithm for Subset Sum

Karl Bringmann, Nick Fischer, Vasileios Nakos

SODA 2025

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

Nick Fischer

SODA 2025

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

Nick Fischer, Ce Jin, Yinzhan Xu

SODA 2025

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

SOSA 2025

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

Nick Fischer, Leo Wennmann

ICALP 2024

New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms

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

STOC 2024

Faster Combinatorial k-Clique Algorithms

Amir Abboud, Nick Fischer, Yarin Shechter

LATIN 2024

Deterministic 3SUM-Hardness

Nick Fischer, Piotr Kaliciak, Adam Polak

ITCS 2024

The Time Complexity of Fully Sparse Matrix Multiplication

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

SODA 2024

Faster Sublinear-Time Edit Distance

Karl Bringmann, Alejandro Cassis, Nick Fischer, Tomasz Kociumaka

SODA 2024

Dynamic Dynamic Time Warping

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

SODA 2024

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

Nick Fischer, Marvin Künnemann, Mirza Redzic

SODA 2024

Deterministic Sparse Pattern Matching via the Baur-Strassen Theorem

Nick Fischer

SODA 2024

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

Karl Bringmann, Alejandro Cassis, Nick Fischer

FOCS 2023

Can You Solve Closest String Faster than Exhaustive Search?

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

ESA 2023

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

Amir Abboud, Karl Bringmann, Nick Fischer

STOC 2023

Improved Sublinear-Time Edit Distance for Preprocessed Strings

Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos

ICALP 2022

A Structural Investigation of the Approximability of Polynomial-Time Problems

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

ICALP 2022

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

Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos

STOC 2022

Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution

Karl Bringmann, Nick Fischer, Vasileios Nakos

SODA 2022

Fine-Grained Completeness for Optimization in P

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

APPROX 2021

Sparse Nonnegative Convolution Is Equivalent to Dense Nonnegative Convolution

Karl Bringmann, Nick Fischer, Vasileios Nakos

STOC 2021

Faster Minimization of Tardy Processing Time on a Single Machine

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

ICALP 2020
Algorithmica 2022

The Computational Complexity of Plethysm Coefficients

Nick Fischer, Christian Ikenmeyer

CC 2020

A Fine-Grained Analogue of Schaefer’s Theorem in P: Dichotomy of Exists^k-Forall-Quantified First-Order Graph Properties

Karl Bringmann, Nick Fischer, Marvin Künnemann

CCC 2019

Axiomatising Infinitary Probabilistic Weak Bisimilarity of Finite-State Behaviours

Nick Fischer, Rob van Glabbeek

JLAMP 2019