Karl Bringmann

241 papers A* 60A 23B 7C 3Journal 129Unranked 16

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Dynamic and Streaming Algorithms for Union Volume Estimation. CoRR Sujoy Bhore, Karl Bringmann, Timothy M. Chan, Yanheng Wang
2026	J	`jnl`	Fine-Grained Complexity of Continuous Euclidean k-Center. CoRR Lotte Blank, Karl Bringmann, Parinya Chalermsook, Karthik C. S., Benedikt Kolbe, Hung Le, Geert van Wordragen
2026	J	`jnl`	Tight (S)ETH-based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-Machine Scheduling. CoRR Karl Bringmann, Anita Dürr, Karol Wegrzycki
2025	A*	`conf`	A Fine-Grained Classification of Subquadratic Patterns for Subgraph Listing and Friends. STOC Karl Bringmann, Egor Gorbachev
2025	A*	`conf`	Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation. SoCG Karl Bringmann, Kasper Green Larsen, André Nusser, Eva Rotenberg, Yanheng Wang
2025	A*	`conf`	Beating Bellman's Algorithm for Subset Sum. SODA Karl Bringmann, Nick Fischer, Vasileios Nakos
2025	A*	`conf`	Near-Optimal Directed Low-Diameter Decompositions. ICALP Karl Bringmann, Nick Fischer, Bernhard Haeupler, Rustam Latypov
2025	J	`jnl`	Near-Optimal Directed Low-Diameter Decompositions. CoRR Karl Bringmann, Nick Fischer, Bernhard Haeupler, Rustam Latypov
2025	J	`jnl`	Tight Fine-Grained Bounds for Direct Access on Join Queries. ACM Trans. Database Syst. Karl Bringmann, Nofar Carmeli, Stefan Mengel
2025	J	`jnl`	Unbalanced Triangle Detection and Enumeration Hardness for Unions of Conjunctive Queries. Log. Methods Comput. Sci. Karl Bringmann, Nofar Carmeli
2024	A*	`ed.`	51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, Tallinn, Estonia, July 8-12, 2024 ICALP Karl Bringmann, Martin Grohe, Gabriele Puppis, Ola Svensson
2024	J	`jnl`	A Fine-grained Classification of Subquadratic Patterns for Subgraph Listing and Friends. CoRR Karl Bringmann, Egor Gorbachev
2024	J	`jnl`	Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation. CoRR Karl Bringmann, Kasper Green Larsen, André Nusser, Eva Rotenberg, Yanheng Wang
2024	A*	`conf`	Approximating Subset Sum Ratio faster than Subset Sum. SODA Karl Bringmann
2024	J	`jnl`	Beating Bellman's Algorithm for Subset Sum. CoRR Karl Bringmann, Nick Fischer, Vasileios Nakos
2024	A*	`conf`	Dynamic Dynamic Time Warping. SODA Karl Bringmann, Nick Fischer, Ivor van der Hoog, Evangelos Kipouridis, Tomasz Kociumaka, Eva Rotenberg
2024	A	`conf`	Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing. ESA Karl Bringmann, Anita Dürr, Adam Polak
2024	J	`jnl`	Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing. CoRR Karl Bringmann, Anita Dürr, Adam Polak
2024	A	`conf`	Exploring the Approximability Landscape of 3SUM. ESA Karl Bringmann, Ahmed Ghazy, Marvin Künnemann
2024	A*	`conf`	Faster Sublinear-Time Edit Distance. SODA Karl Bringmann, Alejandro Cassis, Nick Fischer, Tomasz Kociumaka
2024	A*	`conf`	Fine-Grained Complexity of Earth Mover's Distance Under Translation. SoCG Karl Bringmann, Frank Staals, Karol Wegrzycki, Geert van Wordragen
2024	J	`jnl`	Fine-Grained Complexity of Earth Mover's Distance under Translation. CoRR Karl Bringmann, Frank Staals, Karol Wegrzycki, Geert van Wordragen
2024	J	`jnl`	Fine-grained complexity of Earth Mover's distance under translation. J. Comput. Geom. Karl Bringmann, Frank Staals, Karol Wegrzycki, Geert van Wordragen
2024	A*	`conf`	Knapsack with Small Items in Near-Quadratic Time. STOC Karl Bringmann
2024	A	`conf`	The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds. ITCS Karl Bringmann, Allan Grønlund, Marvin Künnemann, Kasper Green Larsen
2024	J	`jnl`	The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds. TheoretiCS Karl Bringmann, Allan Grønlund, Marvin Künnemann, Kasper Green Larsen
2024	A*	`conf`	The Time Complexity of Fully Sparse Matrix Multiplication. SODA Amir Abboud, Karl Bringmann, Nick Fischer, Marvin Künnemann
2023	J	`jnl`	A Linear-Time ACM Trans. Algorithms Karl Bringmann, Vincent Cohen-Addad, Debarati Das
2023	J	`jnl`	Approximating Subset Sum Ratio faster than Subset Sum. CoRR Karl Bringmann
2023	J	`jnl`	Dynamic Dynamic Time Warping. CoRR Karl Bringmann, Nick Fischer, Ivor van der Hoog, Evangelos Kipouridis, Tomasz Kociumaka, Eva Rotenberg
2023	A	`conf`	Faster 0-1-Knapsack via Near-Convex Min-Plus-Convolution. ESA Karl Bringmann, Alejandro Cassis
2023	J	`jnl`	Faster 0-1-Knapsack via Near-Convex Min-Plus-Convolution. CoRR Karl Bringmann, Alejandro Cassis
2023	J	`jnl`	Faster Sublinear-Time Edit Distance. CoRR Karl Bringmann, Alejandro Cassis, Nick Fischer, Tomasz Kociumaka
2023	J	`jnl`	Knapsack with Small Items in Near-Quadratic Time. CoRR Karl Bringmann
2023	A*	`conf`	Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster! FOCS Karl Bringmann, Alejandro Cassis, Nick Fischer
2023	J	`jnl`	Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster! CoRR Karl Bringmann, Alejandro Cassis, Nick Fischer
2023	A*	`conf`	Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics. STOC Amir Abboud, Karl Bringmann, Nick Fischer
2023	J	`jnl`	The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds. CoRR Karl Bringmann, Allan Grønlund, Marvin Künnemann, Kasper Green Larsen
2023	J	`jnl`	The Time Complexity of Fully Sparse Matrix Multiplication. CoRR Amir Abboud, Karl Bringmann, Nick Fischer, Marvin Künnemann
2023	A*	`conf`	Traversing the FFT Computation Tree for Dimension-Independent Sparse Fourier Transforms. SODA Karl Bringmann, Michael Kapralov, Mikhail Makarov, Vasileios Nakos, Amir Yagudin, Amir Zandieh
2022	—	`ed.`	5th Symposium on Simplicity in Algorithms, SOSA@SODA 2022, Virtual Conference, January 10-11, 2022 SOSA Karl Bringmann, Timothy M. Chan
2022	A*	`conf`	A Structural Investigation of the Approximability of Polynomial-Time Problems. ICALP Karl Bringmann, Alejandro Cassis, Nick Fischer, Marvin Künnemann
2022	J	`jnl`	A Structural Investigation of the Approximability of Polynomial-Time Problems. CoRR Karl Bringmann, Alejandro Cassis, Nick Fischer, Marvin Künnemann
2022	J	`jnl`	Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime. CoRR Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos
2022	A*	`conf`	Almost-optimal sublinear-time edit distance in the low distance regime. STOC Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos
2022	A*	`conf`	Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution. SODA Karl Bringmann, Nick Fischer, Vasileios Nakos
2022	A*	`conf`	Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves. SoCG Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, Dániel Marx, André Nusser
2022	J	`jnl`	Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves. CoRR Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, Dániel Marx, André Nusser
2022	J	`jnl`	Dynamic time warping under translation: Approximation guided by space-filling curves. J. Comput. Geom. Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, Dániel Marx, André Nusser
2022	A*	`conf`	Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution. ICALP Karl Bringmann, Alejandro Cassis
2022	J	`jnl`	Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution. CoRR Karl Bringmann, Alejandro Cassis
2022	J	`jnl`	Faster Minimization of Tardy Processing Time on a Single Machine. Algorithmica Karl Bringmann, Nick Fischer, Danny Hermelin, Dvir Shabtay, Philip Wellnitz
2022	J	`jnl`	Greedy routing and the algorithmic small-world phenomenon. J. Comput. Syst. Sci. Karl Bringmann, Ralph Keusch, Johannes Lengler, Yannic Maus, Anisur Rahaman Molla
2022	J	`jnl`	Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond. CoRR Amir Abboud, Karl Bringmann, Seri Khoury, Or Zamir
2022	A*	`conf`	Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond. STOC Amir Abboud, Karl Bringmann, Seri Khoury, Or Zamir
2022	A*	`conf`	Improved Sublinear-Time Edit Distance for Preprocessed Strings. ICALP Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos
2022	J	`jnl`	Improved Sublinear-Time Edit Distance for Preprocessed Strings. CoRR Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos
2022	J	`jnl`	SETH-based Lower Bounds for Subset Sum and Bicriteria Path. ACM Trans. Algorithms Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay
2022	J	`jnl`	Scheduling lower bounds via AND subset sum. J. Comput. Syst. Sci. Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay
2022	J	`jnl`	Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics. CoRR Amir Abboud, Karl Bringmann, Nick Fischer
2022	A*	`conf`	Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fréchet Distance. SODA Karl Bringmann, Anne Driemel, André Nusser, Ioannis Psarros
2022	A*	`conf`	Tight Fine-Grained Bounds for Direct Access on Join Queries. PODS Karl Bringmann, Nofar Carmeli, Stefan Mengel
2022	J	`jnl`	Tight Fine-Grained Bounds for Direct Access on Join Queries. CoRR Karl Bringmann, Nofar Carmeli, Stefan Mengel
2022	A*	`conf`	Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs. SoCG Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, André Nusser, Zahra Parsaeian
2022	J	`jnl`	Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs. CoRR Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, André Nusser, Zahra Parsaeian
2022	J	`jnl`	Unbalanced Triangle Detection and Enumeration Hardness for Unions of Conjunctive Queries. CoRR Karl Bringmann, Nofar Carmeli
2022	A*	`conf`	Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds. SoCG Bahareh Banyassady, Mark de Berg, Karl Bringmann, Kevin Buchin, Henning Fernau, Dan Halperin, Irina Kostitsyna, Yoshio Okamoto, Stijn Slot
2022	J	`jnl`	Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds. CoRR Bahareh Banyassady, Mark de Berg, Karl Bringmann, Kevin Buchin, Henning Fernau, Dan Halperin, Irina Kostitsyna, Yoshio Okamoto, Stijn Slot
2021	A*	`conf`	A Fine-Grained Perspective on Approximating Subset Sum and Partition. SODA Karl Bringmann, Vasileios Nakos
2021	A*	`conf`	A Linear-Time n ICALP Karl Bringmann, Debarati Das
2021	J	`jnl`	A Linear-Time n CoRR Karl Bringmann, Vincent Cohen-Addad, Debarati Das
2021	A*	`conf`	Current Algorithms for Detecting Subgraphs of Bounded Treewidth Are Probably Optimal. ICALP Karl Bringmann, Jasper Slusallek
2021	J	`jnl`	Current Algorithms for Detecting Subgraphs of Bounded Treewidth are Probably Optimal. CoRR Karl Bringmann, Jasper Slusallek
2021	J	`jnl`	Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution. CoRR Karl Bringmann, Nick Fischer, Vasileios Nakos
2021	J	`jnl`	Discrete Fréchet Distance under Translation: Conditional Hardness and an Improved Algorithm. ACM Trans. Algorithms Karl Bringmann, Marvin Künnemann, André Nusser
2021	—	`conf`	Fast and Simple Modular Subset Sum. SOSA Kyriakos Axiotis, Arturs Backurs, Karl Bringmann, Ce Jin, Vasileios Nakos, Christos Tzamos, Hongxun Wu
2021	A*	`conf`	Fast n-Fold Boolean Convolution via Additive Combinatorics. ICALP Karl Bringmann, Vasileios Nakos
2021	J	`jnl`	Fast n-fold Boolean Convolution via Additive Combinatorics. CoRR Karl Bringmann, Vasileios Nakos
2021	—	`conf`	Fine-Grained Completeness for Optimization in P. APPROX-RANDOM Karl Bringmann, Alejandro Cassis, Nick Fischer, Marvin Künnemann
2021	J	`jnl`	Fine-Grained Completeness for Optimization in P. CoRR Karl Bringmann, Alejandro Cassis, Nick Fischer, Marvin Künnemann
2021	C	`conf`	Fine-Grained Complexity Theory: Conditional Lower Bounds for Computational Geometry. CiE Karl Bringmann
2021	J	`jnl`	Fine-Grained Complexity Theory: Conditional Lower Bounds for Computational Geometry. CoRR Karl Bringmann
2021	A*	`conf`	On Near-Linear-Time Algorithms for Dense Subset Sum. SODA Karl Bringmann, Philip Wellnitz
2021	J	`jnl`	Sparse Fourier Transform by traversing Cooley-Tukey FFT computation graphs. CoRR Karl Bringmann, Michael Kapralov, Mikhail Makarov, Vasileios Nakos, Amir Yagudin, Amir Zandieh
2021	J	`jnl`	Sparse Nonnegative Convolution Is Equivalent to Dense Nonnegative Convolution. CoRR Karl Bringmann, Nick Fischer, Vasileios Nakos
2021	A*	`conf`	Sparse nonnegative convolution is equivalent to dense nonnegative convolution. STOC Karl Bringmann, Nick Fischer, Vasileios Nakos
2021	J	`jnl`	Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fréchet Distance. CoRR Karl Bringmann, Anne Driemel, André Nusser, Ioannis Psarros
2021	J	`jnl`	Top-k-Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum. CoRR Karl Bringmann, Vasileios Nakos
2021	A*	`conf`	Translating Hausdorff Is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation. SoCG Karl Bringmann, André Nusser
2021	J	`jnl`	Translating Hausdorff is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation. CoRR Karl Bringmann, André Nusser
2021	J	`jnl`	Translating Hausdorff is hard: fine-grained lower bounds for Hausdorff distance under translation. J. Comput. Geom. Karl Bringmann, André Nusser
2021	J	`jnl`	Walking the dog fast in practice: Algorithm engineering of the Fréchet distance. J. Comput. Geom. Karl Bringmann, Marvin Künnemann, André Nusser
2020	J	`jnl`	Fast and Simple Modular Subset Sum. CoRR Kyriakos Axiotis, Arturs Backurs, Karl Bringmann, Ce Jin, Vasileios Nakos, Christos Tzamos, Hongxun Wu
2020	A*	`conf`	Faster Minimization of Tardy Processing Time on a Single Machine. ICALP Karl Bringmann, Nick Fischer, Danny Hermelin, Dvir Shabtay, Philip Wellnitz
2020	J	`jnl`	Faster Minimization of Tardy Processing Time on a Single Machine. CoRR Karl Bringmann, Nick Fischer, Danny Hermelin, Dvir Shabtay, Philip Wellnitz
2020	A*	`conf`	Impossibility Results for Grammar-Compressed Linear Algebra. NeurIPS Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann
2020	J	`jnl`	Impossibility Results for Grammar-Compressed Linear Algebra. CoRR Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann
2020	J	`jnl`	Multivariate Analysis of Orthogonal Range Searching and Graph Distances. Algorithmica Karl Bringmann, Thore Husfeldt, Måns Magnusson
2020	J	`jnl`	On Near-Linear-Time Algorithms for Dense Subset Sum. CoRR Karl Bringmann, Philip Wellnitz
2020	J	`jnl`	Polyline simplification has cubic complexity. J. Comput. Geom. Karl Bringmann, Bhaskar Ray Chaudhury
2020	A*	`conf`	Scheduling Lower Bounds via AND Subset Sum. ICALP Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay
2020	J	`jnl`	Scheduling Lower Bounds via AND Subset Sum. CoRR Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay
2020	A*	`conf`	Top-k-convolution and the quest for near-linear output-sensitive subset sum. STOC Karl Bringmann, Vasileios Nakos
2020	J	`jnl`	Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (Unless APSP Can). ACM Trans. Algorithms Karl Bringmann, Pawel Gawrychowski, Shay Mozes, Oren Weimann
2020	A	`conf`	When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance Under Translation. ESA Karl Bringmann, Marvin Künnemann, André Nusser
2020	J	`jnl`	When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation. CoRR Karl Bringmann, Marvin Künnemann, André Nusser
2019	A	`conf`	A Fine-Grained Analogue of Schaefer's Theorem in P: Dichotomy of Exists^k-Forall-Quantified First-Order Graph Properties. CCC Karl Bringmann, Nick Fischer, Marvin Künnemann
2019	A*	`conf`	A PTAS for ℓp-Low Rank Approximation. SODA Frank Ban, Vijay Bhattiprolu, Karl Bringmann, Pavel Kolev, Euiwoong Lee, David P. Woodruff
2019	J	`jnl`	Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max. CoRR Karl Bringmann, Marvin Künnemann, Karol Wegrzycki
2019	A*	`conf`	Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max. STOC Karl Bringmann, Marvin Künnemann, Karol Wegrzycki
2019	J	`jnl`	Approximating Subset Sum is equivalent to Min-Plus-Convolution. CoRR Karl Bringmann
2019	A*	`conf`	Few Matches or Almost Periodicity: Faster Pattern Matching with Mismatches in Compressed Texts. SODA Karl Bringmann, Marvin Künnemann, Philip Wellnitz
2019	A	`conf`	Fine-Grained Complexity Theory (Tutorial). STACS Karl Bringmann
2019	A*	`conf`	Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability. SODA Karl Bringmann, Marvin Künnemann, André Nusser
2019	J	`jnl`	Geometric inhomogeneous random graphs. Theor. Comput. Sci. Karl Bringmann, Ralph Keusch, Johannes Lengler
2019	A	`conf`	On Geometric Set Cover for Orthants. ESA Karl Bringmann, Sándor Kisfaludi-Bak, Michal Pilipczuk, Erik Jan van Leeuwen
2019	A*	`conf`	Polyline Simplification has Cubic Complexity. SoCG Karl Bringmann, Bhaskar Ray Chaudhury
2019	A*	`conf`	SETH-Based Lower Bounds for Subset Sum and Bicriteria Path. SODA Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay
2019	J	`jnl`	Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product. SIAM J. Comput. Karl Bringmann, Fabrizio Grandoni, Barna Saha, Virginia Vassilevska Williams
2019	A*	`conf`	Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance. SoCG Karl Bringmann, Marvin Künnemann, André Nusser
2019	J	`jnl`	Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance. CoRR Karl Bringmann, Marvin Künnemann, André Nusser
2018	J	`jnl`	A PTAS for 𝓁 CoRR Frank Ban, Vijay Bhattiprolu, Karl Bringmann, Pavel Kolev, Euiwoong Lee, David P. Woodruff
2018	J	`jnl`	A fast implementation of near neighbors queries for Fréchet distance (GIS Cup). CoRR Julian Baldus, Karl Bringmann
2018	J	`jnl`	A note on hardness of diameter approximation. Inf. Process. Lett. Karl Bringmann, Sebastian Krinninger
2018	J	`jnl`	Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars. CoRR Karl Bringmann, Philip Wellnitz
2018	J	`jnl`	De-anonymization of Heterogeneous Random Graphs in Quasilinear Time. Algorithmica Karl Bringmann, Tobias Friedrich, Anton Krohmer
2018	J	`jnl`	Fast Fencing. CoRR Mikkel Abrahamsen, Anna Adamaszek, Karl Bringmann, Vincent Cohen-Addad, Mehran Mehr, Eva Rotenberg, Alan Roytman, Mikkel Thorup
2018	A*	`conf`	Fast fencing. STOC Mikkel Abrahamsen, Anna Adamaszek, Karl Bringmann, Vincent Cohen-Addad, Mehran Mehr, Eva Rotenberg, Alan Roytman, Mikkel Thorup
2018	J	`jnl`	Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-And-Solve. CoRR Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann
2018	J	`jnl`	Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability. CoRR Karl Bringmann, Marvin Künnemann, André Nusser
2018	J	`jnl`	Maximum Volume Subset Selection for Anchored Boxes. CoRR Karl Bringmann, Sergio Cabello, Michael T. M. Emmerich
2018	J	`jnl`	More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture. CoRR Amir Abboud, Karl Bringmann, Holger Dell, Jesper Nederlof
2018	A*	`conf`	More consequences of falsifying SETH and the orthogonal vectors conjecture. STOC Amir Abboud, Karl Bringmann, Holger Dell, Jesper Nederlof
2018	J	`jnl`	Multivariate Analysis of Orthogonal Range Searching and Graph Distances Parameterized by Treewidth. CoRR Karl Bringmann, Thore Husfeldt, Måns Magnusson
2018	B	`conf`	Multivariate Analysis of Orthogonal Range Searching and Graph Distances. IPEC Karl Bringmann, Thore Husfeldt, Måns Magnusson
2018	A*	`conf`	Multivariate Fine-Grained Complexity of Longest Common Subsequence. SODA Karl Bringmann, Marvin Künnemann
2018	J	`jnl`	Multivariate Fine-Grained Complexity of Longest Common Subsequence. CoRR Karl Bringmann, Marvin Künnemann
2018	J	`jnl`	On Algebraic Branching Programs of Small Width. J. ACM Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam
2018	J	`jnl`	Polyline Simplification has Cubic Complexity. CoRR Karl Bringmann, Bhaskar Ray Chaudhury
2018	—	`conf`	Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS. FSTTCS Karl Bringmann, Bhaskar Ray Chaudhury
2018	J	`jnl`	Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS. CoRR Karl Bringmann, Bhaskar Ray Chaudhury
2018	A*	`conf`	Tighter Connections Between Formula-SAT and Shaving Logs. ICALP Amir Abboud, Karl Bringmann
2018	J	`jnl`	Tighter Connections Between Formula-SAT and Shaving Logs. CoRR Amir Abboud, Karl Bringmann
2018	A*	`conf`	Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can). SODA Karl Bringmann, Pawel Gawrychowski, Shay Mozes, Oren Weimann
2017	A*	`conf`	A Dichotomy for Regular Expression Membership Testing. FOCS Karl Bringmann, Allan Grønlund, Kasper Green Larsen
2017	A*	`conf`	A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum. SODA Karl Bringmann
2017	J	`jnl`	A Note on Hardness of Diameter Approximation. CoRR Karl Bringmann, Sebastian Krinninger
2017	—	`conf`	A fast implementation of near neighbors queries for Fréchet distance (GIS Cup). SIGSPATIAL/GIS Julian Baldus, Karl Bringmann
2017	—	`conf`	Approximation Algorithms for l NIPS Karl Bringmann, Pavel Kolev, David P. Woodruff
2017	J	`jnl`	Approximation Algorithms for ࡁ CoRR Karl Bringmann, Pavel Kolev, David P. Woodruff
2017	A	`conf`	Brief Announcement: A Note on Hardness of Diameter Approximation. DISC Karl Bringmann, Sebastian Krinninger
2017	B	`conf`	Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars. CPM Karl Bringmann, Philip Wellnitz
2017	J	`jnl`	Efficient Sampling Methods for Discrete Distributions. Algorithmica Karl Bringmann, Konstantinos Panagiotou
2017	A*	`conf`	Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve. FOCS Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann
2017	A*	`conf`	Greedy Routing and the Algorithmic Small-World Phenomenon. PODC Karl Bringmann, Ralph Keusch, Johannes Lengler, Yannic Maus, Anisur Rahaman Molla
2017	A*	`conf`	Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs. ICALP Karl Bringmann, Thomas Dueholm Hansen, Sebastian Krinninger
2017	J	`jnl`	Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs. CoRR Karl Bringmann, Thomas Dueholm Hansen, Sebastian Krinninger
2017	J	`jnl`	Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds. Int. J. Comput. Geom. Appl. Karl Bringmann, Marvin Künnemann
2017	A*	`conf`	Maximum Volume Subset Selection for Anchored Boxes. SoCG Karl Bringmann, Sergio Cabello, Michael T. M. Emmerich
2017	J	`jnl`	Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines. Algorithmica S. Anand, Karl Bringmann, Tobias Friedrich, Naveen Garg, Amit Kumar
2017	A	`conf`	On Algebraic Branching Programs of Small Width. CCC Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam
2017	J	`jnl`	On algebraic branching programs of small width. CoRR Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam
2017	J	`jnl`	On algebraic branching programs of small width. Electron. Colloquium Comput. Complex. Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam
2017	J	`jnl`	SETH-Based Lower Bounds for Subset Sum and Bicriteria Path. CoRR Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay
2017	A	`conf`	Sampling Geometric Inhomogeneous Random Graphs in Linear Time. ESA Karl Bringmann, Ralph Keusch, Johannes Lengler
2017	J	`jnl`	Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can). CoRR Karl Bringmann, Pawel Gawrychowski, Shay Mozes, Oren Weimann
2017	J	`jnl`	Truly Sub-cubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product. CoRR Karl Bringmann, Fabrizio Grandoni, Barna Saha, Virginia Vassilevska Williams
2016	J	`jnl`	A Dichotomy for Regular Expression Membership Testing. CoRR Karl Bringmann, Allan Grønlund, Kasper Green Larsen
2016	J	`jnl`	A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum. CoRR Karl Bringmann
2016	J	`jnl`	Approximability of the discrete Fréchet distance. J. Comput. Geom. Karl Bringmann, Wolfgang Mulzer
2016	J	`jnl`	Average Distance in a General Class of Scale-Free Networks with Underlying Geometry. CoRR Karl Bringmann, Ralph Keusch, Johannes Lengler
2016	J	`jnl`	Balls into bins via local search: Cover time and maximum load. Random Struct. Algorithms Karl Bringmann, Thomas Sauerwald, Alexandre Stauffer, He Sun
2016	J	`jnl`	Greedy Routing and the Algorithmic Small-World Phenomenom. CoRR Karl Bringmann, Ralph Keusch, Johannes Lengler, Yannic Maus, Anisur Rahaman Molla
2016	A	`conf`	Hitting Set for Hypergraphs of Low VC-dimension. ESA Karl Bringmann, László Kozma, Shay Moran, N. S. Narayanaswamy
2016	J	`jnl`	Parameterized complexity dichotomy for Steiner Multicut. J. Comput. Syst. Sci. Karl Bringmann, Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen
2016	A*	`conf`	Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product. FOCS Karl Bringmann, Fabrizio Grandoni, Barna Saha, Virginia Vassilevska Williams
2015	A*	`conf`	Approximability of the Discrete Fréchet Distance. SoCG Karl Bringmann, Wolfgang Mulzer
2015	J	`jnl`	Counting Triangulations and Other Crossing-Free Structures via Onion Layers. Discret. Comput. Geom. Victor Alvarez, Karl Bringmann, Radu Curticapean, Saurabh Ray
2015	J	`jnl`	Counting triangulations and other crossing-free structures approximately. Comput. Geom. Victor Alvarez, Karl Bringmann, Saurabh Ray, Raimund Seidel
2015	B	`conf`	Efficient computation of two-dimensional solution sets maximizing the epsilon-indicator. CEC Karl Bringmann, Tobias Friedrich, Patrick Klitzke
2015	J	`jnl`	Efficient optimization of many objectives by approximation-guided evolution. Eur. J. Oper. Res. Markus Wagner, Karl Bringmann, Tobias Friedrich, Frank Neumann
2015	J	`jnl`	Geometric Inhomogeneous Random Graphs. CoRR Karl Bringmann, Ralph Keusch, Johannes Lengler
2015	J	`jnl`	Hitting Set in hypergraphs of low VC-dimension. CoRR Karl Bringmann, László Kozma, Shay Moran, N. S. Narayanaswamy
2015	B	`conf`	Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds. ISAAC Karl Bringmann, Marvin Künnemann
2015	J	`jnl`	Online Checkpointing with Improved Worst-Case Guarantees. INFORMS J. Comput. Karl Bringmann, Benjamin Doerr, Adrian Neumann, Jakub Sliacan
2015	A	`conf`	Parameterized Complexity Dichotomy for Steiner Multicut. STACS Karl Bringmann, Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen
2015	A*	`conf`	Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping. FOCS Karl Bringmann, Marvin Künnemann
2015	J	`jnl`	Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping. CoRR Karl Bringmann, Marvin Künnemann
2015	J	`jnl`	Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems. Algorithmica Karl Bringmann, Christian Engels, Bodo Manthey, B. V. Raghavendra Rao
2015	J	`jnl`	Sampling from Discrete Distributions and Computing Frechet Distances. Bull. EATCS Karl Bringmann
2015	—	`—`	Sampling from discrete distributions and computing Fréchet distances. Karl Bringmann
2015	—	`conf`	Ultra-Fast Load Balancing on Scale-Free Networks. ICALP (2) Karl Bringmann, Tobias Friedrich, Martin Hoefer, Ralf Rothenberger, Thomas Sauerwald
2014	A	`conf`	Balls into bins via local search: cover time and maximum load. STACS Karl Bringmann, Thomas Sauerwald, Alexandre Stauffer, He Sun
2014	J	`jnl`	Convergence of Hypervolume-Based Archiving Algorithms. IEEE Trans. Evol. Comput. Karl Bringmann, Tobias Friedrich
2014	J	`jnl`	Counting Triangulations and other Crossing-Free Structures Approximately. CoRR Victor Alvarez, Karl Bringmann, Saurabh Ray, Raimund Seidel
2014	A	`conf`	De-anonymization of Heterogeneous Random Graphs in Quasilinear Time. ESA Karl Bringmann, Tobias Friedrich, Anton Krohmer
2014	A	`conf`	Generic Postprocessing via Subset Selection for Hypervolume and Epsilon-Indicator. PPSN Karl Bringmann, Tobias Friedrich, Patrick Klitzke
2014	—	`ch.`	Generierung diskreter Zufallsvariablen und Berechnung der Fréchetdistanz. Ausgezeichnete Informatikdissertationen Karl Bringmann
2014	J	`jnl`	Improved approximation for Fréchet distance on c-packed curves matching conditional lower bounds. CoRR Karl Bringmann, Marvin Künnemann
2014	—	`conf`	Internal DLA: Efficient Simulation of a Physical Growth Model - (Extended Abstract). ICALP (1) Karl Bringmann, Fabian Kuhn, Konstantinos Panagiotou, Ueli Peter, Henning Thomas
2014	J	`jnl`	Parameterized Complexity Dichotomy for Steiner Multicut. CoRR Karl Bringmann, Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen
2014	A	`conf`	Two-dimensional subset selection for hypervolume and epsilon-indicator. GECCO Karl Bringmann, Tobias Friedrich, Patrick Klitzke
2014	A*	`conf`	Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails. FOCS Karl Bringmann
2014	J	`jnl`	Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails. CoRR Karl Bringmann
2013	J	`jnl`	A Simple Sweep Line Algorithm for Counting Triangulations and Pseudo-triangulations. CoRR Victor Alvarez, Karl Bringmann, Saurabh Ray
2013	J	`jnl`	Approximation quality of the hypervolume indicator. Artif. Intell. Karl Bringmann, Tobias Friedrich
2013	J	`jnl`	Balls into bins via local search: cover time and maximum load. CoRR Karl Bringmann, Thomas Sauerwald, Alexandre Stauffer, He Sun
2013	J	`jnl`	Bringing Order to Special Cases of Klee's Measure Problem CoRR Karl Bringmann
2013	B	`conf`	Bringing Order to Special Cases of Klee's Measure Problem. MFCS Karl Bringmann
2013	—	`conf`	Counting Triangulations Approximately. CCCG Victor Alvarez, Karl Bringmann, Saurabh Ray, Raimund Seidel
2013	J	`jnl`	Counting Triangulations and other Crossing-free Structures via Onion Layers. CoRR Victor Alvarez, Karl Bringmann, Radu Curticapean, Saurabh Ray
2013	—	`conf`	Exact and Efficient Generation of Geometric Random Variates and Random Graphs. ICALP (1) Karl Bringmann, Tobias Friedrich
2013	—	`conf`	Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines. ICALP (1) S. Anand, Karl Bringmann, Tobias Friedrich, Naveen Garg, Amit Kumar
2013	J	`jnl`	Online Checkpointing with Improved Worst-Case Guarantees CoRR Karl Bringmann, Benjamin Doerr, Adrian Neumann, Jakub Sliacan
2013	—	`conf`	Online Checkpointing with Improved Worst-Case Guarantees. ICALP (1) Karl Bringmann, Benjamin Doerr, Adrian Neumann, Jakub Sliacan
2013	C	`conf`	Online checkpointing with improved worst-case guarantees. CTW Karl Bringmann, Benjamin Doerr, Adrian Neumann, Jakub Sliacan
2013	A	`conf`	Parameterized average-case complexity of the hypervolume indicator. GECCO Karl Bringmann, Tobias Friedrich
2013	J	`jnl`	Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems. CoRR Karl Bringmann, Christian Engels, Bodo Manthey, B. V. Raghavendra Rao
2013	B	`conf`	Random Shortest Paths: Non-euclidean Instances for Metric Optimization Problems. MFCS Karl Bringmann, Christian Engels, Bodo Manthey, B. V. Raghavendra Rao
2013	J	`jnl`	Speeding up many-objective optimization by Monte Carlo approximations. Artif. Intell. Karl Bringmann, Tobias Friedrich, Christian Igel, Thomas Voß
2013	A*	`conf`	Succinct sampling from discrete distributions. STOC Karl Bringmann, Kasper Green Larsen
2012	J	`jnl`	An improved algorithm for Kleeʼs measure problem on fat boxes. Comput. Geom. Karl Bringmann
2012	J	`jnl`	Approximating the least hypervolume contributor: NP-hard in general, but fast in practice. Theor. Comput. Sci. Karl Bringmann, Tobias Friedrich
2012	A	`conf`	Convergence of hypervolume-based archiving algorithms ii: competitiveness. GECCO Karl Bringmann, Tobias Friedrich
2012	—	`conf`	Counting crossing-free structures. SCG Victor Alvarez, Karl Bringmann, Radu Curticapean, Saurabh Ray
2012	—	`conf`	Efficient Sampling Methods for Discrete Distributions. ICALP (1) Karl Bringmann, Konstantinos Panagiotou
2012	J	`jnl`	Remarks on Category-Based Routing in Social Networks CoRR Karl Bringmann, Kurt Mehlhorn, Adrian Neumann
2011	A*	`conf`	Approximation-Guided Evolutionary Multi-Objective Optimization. IJCAI Karl Bringmann, Tobias Friedrich, Frank Neumann, Markus Wagner
2011	A	`conf`	Convergence of hypervolume-based archiving algorithms I: effectiveness. GECCO Karl Bringmann, Tobias Friedrich
2011	A	`conf`	The logarithmic hypervolume indicator. FOGA Tobias Friedrich, Karl Bringmann, Thomas Voß, Christian Igel
2010	J	`jnl`	An Efficient Algorithm for Computing Hypervolume Contributions. Evol. Comput. Karl Bringmann, Tobias Friedrich
2010	J	`jnl`	Approximating the volume of unions and intersections of high-dimensional geometric objects. Comput. Geom. Karl Bringmann, Tobias Friedrich
2010	—	`conf`	Klee's measure problem on fat boxes in time PARTIAL DIFFERENTIAL ( SCG Karl Bringmann
2010	—	`conf`	Scaling up indicator-based MOEAs by approximating the least hypervolume contributor: a preliminary study. GECCO (Companion) Thomas Voß, Tobias Friedrich, Karl Bringmann, Christian Igel
2010	A	`conf`	The maximum hypervolume set yields near-optimal approximation. GECCO Karl Bringmann, Tobias Friedrich
2010	—	`conf`	Tight Bounds for the Approximation Ratio of the Hypervolume Indicator. PPSN (1) Karl Bringmann, Tobias Friedrich
2009	C	`conf`	Approximating the Least Hypervolume Contributor: NP-Hard in General, But Fast in Practice. EMO Karl Bringmann, Tobias Friedrich
2009	A	`conf`	Don't be greedy when calculating hypervolume contributions. FOGA Karl Bringmann, Tobias Friedrich
2008	B	`conf`	Approximating the Volume of Unions and Intersections of High-Dimensional Geometric Objects. ISAAC Karl Bringmann, Tobias Friedrich
2008	J	`jnl`	Approximating the least hypervolume contributor: NP-hard in general, but fast in practice CoRR Karl Bringmann, Tobias Friedrich
2008	J	`jnl`	Approximating the volume of unions and intersections of high-dimensional geometric objects CoRR Karl Bringmann, Tobias Friedrich