MPI-INF Logo
Homepage

Contact

Nick Fischer

Nick Fischer

Update: I am now a postdoc at Weizmann Institute of Science.

Max-Planck-Institut für Informatik
Department 1: Algorithms and Complexity
 office: Campus E1 4, Room 328
Saarland Informatics Campus
66123 Saarbrücken
Germany
 email: Get my email address via email
 phone: +49 681 9325-1028

Research Interests

  • Fine-Grained Complexity and Algorithm Design
  • Computational Problems related to Additive Combinatorics
  • String Algorithms

Research Papers

  1. Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!
    Karl Bringmann, Alejandro Cassis and Nick Fischer
  2. Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics (STOC 2023, to appear)
    Amir Abboud, Karl Bringmann and Nick Fischer
  3. Improved Sublinear-Time Edit Distance for Preprocessed Strings (ICALP 2022)
    Karl Bringmann, Alejandro Cassis, Nick Fischer and Vasileios Nakos
  4. A Structural Investigation of the Approximability of Polynomial-Time Problems (ICALP 2022)
    Karl Bringmann, Alejandro Cassis, Nick Fischer and Marvin Künnemann
  5. Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime (STOC 2022)
    Karl Bringmann, Alejandro Cassis, Nick Fischer and Vasileios Nakos
  6. Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution (SODA 2022)
    Karl Bringmann, Nick Fischer and Vasileios Nakos
  7. Sparse Nonnegative Convolution is Equivalent to Dense Nonnegative Convolution (STOC 2021)
    Karl Bringmann, Nick Fischer and Vasileios Nakos
  8. Fine-Grained Completeness for Optimization in P (APPROX 2021)
    Karl Bringmann, Alejandro Cassis, Nick Fischer and Marvin Künnemann
  9. The Computational Complexity of Plethysm Coefficients (CC 2020)
    Nick Fischer and Christian Ikenmeyer
  10. Faster Minimization of Tardy Processing Time on a Single Machine (ICALP 2020)
    Karl Bringmann, Nick Fischer, Danny Hermelin, Dvir Shabtay and Philip Wellnitz
  11. A Fine-Grained Analogue of Schaefer’s Theorem in P: Dichotomy of ∃k∀-Quantified First-Order Graph Properties (CCC 2019)
    Karl Bringmann, Nick Fischer and Marvin Künnemann
  12. Axiomatising Infinitary Probabilistic Weak Bisimilarity of Finite-State Behaviours (JLAMP 2019)
    Nick Fischer and Rob van Glabbeek

Teaching

Education