Karl Bringmann

ORCID

Publication Activity (10 Years)

Years Active: 2008-2024
Publications (10 Years): 156

Top Venues

Saarland University (PHD)

Education History

Saarland University

PHD

Publications

Karl Bringmann, Allan Grønlund, Marvin Künnemann, Kasper Green Larsen
The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds. ITCS (2024)
Karl Bringmann, Nick Fischer, Ivor van der Hoog, Evangelos Kipouridis, Tomasz Kociumaka, Eva Rotenberg
Dynamic Dynamic Time Warping. SODA (2024)
Karl Bringmann
Approximating Subset Sum Ratio faster than Subset Sum. SODA (2024)
Karl Bringmann, Anita Dürr, Adam Polak
Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing. CoRR (2024)
Karl Bringmann
Knapsack with Small Items in Near-Quadratic Time. STOC (2024)
Karl Bringmann, Frank Staals, Karol Wegrzycki, Geert van Wordragen
Fine-Grained Complexity of Earth Mover's Distance Under Translation. SoCG (2024)
Karl Bringmann, Egor Gorbachev
A Fine-grained Classification of Subquadratic Patterns for Subgraph Listing and Friends. CoRR (2024)
Karl Bringmann, Alejandro Cassis, Nick Fischer, Tomasz Kociumaka
Faster Sublinear-Time Edit Distance. SODA (2024)
Karl Bringmann, Frank Staals, Karol Wegrzycki, Geert van Wordragen
Fine-Grained Complexity of Earth Mover's Distance under Translation. CoRR (2024)
Amir Abboud, Karl Bringmann, Nick Fischer, Marvin Künnemann
The Time Complexity of Fully Sparse Matrix Multiplication. SODA (2024)
Karl Bringmann, Vincent Cohen-Addad, Debarati Das
-Approximation for Longest Common Subsequence. ACM Trans. Algorithms 19 (1) (2023)
Karl Bringmann
Knapsack with Small Items in Near-Quadratic Time. CoRR (2023)
Karl Bringmann
Approximating Subset Sum Ratio faster than Subset Sum. CoRR (2023)
Karl Bringmann, Alejandro Cassis
Faster 0-1-Knapsack via Near-Convex Min-Plus-Convolution. CoRR (2023)
Karl Bringmann, Alejandro Cassis, Nick Fischer
Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster! FOCS (2023)
Karl Bringmann, Nick Fischer, Ivor van der Hoog, Evangelos Kipouridis, Tomasz Kociumaka, Eva Rotenberg
Dynamic Dynamic Time Warping. CoRR (2023)
Amir Abboud, Karl Bringmann, Nick Fischer
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics. STOC (2023)
Karl Bringmann, Alejandro Cassis
Faster 0-1-Knapsack via Near-Convex Min-Plus-Convolution. ESA (2023)
Karl Bringmann, Michael Kapralov, Mikhail Makarov, Vasileios Nakos, Amir Yagudin, Amir Zandieh
Traversing the FFT Computation Tree for Dimension-Independent Sparse Fourier Transforms. SODA (2023)
Amir Abboud, Karl Bringmann, Nick Fischer, Marvin Künnemann
The Time Complexity of Fully Sparse Matrix Multiplication. CoRR (2023)
Karl Bringmann, Alejandro Cassis, Nick Fischer, Tomasz Kociumaka
Faster Sublinear-Time Edit Distance. CoRR (2023)
Karl Bringmann, Allan Grønlund, Marvin Künnemann, Kasper Green Larsen
The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds. CoRR (2023)
Karl Bringmann, Alejandro Cassis, Nick Fischer
Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster! CoRR (2023)
Amir Abboud, Karl Bringmann, Seri Khoury, Or Zamir
Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond. STOC (2022)
Karl Bringmann, Alejandro Cassis
Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution. ICALP (2022)
Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos
Improved Sublinear-Time Edit Distance for Preprocessed Strings. ICALP (2022)
Amir Abboud, Karl Bringmann, Seri Khoury, Or Zamir
Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond. CoRR (2022)
Karl Bringmann, Nick Fischer, Danny Hermelin, Dvir Shabtay, Philip Wellnitz
Faster Minimization of Tardy Processing Time on a Single Machine. Algorithmica 84 (5) (2022)
Karl Bringmann, Nick Fischer, Vasileios Nakos
Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution. SODA (2022)
Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, Dániel Marx, André Nusser
Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves. SoCG (2022)
Amir Abboud, Karl Bringmann, Nick Fischer
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics. CoRR (2022)
Karl Bringmann, Alejandro Cassis, Nick Fischer, Marvin Künnemann
A Structural Investigation of the Approximability of Polynomial-Time Problems. CoRR (2022)
Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay
Scheduling lower bounds via AND subset sum. J. Comput. Syst. Sci. 127 (2022)
Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos
Improved Sublinear-Time Edit Distance for Preprocessed Strings. CoRR (2022)
Karl Bringmann, Alejandro Cassis
Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution. CoRR (2022)
Karl Bringmann, Nofar Carmeli
Unbalanced Triangle Detection and Enumeration Hardness for Unions of Conjunctive Queries. CoRR (2022)
Karl Bringmann, Nofar Carmeli, Stefan Mengel
Tight Fine-Grained Bounds for Direct Access on Join Queries. PODS (2022)
Karl Bringmann, Anne Driemel, André Nusser, Ioannis Psarros
Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fréchet Distance. SODA (2022)
Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, André Nusser, Zahra Parsaeian
Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs. SoCG (2022)
Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos
Almost-optimal sublinear-time edit distance in the low distance regime. STOC (2022)
Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos
Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime. CoRR (2022)
Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, André Nusser, Zahra Parsaeian
Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs. CoRR (2022)
Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay
SETH-based Lower Bounds for Subset Sum and Bicriteria Path. ACM Trans. Algorithms 18 (1) (2022)
Bahareh Banyassady, Mark de Berg, Karl Bringmann, Kevin Buchin, Henning Fernau, Dan Halperin, Irina Kostitsyna, Yoshio Okamoto, Stijn Slot
Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds. CoRR (2022)
Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, Dániel Marx, André Nusser
Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves. CoRR (2022)
Bahareh Banyassady, Mark de Berg, Karl Bringmann, Kevin Buchin, Henning Fernau, Dan Halperin, Irina Kostitsyna, Yoshio Okamoto, Stijn Slot
Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds. SoCG (2022)
Karl Bringmann, Alejandro Cassis, Nick Fischer, Marvin Künnemann
A Structural Investigation of the Approximability of Polynomial-Time Problems. ICALP (2022)
Karl Bringmann, Ralph Keusch, Johannes Lengler, Yannic Maus, Anisur Rahaman Molla
Greedy routing and the algorithmic small-world phenomenon. J. Comput. Syst. Sci. 125 (2022)
Karl Bringmann, Nofar Carmeli, Stefan Mengel
Tight Fine-Grained Bounds for Direct Access on Join Queries. CoRR (2022)
Karl Bringmann, Vasileios Nakos
Fast n-Fold Boolean Convolution via Additive Combinatorics. ICALP (2021)
Karl Bringmann, Vincent Cohen-Addad, Debarati Das
-Approximation for Longest Common Subsequence. CoRR (2021)
Karl Bringmann, Nick Fischer, Vasileios Nakos
Sparse nonnegative convolution is equivalent to dense nonnegative convolution. STOC (2021)
Karl Bringmann, Vasileios Nakos
A Fine-Grained Perspective on Approximating Subset Sum and Partition. SODA (2021)
Karl Bringmann, Jasper Slusallek
Current Algorithms for Detecting Subgraphs of Bounded Treewidth Are Probably Optimal. ICALP (2021)
Karl Bringmann, André Nusser
Translating Hausdorff is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation. CoRR (2021)
Karl Bringmann, André Nusser
Translating Hausdorff Is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation. SoCG (2021)
Karl Bringmann
Fine-Grained Complexity Theory: Conditional Lower Bounds for Computational Geometry. CiE (2021)
Kyriakos Axiotis, Arturs Backurs, Karl Bringmann, Ce Jin, Vasileios Nakos, Christos Tzamos, Hongxun Wu
Fast and Simple Modular Subset Sum. SOSA (2021)
Karl Bringmann, Michael Kapralov, Mikhail Makarov, Vasileios Nakos, Amir Yagudin, Amir Zandieh
Sparse Fourier Transform by traversing Cooley-Tukey FFT computation graphs. CoRR (2021)
Karl Bringmann
Fine-Grained Complexity Theory: Conditional Lower Bounds for Computational Geometry. CoRR (2021)
Karl Bringmann, Nick Fischer, Vasileios Nakos
Sparse Nonnegative Convolution Is Equivalent to Dense Nonnegative Convolution. CoRR (2021)
Karl Bringmann, Anne Driemel, André Nusser, Ioannis Psarros
Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fréchet Distance. CoRR (2021)
Karl Bringmann, Marvin Künnemann, André Nusser
Discrete Fréchet Distance under Translation: Conditional Hardness and an Improved Algorithm. ACM Trans. Algorithms 17 (3) (2021)
Karl Bringmann, Vasileios Nakos
Fast n-fold Boolean Convolution via Additive Combinatorics. CoRR (2021)
Karl Bringmann, Alejandro Cassis, Nick Fischer, Marvin Künnemann
Fine-Grained Completeness for Optimization in P. APPROX-RANDOM (2021)
Karl Bringmann, Marvin Künnemann, André Nusser
Walking the dog fast in practice: Algorithm engineering of the Fréchet distance. J. Comput. Geom. 12 (1) (2021)
Karl Bringmann, Vasileios Nakos
Top-k-Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum. CoRR (2021)
Karl Bringmann, Debarati Das
-Approximation for Longest Common Subsequence. ICALP (2021)
Karl Bringmann, Philip Wellnitz
On Near-Linear-Time Algorithms for Dense Subset Sum. SODA (2021)
Karl Bringmann, Nick Fischer, Vasileios Nakos
Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution. CoRR (2021)
Karl Bringmann, Alejandro Cassis, Nick Fischer, Marvin Künnemann
Fine-Grained Completeness for Optimization in P. CoRR (2021)
Karl Bringmann, Jasper Slusallek
Current Algorithms for Detecting Subgraphs of Bounded Treewidth are Probably Optimal. CoRR (2021)
Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann
Impossibility Results for Grammar-Compressed Linear Algebra. NeurIPS (2020)
Karl Bringmann, Philip Wellnitz
On Near-Linear-Time Algorithms for Dense Subset Sum. CoRR (2020)
Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann
Impossibility Results for Grammar-Compressed Linear Algebra. CoRR (2020)
Karl Bringmann, Nick Fischer, Danny Hermelin, Dvir Shabtay, Philip Wellnitz
Faster Minimization of Tardy Processing Time on a Single Machine. ICALP (2020)
Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay
Scheduling Lower Bounds via AND Subset Sum. CoRR (2020)
Karl Bringmann, Nick Fischer, Danny Hermelin, Dvir Shabtay, Philip Wellnitz
Faster Minimization of Tardy Processing\newline Time on a Single Machine. CoRR (2020)
Karl Bringmann, Bhaskar Ray Chaudhury
Polyline simplification has cubic complexity. J. Comput. Geom. 11 (2) (2020)
Karl Bringmann, Pawel Gawrychowski, Shay Mozes, Oren Weimann
Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (Unless APSP Can). ACM Trans. Algorithms 16 (4) (2020)
Karl Bringmann, Vasileios Nakos
Top-k-convolution and the quest for near-linear output-sensitive subset sum. STOC (2020)
Karl Bringmann, Thore Husfeldt, Måns Magnusson
Multivariate Analysis of Orthogonal Range Searching and Graph Distances. Algorithmica 82 (8) (2020)
Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay
Scheduling Lower Bounds via AND Subset Sum. ICALP (2020)
Karl Bringmann, Marvin Künnemann, André Nusser
When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance Under Translation. ESA (2020)
Kyriakos Axiotis, Arturs Backurs, Karl Bringmann, Ce Jin, Vasileios Nakos, Christos Tzamos, Hongxun Wu
Fast and Simple Modular Subset Sum. CoRR (2020)
Karl Bringmann, Marvin Künnemann, André Nusser
When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation. CoRR (2020)
Karl Bringmann
Approximating Subset Sum is equivalent to Min-Plus-Convolution. CoRR (2019)
Karl Bringmann, Marvin Künnemann, Karol Wegrzycki
Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max. STOC (2019)
Karl Bringmann, Sándor Kisfaludi-Bak, Michal Pilipczuk, Erik Jan van Leeuwen
On Geometric Set Cover for Orthants. ESA (2019)
Karl Bringmann, Nick Fischer, Marvin Künnemann
A Fine-Grained Analogue of Schaefer's Theorem in P: Dichotomy of Exists^k-Forall-Quantified First-Order Graph Properties. Computational Complexity Conference (2019)
Frank Ban, Vijay Bhattiprolu, Karl Bringmann, Pavel Kolev, Euiwoong Lee, David P. Woodruff
A PTAS for ℓp-Low Rank Approximation. SODA (2019)
Karl Bringmann
Fine-Grained Complexity Theory (Tutorial). STACS (2019)
Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay
SETH-Based Lower Bounds for Subset Sum and Bicriteria Path. SODA (2019)
Karl Bringmann, Marvin Künnemann, André Nusser
Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance. CoRR (2019)
Karl Bringmann, Ralph Keusch, Johannes Lengler
Geometric inhomogeneous random graphs. Theor. Comput. Sci. 760 (2019)
Karl Bringmann, Bhaskar Ray Chaudhury
Polyline Simplification has Cubic Complexity. SoCG (2019)
Karl Bringmann, Philip Wellnitz, Marvin Künnemann
Few Matches or Almost Periodicity: Faster Pattern Matching with Mismatches in Compressed Texts. SODA (2019)
Karl Bringmann, Fabrizio Grandoni, Barna Saha, Virginia Vassilevska Williams
Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product. SIAM J. Comput. 48 (2) (2019)
Karl Bringmann, Marvin Künnemann, André Nusser
Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance. SoCG (2019)
Karl Bringmann, Marvin Künnemann, Karol Wegrzycki
Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max. CoRR (2019)

Karl Bringmann.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Karl Bringmann