Nick Fischer

According to our database, Nick Fischer authored at least 29 papers between 2019 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

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

Nick Fischer

CoRR, 2024

Beating Bellman's Algorithm for Subset Sum.

Karl Bringmann, Nick Fischer, Vasileios Nakos

CoRR, 2024

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

CoRR, 2024

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

Nick Fischer, Ce Jin, Yinzhan Xu

CoRR, 2024

Recognizing Sumsets is NP-Complete.

Amir Abboud, Nick Fischer, Ron Safier, Nathan Wallheimer

CoRR, 2024

The Effect of Sparsity on <i>k</i>-Dominating Set and Related First-Order Graph Properties.

Nick Fischer, Marvin Künnemann, Mirza Redzic

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Deterministic Sparse Pattern Matching via the Baur-Strassen Theorem.

Nick Fischer

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Dynamic Dynamic Time Warping.

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

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Faster Sublinear-Time Edit Distance.

Karl Bringmann, Alejandro Cassis, Nick Fischer, Tomasz Kociumaka

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

The Time Complexity of Fully Sparse Matrix Multiplication.

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

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Faster Combinatorial k-Clique Algorithms.

Amir Abboud, Nick Fischer, Yarin Shechter

Proceedings of the LATIN 2024: Theoretical Informatics, 2024

Deterministic 3SUM-Hardness.

Nick Fischer, Piotr Kaliciak, Adam Polak

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

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

Nick Fischer, Leo Wennmann

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

2023

Algorithms for sparse convolution and sublinear edit distance.

Nick Fischer

PhD thesis, 2023

New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms.

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

Electron. Colloquium Comput. Complex., 2023

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

Nick Fischer, Marvin Künnemann, Mirza Redzic

CoRR, 2023

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

Amir Abboud, Karl Bringmann, Nick Fischer

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

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

Karl Bringmann, Alejandro Cassis, Nick Fischer

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Can You Solve Closest String Faster Than Exhaustive Search?

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

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

2022

Faster Minimization of Tardy Processing Time on a Single Machine.

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

Algorithmica, 2022

Almost-optimal sublinear-time edit distance in the low distance regime.

Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution.

Karl Bringmann, Nick Fischer, Vasileios Nakos

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Improved Sublinear-Time Edit Distance for Preprocessed Strings.

Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

A Structural Investigation of the Approximability of Polynomial-Time Problems.

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

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

2021

Sparse nonnegative convolution is equivalent to dense nonnegative convolution.

Karl Bringmann, Nick Fischer, Vasileios Nakos

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Fine-Grained Completeness for Optimization in P.

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

Proceedings of the Approximation, 2021

2020

The Computational Complexity of Plethysm Coefficients.

Nick Fischer, Christian Ikenmeyer

Comput. Complex., 2020

2019

Axiomatising infinitary probabilistic weak bisimilarity of finite-state behaviours.

Nick Fischer, Rob van Glabbeek

J. Log. Algebraic Methods Program., 2019

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

Proceedings of the 34th Computational Complexity Conference, 2019