Stop the war!Остановите войну!
for scientists:
Google
Google Scholar
Semantic Scholar
IA 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
2020 – today
- 2022
[j33]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)- [j32]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) - [j31]Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay:
Scheduling lower bounds via AND subset sum. J. Comput. Syst. Sci. 127: 29-40 (2022) - [j30]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) - [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 - [e1]Karl Bringmann, Timothy 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] - [i71]Karl Bringmann, Nofar Carmeli, Stefan Mengel:
Tight Fine-Grained Bounds for Direct Access on Join Queries. CoRR abs/2201.02401 (2022) - [i70]Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos:
Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime. CoRR abs/2202.08066 (2022) - [i69]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) - [i68]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) - [i67]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) - [i66]Karl Bringmann, Alejandro Cassis, Nick Fischer, Marvin Künnemann:
A Structural Investigation of the Approximability of Polynomial-Time Problems. CoRR abs/2204.11681 (2022) - [i65]Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos:
Improved Sublinear-Time Edit Distance for Preprocessed Strings. CoRR abs/2204.14137 (2022) - [i64]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) - [i63]Karl Bringmann, Alejandro Cassis:
Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution. CoRR abs/2205.08493 (2022) - 2021
- [j29]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) - [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) - [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 - [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
- [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) - [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 - [i51]Karl Bringmann, Nick Fischer, Danny Hermelin, Dvir Shabtay, Philip Wellnitz:
Faster Minimization of Tardy Processing\newline 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)
2010 – 2019
- 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) - [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. Computational Complexity Conference 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, Philip Wellnitz, Marvin Künnemann:
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 - [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
- [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) - [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 - [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
- [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) - [c47]Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam:
On Algebraic Branching Programs of Small Width. Computational Complexity Conference 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 - [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. 24: 34 (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)