default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDKarl Bringmann
Person information
- affiliation: Max Planck Institute for Informatics, Saarbrücken, Germany
- affiliation: Saarland University, Department of Computer Science, Germany
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
Books and Theses
- 2015
[b1]Karl Bringmann:
Sampling from discrete distributions and computing Fréchet distances. Saarland University, 2015
Journal Articles
- 2023
- [j36]Karl Bringmann
, Vincent Cohen-Addad, Debarati Das:
A Linear-Time n0.4-Approximation for Longest Common Subsequence. ACM Trans. Algorithms 19(1): 9:1-9:24 (2023) - 2022
- [j35]Karl Bringmann, Nick Fischer, Danny Hermelin, Dvir Shabtay, Philip Wellnitz:
Faster Minimization of Tardy Processing Time on a Single Machine. Algorithmica 84(5): 1341-1356 (2022) - [j34]Karl Bringmann, Ralph Keusch, Johannes Lengler, Yannic Maus, Anisur Rahaman Molla:
Greedy routing and the algorithmic small-world phenomenon. J. Comput. Syst. Sci. 125: 59-105 (2022) - [j33]Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay:
Scheduling lower bounds via AND subset sum. J. Comput. Syst. Sci. 127: 29-40 (2022) - [j32]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. J. Comput. Geom. 14(2): 83-107 (2022) - [j31]Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay:
SETH-based Lower Bounds for Subset Sum and Bicriteria Path. ACM Trans. Algorithms 18(1): 6:1-6:22 (2022) - 2021
- [j30]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): 70-108 (2021) - [j29]Karl Bringmann, André Nusser:
Translating Hausdorff is hard: fine-grained lower bounds for Hausdorff distance under translation. J. Comput. Geom. 13(2): 30-50 (2021) - [j28]Karl Bringmann, Marvin Künnemann, André Nusser:
Discrete Fréchet Distance under Translation: Conditional Hardness and an Improved Algorithm. ACM Trans. Algorithms 17(3): 25:1-25:42 (2021) - 2020
- [j27]Karl Bringmann, Thore Husfeldt, Måns Magnusson:
Multivariate Analysis of Orthogonal Range Searching and Graph Distances. Algorithmica 82(8): 2292-2315 (2020) - [j26]Karl Bringmann, Bhaskar Ray Chaudhury:
Polyline simplification has cubic complexity. J. Comput. Geom. 11(2): 94-130 (2020) - [j25]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): 48:1-48:22 (2020) - 2019
- [j24]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): 481-512 (2019) - [j23]Karl Bringmann, Ralph Keusch, Johannes Lengler:
Geometric inhomogeneous random graphs. Theor. Comput. Sci. 760: 35-54 (2019) - 2018
- [j22]Karl Bringmann, Tobias Friedrich, Anton Krohmer:
De-anonymization of Heterogeneous Random Graphs in Quasilinear Time. Algorithmica 80(11): 3397-3427 (2018) - [j21]Karl Bringmann, Sebastian Krinninger:
A note on hardness of diameter approximation. Inf. Process. Lett. 133: 10-15 (2018) - [j20]Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam:
On Algebraic Branching Programs of Small Width. J. ACM 65(5): 32:1-32:29 (2018) - 2017
- [j19]S. Anand, Karl Bringmann, Tobias Friedrich, Naveen Garg, Amit Kumar:
Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines. Algorithmica 77(2): 515-536 (2017) - [j18]Karl Bringmann, Konstantinos Panagiotou:
Efficient Sampling Methods for Discrete Distributions. Algorithmica 79(2): 484-508 (2017) - [j17]Karl Bringmann, Marvin Künnemann:
Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds. Int. J. Comput. Geom. Appl. 27(1-2): 85-120 (2017) - 2016
- [j16]Karl Bringmann, Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen:
Parameterized complexity dichotomy for Steiner Multicut. J. Comput. Syst. Sci. 82(6): 1020-1043 (2016) - [j15]Karl Bringmann, Wolfgang Mulzer:
Approximability of the discrete Fréchet distance. J. Comput. Geom. 7(2): 46-76 (2016) - [j14]Karl Bringmann, Thomas Sauerwald, Alexandre Stauffer, He Sun:
Balls into bins via local search: Cover time and maximum load. Random Struct. Algorithms 48(4): 681-702 (2016) - 2015
- [j13]Karl Bringmann, Christian Engels, Bodo Manthey, B. V. Raghavendra Rao:
Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems. Algorithmica 73(1): 42-62 (2015) - [j12]Victor Alvarez, Karl Bringmann, Saurabh Ray, Raimund Seidel:
Counting triangulations and other crossing-free structures approximately. Comput. Geom. 48(5): 386-397 (2015) - [j11]Victor Alvarez, Karl Bringmann, Radu Curticapean, Saurabh Ray:
Counting Triangulations and Other Crossing-Free Structures via Onion Layers. Discret. Comput. Geom. 53(4): 675-690 (2015) - [j10]Karl Bringmann:
Sampling from Discrete Distributions and Computing Frechet Distances. Bull. EATCS 116 (2015) - [j9]Markus Wagner, Karl Bringmann, Tobias Friedrich, Frank Neumann:
Efficient optimization of many objectives by approximation-guided evolution. Eur. J. Oper. Res. 243(2): 465-479 (2015) - [j8]Karl Bringmann, Benjamin Doerr, Adrian Neumann, Jakub Sliacan:
Online Checkpointing with Improved Worst-Case Guarantees. INFORMS J. Comput. 27(3): 478-490 (2015) - 2014
- [j7]Karl Bringmann, Tobias Friedrich:
Convergence of Hypervolume-Based Archiving Algorithms. IEEE Trans. Evol. Comput. 18(5): 643-657 (2014) - 2013
- [j6]Karl Bringmann, Tobias Friedrich:
Approximation quality of the hypervolume indicator. Artif. Intell. 195: 265-290 (2013) - [j5]Karl Bringmann, Tobias Friedrich, Christian Igel, Thomas Voß:
Speeding up many-objective optimization by Monte Carlo approximations. Artif. Intell. 204: 22-29 (2013) - 2012
- [j4]Karl Bringmann:
An improved algorithm for Kleeʼs measure problem on fat boxes. Comput. Geom. 45(5-6): 225-233 (2012) - [j3]Karl Bringmann, Tobias Friedrich:
Approximating the least hypervolume contributor: NP-hard in general, but fast in practice. Theor. Comput. Sci. 425: 104-116 (2012) - 2010
- [j2]Karl Bringmann, Tobias Friedrich:
Approximating the volume of unions and intersections of high-dimensional geometric objects. Comput. Geom. 43(6-7): 601-610 (2010) - [j1]Karl Bringmann, Tobias Friedrich:
An Efficient Algorithm for Computing Hypervolume Contributions. Evol. Comput. 18(3): 383-402 (2010)
Conference and Workshop Papers
- 2024
- [c103]Karl Bringmann, Frank Staals, Karol Wegrzycki, Geert van Wordragen:
Fine-Grained Complexity of Earth Mover's Distance Under Translation. SoCG 2024: 25:1-25:17 - [c102]Karl Bringmann, Anita Dürr, Adam Polak:
Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing. ESA 2024: 33:1-33:15 - [c101]Karl Bringmann, Ahmed Ghazy, Marvin Künnemann:
Exploring the Approximability Landscape of 3SUM. ESA 2024: 34:1-34:15 - [c100]Karl Bringmann, Allan Grønlund, Marvin Künnemann, Kasper Green Larsen:
The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds. ITCS 2024: 22:1-22:25 - [c99]Karl Bringmann, Nick Fischer, Ivor van der Hoog, Evangelos Kipouridis, Tomasz Kociumaka, Eva Rotenberg:
Dynamic Dynamic Time Warping. SODA 2024: 208-242 - [c98]Karl Bringmann:
Approximating Subset Sum Ratio faster than Subset Sum. SODA 2024: 1260-1277 - [c97]Karl Bringmann, Alejandro Cassis, Nick Fischer, Tomasz Kociumaka:
Faster Sublinear-Time Edit Distance. SODA 2024: 3274-3301 - [c96]Amir Abboud, Karl Bringmann, Nick Fischer, Marvin Künnemann:
The Time Complexity of Fully Sparse Matrix Multiplication. SODA 2024: 4670-4703 - [c95]Karl Bringmann:
Knapsack with Small Items in Near-Quadratic Time. STOC 2024: 259-270 - 2023
- [c94]Karl Bringmann, Alejandro Cassis:
Faster 0-1-Knapsack via Near-Convex Min-Plus-Convolution. ESA 2023: 24:1-24:16 - [c93]Karl Bringmann, Alejandro Cassis, Nick Fischer:
Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster! FOCS 2023: 515-538 - [c92]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: 4768-4845 - [c91]Amir Abboud, Karl Bringmann, Nick Fischer:
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics. STOC 2023: 391-404 - 2022
- [c90]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: 12:1-12:16 - [c89]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: 20:1-20:17 - [c88]Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, André Nusser, Zahra Parsaeian:
Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs. SoCG 2022: 21:1-21:16 - [c87]Karl Bringmann, Alejandro Cassis, Nick Fischer, Marvin Künnemann:
A Structural Investigation of the Approximability of Polynomial-Time Problems. ICALP 2022: 30:1-30:20 - [c86]Karl Bringmann, Alejandro Cassis:
Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution. ICALP 2022: 31:1-31:21 - [c85]Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos:
Improved Sublinear-Time Edit Distance for Preprocessed Strings. ICALP 2022: 32:1-32:20 - [c84]Karl Bringmann, Nofar Carmeli, Stefan Mengel:
Tight Fine-Grained Bounds for Direct Access on Join Queries. PODS 2022: 427-436 - [c83]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: 517-550 - [c82]Karl Bringmann, Nick Fischer, Vasileios Nakos:
Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution. SODA 2022: 3069-3090 - [c81]Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos:
Almost-optimal sublinear-time edit distance in the low distance regime. STOC 2022: 1102-1115 - [c80]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: 1487-1500 - 2021
- [c79]Karl Bringmann, Alejandro Cassis, Nick Fischer, Marvin Künnemann:
Fine-Grained Completeness for Optimization in P. APPROX-RANDOM 2021: 9:1-9:22 - [c78]Karl Bringmann:
Fine-Grained Complexity Theory: Conditional Lower Bounds for Computational Geometry. CiE 2021: 60-70 - [c77]Karl Bringmann, André Nusser:
Translating Hausdorff Is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation. SoCG 2021: 18:1-18:17 - [c76]Karl Bringmann, Debarati Das:
A Linear-Time n0.4-Approximation for Longest Common Subsequence. ICALP 2021: 39:1-39:20 - [c75]Karl Bringmann, Jasper Slusallek:
Current Algorithms for Detecting Subgraphs of Bounded Treewidth Are Probably Optimal. ICALP 2021: 40:1-40:16 - [c74]Karl Bringmann, Vasileios Nakos:
Fast n-Fold Boolean Convolution via Additive Combinatorics. ICALP 2021: 41:1-41:17 - [c73]Karl Bringmann, Philip Wellnitz:
On Near-Linear-Time Algorithms for Dense Subset Sum. SODA 2021: 1777-1796 - [c72]Karl Bringmann, Vasileios Nakos:
A Fine-Grained Perspective on Approximating Subset Sum and Partition. SODA 2021: 1797-1815 - [c71]Kyriakos Axiotis, Arturs Backurs, Karl Bringmann, Ce Jin, Vasileios Nakos, Christos Tzamos, Hongxun Wu:
Fast and Simple Modular Subset Sum. SOSA 2021: 57-67 - [c70]Karl Bringmann, Nick Fischer, Vasileios Nakos:
Sparse nonnegative convolution is equivalent to dense nonnegative convolution. STOC 2021: 1711-1724 - 2020
- [c69]Karl Bringmann, Marvin Künnemann, André Nusser:
When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance Under Translation. ESA 2020: 25:1-25:17 - [c68]Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay:
Scheduling Lower Bounds via AND Subset Sum. ICALP 2020: 4:1-4:15 - [c67]Karl Bringmann, Nick Fischer, Danny Hermelin, Dvir Shabtay, Philip Wellnitz:
Faster Minimization of Tardy Processing Time on a Single Machine. ICALP 2020: 19:1-19:12 - [c66]Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann:
Impossibility Results for Grammar-Compressed Linear Algebra. NeurIPS 2020 - [c65]Karl Bringmann, Vasileios Nakos:
Top-k-convolution and the quest for near-linear output-sensitive subset sum. STOC 2020: 982-995 - 2019
- [c64]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. CCC 2019: 31:1-31:27 - [c63]Karl Bringmann, Marvin Künnemann, André Nusser:
Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance. SoCG 2019: 17:1-17:21 - [c62]Karl Bringmann, Bhaskar Ray Chaudhury:
Polyline Simplification has Cubic Complexity. SoCG 2019: 18:1-18:16 - [c61]Karl Bringmann, Sándor Kisfaludi-Bak, Michal Pilipczuk, Erik Jan van Leeuwen:
On Geometric Set Cover for Orthants. ESA 2019: 26:1-26:18 - [c60]Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay:
SETH-Based Lower Bounds for Subset Sum and Bicriteria Path. SODA 2019: 41-57 - [c59]Frank Ban, Vijay Bhattiprolu, Karl Bringmann, Pavel Kolev, Euiwoong Lee, David P. Woodruff:
A PTAS for ℓp-Low Rank Approximation. SODA 2019: 747-766 - [c58]Karl Bringmann, Marvin Künnemann, Philip Wellnitz:
Few Matches or Almost Periodicity: Faster Pattern Matching with Mismatches in Compressed Texts. SODA 2019: 1126-1145 - [c57]Karl Bringmann, Marvin Künnemann, André Nusser:
Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability. SODA 2019: 2902-2921 - [c56]Karl Bringmann:
Fine-Grained Complexity Theory (Tutorial). STACS 2019: 4:1-4:7 - [c55]Karl Bringmann, Marvin Künnemann, Karol Wegrzycki:
Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max. STOC 2019: 943-954 - 2018
- [c54]Karl Bringmann, Bhaskar Ray Chaudhury:
Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS. FSTTCS 2018: 40:1-40:16 - [c53]Amir Abboud, Karl Bringmann:
Tighter Connections Between Formula-SAT and Shaving Logs. ICALP 2018: 8:1-8:18 - [c52]Karl Bringmann, Thore Husfeldt, Måns Magnusson:
Multivariate Analysis of Orthogonal Range Searching and Graph Distances. IPEC 2018: 4:1-4:13 - [c51]Karl Bringmann, Pawel Gawrychowski, Shay Mozes, Oren Weimann:
Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can). SODA 2018: 1190-1206 - [c50]Karl Bringmann, Marvin Künnemann:
Multivariate Fine-Grained Complexity of Longest Common Subsequence. SODA 2018: 1216-1235 - [c49]Amir Abboud, Karl Bringmann, Holger Dell, Jesper Nederlof:
More consequences of falsifying SETH and the orthogonal vectors conjecture. STOC 2018: 253-266 - [c48]Mikkel Abrahamsen, Anna Adamaszek, Karl Bringmann, Vincent Cohen-Addad, Mehran Mehr, Eva Rotenberg, Alan Roytman, Mikkel Thorup:
Fast fencing. STOC 2018: 564-573 - 2017
- [c47]Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam:
On Algebraic Branching Programs of Small Width. CCC 2017: 20:1-20:31 - [c46]Karl Bringmann, Sergio Cabello, Michael T. M. Emmerich:
Maximum Volume Subset Selection for Anchored Boxes. SoCG 2017: 22:1-22:15 - [c45]Karl Bringmann, Philip Wellnitz:
Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars. CPM 2017: 12:1-12:14 - [c44]Karl Bringmann, Ralph Keusch, Johannes Lengler:
Sampling Geometric Inhomogeneous Random Graphs in Linear Time. ESA 2017: 20:1-20:15 - [c43]Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann:
Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve. FOCS 2017: 192-203 - [c42]Karl Bringmann, Allan Grønlund, Kasper Green Larsen:
A Dichotomy for Regular Expression Membership Testing. FOCS 2017: 307-318 - [c41]Julian Baldus, Karl Bringmann:
A fast implementation of near neighbors queries for Fréchet distance (GIS Cup). SIGSPATIAL/GIS 2017: 99:1-99:4 - [c40]Karl Bringmann, Thomas Dueholm Hansen, Sebastian Krinninger:
Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs. ICALP 2017: 124:1-124:16 - [c39]Karl Bringmann, Pavel Kolev, David P. Woodruff:
Approximation Algorithms for l0-Low Rank Approximation. NIPS 2017: 6648-6659 - [c38]Karl Bringmann, Ralph Keusch, Johannes Lengler, Yannic Maus, Anisur Rahaman Molla:
Greedy Routing and the Algorithmic Small-World Phenomenon. PODC 2017: 371-380 - [c37]Karl Bringmann:
A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum. SODA 2017: 1073-1084 - [c36]Karl Bringmann, Sebastian Krinninger:
Brief Announcement: A Note on Hardness of Diameter Approximation. DISC 2017: 44:1-44:3 - 2016
- [c35]Karl Bringmann, László Kozma, Shay Moran, N. S. Narayanaswamy:
Hitting Set for Hypergraphs of Low VC-dimension. ESA 2016: 23:1-23:18 - [c34]Karl Bringmann, Fabrizio Grandoni, Barna Saha, Virginia Vassilevska Williams:
Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product. FOCS 2016: 375-384 - 2015
- [c33]Karl Bringmann, Tobias Friedrich, Patrick Klitzke:
Efficient computation of two-dimensional solution sets maximizing the epsilon-indicator. CEC 2015: 970-977 - [c32]Karl Bringmann, Wolfgang Mulzer:
Approximability of the Discrete Fréchet Distance. SoCG 2015: 739-753 - [c31]Karl Bringmann, Marvin Künnemann:
Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping. FOCS 2015: 79-97 - [c30]Karl Bringmann, Tobias Friedrich, Martin Hoefer, Ralf Rothenberger, Thomas Sauerwald:
Ultra-Fast Load Balancing on Scale-Free Networks. ICALP (2) 2015: 516-527 - [c29]Karl Bringmann, Marvin Künnemann:
Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds. ISAAC 2015: 517-528 - [c28]Karl Bringmann, Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen:
Parameterized Complexity Dichotomy for Steiner Multicut. STACS 2015: 157-170 - 2014
- [c27]Karl Bringmann, Tobias Friedrich, Anton Krohmer:
De-anonymization of Heterogeneous Random Graphs in Quasilinear Time. ESA 2014: 197-208 - [c26]Karl Bringmann:
Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails. FOCS 2014: 661-670 - [c25]Karl Bringmann, Tobias Friedrich, Patrick Klitzke:
Two-dimensional subset selection for hypervolume and epsilon-indicator. GECCO 2014: 589-596 - [c24]Karl Bringmann, Fabian Kuhn, Konstantinos Panagiotou, Ueli Peter, Henning Thomas:
Internal DLA: Efficient Simulation of a Physical Growth Model - (Extended Abstract). ICALP (1) 2014: 247-258 - [c23]Karl Bringmann, Tobias Friedrich, Patrick Klitzke:
Generic Postprocessing via Subset Selection for Hypervolume and Epsilon-Indicator. PPSN 2014: 518-527 - [c22]Karl Bringmann, Thomas Sauerwald, Alexandre Stauffer, He Sun:
Balls into bins via local search: cover time and maximum load. STACS 2014: 187-198 - 2013
- [c21]Victor Alvarez, Karl Bringmann, Saurabh Ray, Raimund Seidel:
Counting Triangulations Approximately. CCCG 2013 - [c20]Karl Bringmann, Tobias Friedrich:
Parameterized average-case complexity of the hypervolume indicator. GECCO 2013: 575-582 - [c19]S. Anand, Karl Bringmann, Tobias Friedrich, Naveen Garg, Amit Kumar:
Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines. ICALP (1) 2013: 13-24 - [c18]Karl Bringmann, Benjamin Doerr, Adrian Neumann, Jakub Sliacan:
Online Checkpointing with Improved Worst-Case Guarantees. ICALP (1) 2013: 255-266 - [c17]Karl Bringmann, Tobias Friedrich:
Exact and Efficient Generation of Geometric Random Variates and Random Graphs. ICALP (1) 2013: 267-278 - [c16]Karl Bringmann:
Bringing Order to Special Cases of Klee's Measure Problem. MFCS 2013: 207-218 - [c15]Karl Bringmann, Christian Engels, Bodo Manthey, B. V. Raghavendra Rao:
Random Shortest Paths: Non-euclidean Instances for Metric Optimization Problems. MFCS 2013: 219-230 - [c14]Karl Bringmann, Kasper Green Larsen:
Succinct sampling from discrete distributions. STOC 2013: 775-782 - 2012
- [c13]Victor Alvarez, Karl Bringmann, Radu Curticapean, Saurabh Ray:
Counting crossing-free structures. SCG 2012: 61-68 - [c12]Karl Bringmann, Tobias Friedrich:
Convergence of hypervolume-based archiving algorithms ii: competitiveness. GECCO 2012: 457-464 - [c11]Karl Bringmann, Konstantinos Panagiotou:
Efficient Sampling Methods for Discrete Distributions. ICALP (1) 2012: 133-144 - 2011
- [c10]Tobias Friedrich, Karl Bringmann, Thomas Voß, Christian Igel:
The logarithmic hypervolume indicator. FOGA 2011: 81-92 - [c9]Karl Bringmann, Tobias Friedrich:
Convergence of hypervolume-based archiving algorithms I: effectiveness. GECCO 2011: 745-752 - [c8]Karl Bringmann, Tobias Friedrich, Frank Neumann, Markus Wagner:
Approximation-Guided Evolutionary Multi-Objective Optimization. IJCAI 2011: 1198-1203 - 2010
- [c7]Karl Bringmann:
Klee's measure problem on fat boxes in time PARTIAL DIFFERENTIAL (n(d+2)/3). SCG 2010: 222-229 - [c6]Karl Bringmann, Tobias Friedrich:
The maximum hypervolume set yields near-optimal approximation. GECCO 2010: 511-518 - [c5]Thomas Voß, Tobias Friedrich, Karl Bringmann, Christian Igel:
Scaling up indicator-based MOEAs by approximating the least hypervolume contributor: a preliminary study. GECCO (Companion) 2010: 1975-1978 - [c4]Karl Bringmann, Tobias Friedrich:
Tight Bounds for the Approximation Ratio of the Hypervolume Indicator. PPSN (1) 2010: 607-616 - 2009
- [c3]Karl Bringmann, Tobias Friedrich:
Approximating the Least Hypervolume Contributor: NP-Hard in General, But Fast in Practice. EMO 2009: 6-20 - [c2]Karl Bringmann, Tobias Friedrich:
Don't be greedy when calculating hypervolume contributions. FOGA 2009: 103-112 - 2008
- [c1]Karl Bringmann, Tobias Friedrich:
Approximating the Volume of Unions and Intersections of High-Dimensional Geometric Objects. ISAAC 2008: 436-447
Parts in Books or Collections
- 2014
- [p1]Karl Bringmann:
Generierung diskreter Zufallsvariablen und Berechnung der Fréchetdistanz. Ausgezeichnete Informatikdissertationen 2014: 51-60
Editorship
- 2024
- [e2]Karl Bringmann, Martin Grohe, Gabriele Puppis, Ola Svensson:
51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia. LIPIcs 297, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2024, ISBN 978-3-95977-322-5 [contents] - 2022
- [e1]Karl Bringmann, Timothy M. Chan:
5th Symposium on Simplicity in Algorithms, SOSA@SODA 2022, Virtual Conference, January 10-11, 2022. SIAM 2022, ISBN 978-1-61197-706-6 [contents]
Informal and Other Publications
- 2024
- [i86]Karl Bringmann, Frank Staals, Karol Wegrzycki, Geert van Wordragen:
Fine-Grained Complexity of Earth Mover's Distance under Translation. CoRR abs/2403.04356 (2024) - [i85]Karl Bringmann, Egor Gorbachev:
A Fine-grained Classification of Subquadratic Patterns for Subgraph Listing and Friends. CoRR abs/2404.04369 (2024) - [i84]Karl Bringmann, Anita Dürr, Adam Polak:
Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing. CoRR abs/2404.05681 (2024) - [i83]Karl Bringmann, Kasper Green Larsen, André Nusser, Eva Rotenberg, Yanheng Wang:
Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation. CoRR abs/2410.00996 (2024) - [i82]Karl Bringmann, Nick Fischer, Vasileios Nakos:
Beating Bellman's Algorithm for Subset Sum. CoRR abs/2410.21942 (2024) - 2023
- [i81]Karl Bringmann, Alejandro Cassis, Nick Fischer:
Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster! CoRR abs/2304.05279 (2023) - [i80]Karl Bringmann, Alejandro Cassis:
Faster 0-1-Knapsack via Near-Convex Min-Plus-Convolution. CoRR abs/2305.01593 (2023) - [i79]Karl Bringmann:
Knapsack with Small Items in Near-Quadratic Time. CoRR abs/2308.03075 (2023) - [i78]Amir Abboud, Karl Bringmann, Nick Fischer, Marvin Künnemann:
The Time Complexity of Fully Sparse Matrix Multiplication. CoRR abs/2309.06317 (2023) - [i77]Karl Bringmann:
Approximating Subset Sum Ratio faster than Subset Sum. CoRR abs/2310.07595 (2023) - [i76]Karl Bringmann, Nick Fischer, Ivor van der Hoog, Evangelos Kipouridis, Tomasz Kociumaka, Eva Rotenberg:
Dynamic Dynamic Time Warping. CoRR abs/2310.18128 (2023) - [i75]Karl Bringmann, Allan Grønlund, Marvin Künnemann, Kasper Green Larsen:
The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds. CoRR abs/2311.10204 (2023) - [i74]Karl Bringmann, Alejandro Cassis, Nick Fischer, Tomasz Kociumaka:
Faster Sublinear-Time Edit Distance. CoRR abs/2312.01759 (2023) - 2022
- [i73]Karl Bringmann, Nofar Carmeli, Stefan Mengel:
Tight Fine-Grained Bounds for Direct Access on Join Queries. CoRR abs/2201.02401 (2022) - [i72]Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos:
Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime. CoRR abs/2202.08066 (2022) - [i71]Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, André Nusser, Zahra Parsaeian:
Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs. CoRR abs/2203.03663 (2022) - [i70]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 abs/2203.07898 (2022) - [i69]Amir Abboud, Karl Bringmann, Seri Khoury, Or Zamir:
Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond. CoRR abs/2204.10465 (2022) - [i68]Karl Bringmann, Alejandro Cassis, Nick Fischer, Marvin Künnemann:
A Structural Investigation of the Approximability of Polynomial-Time Problems. CoRR abs/2204.11681 (2022) - [i67]Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos:
Improved Sublinear-Time Edit Distance for Preprocessed Strings. CoRR abs/2204.14137 (2022) - [i66]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 abs/2205.07777 (2022) - [i65]Karl Bringmann, Alejandro Cassis:
Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution. CoRR abs/2205.08493 (2022) - [i64]Karl Bringmann, Nofar Carmeli:
Unbalanced Triangle Detection and Enumeration Hardness for Unions of Conjunctive Queries. CoRR abs/2210.11996 (2022) - [i63]Amir Abboud, Karl Bringmann, Nick Fischer:
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics. CoRR abs/2211.07058 (2022) - 2021
- [i62]Karl Bringmann, André Nusser:
Translating Hausdorff is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation. CoRR abs/2101.07696 (2021) - [i61]Karl Bringmann, Vasileios Nakos:
Fast n-fold Boolean Convolution via Additive Combinatorics. CoRR abs/2105.03968 (2021) - [i60]Karl Bringmann, Jasper Slusallek:
Current Algorithms for Detecting Subgraphs of Bounded Treewidth are Probably Optimal. CoRR abs/2105.05062 (2021) - [i59]Karl Bringmann, Nick Fischer, Vasileios Nakos:
Sparse Nonnegative Convolution Is Equivalent to Dense Nonnegative Convolution. CoRR abs/2105.05984 (2021) - [i58]Karl Bringmann, Vincent Cohen-Addad, Debarati Das:
A Linear-Time n0.4-Approximation for Longest Common Subsequence. CoRR abs/2106.08195 (2021) - [i57]Karl Bringmann, Alejandro Cassis, Nick Fischer, Marvin Künnemann:
Fine-Grained Completeness for Optimization in P. CoRR abs/2107.01721 (2021) - [i56]Karl Bringmann, Michael Kapralov, Mikhail Makarov, Vasileios Nakos, Amir Yagudin, Amir Zandieh:
Sparse Fourier Transform by traversing Cooley-Tukey FFT computation graphs. CoRR abs/2107.07347 (2021) - [i55]Karl Bringmann, Nick Fischer, Vasileios Nakos:
Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution. CoRR abs/2107.07625 (2021) - [i54]Karl Bringmann, Anne Driemel, André Nusser, Ioannis Psarros:
Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fréchet Distance. CoRR abs/2107.07792 (2021) - [i53]Karl Bringmann, Vasileios Nakos:
Top-k-Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum. CoRR abs/2107.13206 (2021) - [i52]Karl Bringmann:
Fine-Grained Complexity Theory: Conditional Lower Bounds for Computational Geometry. CoRR abs/2110.10283 (2021) - 2020
- [i51]Karl Bringmann, Nick Fischer, Danny Hermelin, Dvir Shabtay, Philip Wellnitz:
Faster Minimization of Tardy Processing Time on a Single Machine. CoRR abs/2003.07104 (2020) - [i50]Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay:
Scheduling Lower Bounds via AND Subset Sum. CoRR abs/2003.07113 (2020) - [i49]Karl Bringmann, Marvin Künnemann, André Nusser:
When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation. CoRR abs/2008.07510 (2020) - [i48]Kyriakos Axiotis, Arturs Backurs, Karl Bringmann, Ce Jin, Vasileios Nakos, Christos Tzamos, Hongxun Wu:
Fast and Simple Modular Subset Sum. CoRR abs/2008.10577 (2020) - [i47]Karl Bringmann, Philip Wellnitz:
On Near-Linear-Time Algorithms for Dense Subset Sum. CoRR abs/2010.09096 (2020) - [i46]Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann:
Impossibility Results for Grammar-Compressed Linear Algebra. CoRR abs/2010.14181 (2020) - 2019
- [i45]Karl Bringmann, Marvin Künnemann, André Nusser:
Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance. CoRR abs/1901.01504 (2019) - [i44]Karl Bringmann, Marvin Künnemann, Karol Wegrzycki:
Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max. CoRR abs/1907.11078 (2019) - [i43]Karl Bringmann:
Approximating Subset Sum is equivalent to Min-Plus-Convolution. CoRR abs/1912.12529 (2019) - 2018
- [i42]Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann:
Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-And-Solve. CoRR abs/1803.00796 (2018) - [i41]Karl Bringmann, Philip Wellnitz:
Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars. CoRR abs/1803.00804 (2018) - [i40]Julian Baldus, Karl Bringmann:
A fast implementation of near neighbors queries for Fréchet distance (GIS Cup). CoRR abs/1803.00806 (2018) - [i39]Karl Bringmann, Sergio Cabello, Michael T. M. Emmerich:
Maximum Volume Subset Selection for Anchored Boxes. CoRR abs/1803.00849 (2018) - [i38]Karl Bringmann, Marvin Künnemann:
Multivariate Fine-Grained Complexity of Longest Common Subsequence. CoRR abs/1803.00938 (2018) - [i37]Mikkel Abrahamsen, Anna Adamaszek, Karl Bringmann, Vincent Cohen-Addad, Mehran Mehr, Eva Rotenberg, Alan Roytman, Mikkel Thorup:
Fast Fencing. CoRR abs/1804.00101 (2018) - [i36]Amir Abboud, Karl Bringmann:
Tighter Connections Between Formula-SAT and Shaving Logs. CoRR abs/1804.08978 (2018) - [i35]Karl Bringmann, Thore Husfeldt, Måns Magnusson:
Multivariate Analysis of Orthogonal Range Searching and Graph Distances Parameterized by Treewidth. CoRR abs/1805.07135 (2018) - [i34]Amir Abboud, Karl Bringmann, Holger Dell, Jesper Nederlof:
More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture. CoRR abs/1805.08554 (2018) - [i33]Frank Ban, Vijay Bhattiprolu, Karl Bringmann, Pavel Kolev, Euiwoong Lee, David P. Woodruff:
A PTAS for 𝓁p-Low Rank Approximation. CoRR abs/1807.06101 (2018) - [i32]Karl Bringmann, Bhaskar Ray Chaudhury:
Polyline Simplification has Cubic Complexity. CoRR abs/1810.00621 (2018) - [i31]Karl Bringmann, Bhaskar Ray Chaudhury:
Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS. CoRR abs/1810.01238 (2018) - [i30]Karl Bringmann, Marvin Künnemann, André Nusser:
Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability. CoRR abs/1810.10982 (2018) - 2017
- [i29]Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam:
On algebraic branching programs of small width. CoRR abs/1702.05328 (2017) - [i28]Karl Bringmann, Pawel Gawrychowski, Shay Mozes, Oren Weimann:
Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can). CoRR abs/1703.08940 (2017) - [i27]Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay:
SETH-Based Lower Bounds for Subset Sum and Bicriteria Path. CoRR abs/1704.04546 (2017) - [i26]Karl Bringmann, Thomas Dueholm Hansen, Sebastian Krinninger:
Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs. CoRR abs/1704.08122 (2017) - [i25]Karl Bringmann, Sebastian Krinninger:
A Note on Hardness of Diameter Approximation. CoRR abs/1705.02127 (2017) - [i24]Karl Bringmann, Fabrizio Grandoni, Barna Saha, Virginia Vassilevska Williams:
Truly Sub-cubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product. CoRR abs/1707.05095 (2017) - [i23]Karl Bringmann, Pavel Kolev, David P. Woodruff:
Approximation Algorithms for ࡁ0-Low Rank Approximation. CoRR abs/1710.11253 (2017) - [i22]Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam:
On algebraic branching programs of small width. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [i21]Karl Bringmann, Ralph Keusch, Johannes Lengler:
Average Distance in a General Class of Scale-Free Networks with Underlying Geometry. CoRR abs/1602.05712 (2016) - [i20]Karl Bringmann:
A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum. CoRR abs/1610.04712 (2016) - [i19]Karl Bringmann, Allan Grønlund, Kasper Green Larsen:
A Dichotomy for Regular Expression Membership Testing. CoRR abs/1611.00918 (2016) - [i18]Karl Bringmann, Ralph Keusch, Johannes Lengler, Yannic Maus, Anisur Rahaman Molla:
Greedy Routing and the Algorithmic Small-World Phenomenom. CoRR abs/1612.05539 (2016) - 2015
- [i17]Karl Bringmann, Marvin Künnemann:
Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping. CoRR abs/1502.01063 (2015) - [i16]Karl Bringmann, Ralph Keusch, Johannes Lengler:
Geometric Inhomogeneous Random Graphs. CoRR abs/1511.00576 (2015) - [i15]Karl Bringmann, László Kozma, Shay Moran, N. S. Narayanaswamy:
Hitting Set in hypergraphs of low VC-dimension. CoRR abs/1512.00481 (2015) - 2014
- [i14]Victor Alvarez, Karl Bringmann, Saurabh Ray, Raimund Seidel:
Counting Triangulations and other Crossing-Free Structures Approximately. CoRR abs/1404.0261 (2014) - [i13]Karl Bringmann:
Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails. CoRR abs/1404.1448 (2014) - [i12]Karl Bringmann, Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen:
Parameterized Complexity Dichotomy for Steiner Multicut. CoRR abs/1404.7006 (2014) - [i11]Karl Bringmann, Marvin Künnemann:
Improved approximation for Fréchet distance on c-packed curves matching conditional lower bounds. CoRR abs/1408.1340 (2014) - 2013
- [i10]Karl Bringmann, Benjamin Doerr, Adrian Neumann, Jakub Sliacan:
Online checkpointing with improved worst-case guarantees. CTW 2013: 23-26 - [i9]Karl Bringmann:
Bringing Order to Special Cases of Klee's Measure Problem. CoRR abs/1301.7154 (2013) - [i8]Karl Bringmann, Benjamin Doerr, Adrian Neumann, Jakub Sliacan:
Online Checkpointing with Improved Worst-Case Guarantees. CoRR abs/1302.4216 (2013) - [i7]Karl Bringmann, Christian Engels, Bodo Manthey, B. V. Raghavendra Rao:
Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems. CoRR abs/1306.3030 (2013) - [i6]Karl Bringmann, Thomas Sauerwald, Alexandre Stauffer, He Sun:
Balls into bins via local search: cover time and maximum load. CoRR abs/1310.0801 (2013) - [i5]Victor Alvarez, Karl Bringmann, Saurabh Ray:
A Simple Sweep Line Algorithm for Counting Triangulations and Pseudo-triangulations. CoRR abs/1312.3188 (2013) - [i4]Victor Alvarez, Karl Bringmann, Radu Curticapean, Saurabh Ray:
Counting Triangulations and other Crossing-free Structures via Onion Layers. CoRR abs/1312.4628 (2013) - 2012
- [i3]Karl Bringmann, Kurt Mehlhorn, Adrian Neumann:
Remarks on Category-Based Routing in Social Networks. CoRR abs/1202.2293 (2012) - 2008
- [i2]Karl Bringmann, Tobias Friedrich:
Approximating the volume of unions and intersections of high-dimensional geometric objects. CoRR abs/0809.0835 (2008) - [i1]Karl Bringmann, Tobias Friedrich:
Approximating the least hypervolume contributor: NP-hard in general, but fast in practice. CoRR abs/0812.2636 (2008)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2025-01-13 02:04 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
