vix.ing · top · new · best · stats · spec

Bringmann, Karl

  1. SETH-Based Lower Bounds for Subset Sum and Bicriteria Path
    2017/04/14 by Amir Abboud, Karl Bringmann, Abboud, Amir +5 · 5 citations
    Computer Science · Engineering · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems
  2. A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum
    2016/10/15 by Karl Bringmann, Bringmann, Karl · 4 citations
    Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Algorithms and Data Compression #Limits and Structures in Graph Theory
  3. Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping
    2015/02/03 by Bringmann, Karl, Künnemann, Marvin · 4 citations
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  4. Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless\n APSP can)
    2017/03/27 by Karl Bringmann, Bringmann, Karl, Paweł Gawrychowski +5 · 3 citations
    Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Network Packet Processing and Optimization
  5. Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!
    2023/04/11 by Bringmann, Karl, Cassis, Alejandro, Fischer, Nick · 5 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  6. Impossibility Results for Grammar-Compressed Linear Algebra
    2020/10/27 by Abboud, Amir, Backurs, Arturs, Bringmann, Karl +1 · 3 citations
    #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Machine Learning (cs.LG)
  7. Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails
    2014/04/05 by Karl Bringmann, Bringmann, Karl · 3 citations
    Computer Science · #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #Complexity and Algorithms in Graphs
  8. Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond
    2022/04/22 by Abboud, Amir, Bringmann, Karl, Khoury, Seri +1 · 4 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  9. Truly Sub-cubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product
    2017/07/17 by Bringmann, Karl, Grandoni, Fabrizio, Saha, Barna +1 · 3 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  10. A Dichotomy for Regular Expression Membership Testing
    2016/11/03 by Bringmann, Karl, Grønlund, Allan, Larsen, Kasper Green · 2 citations
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  11. Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs
    2022/03/07 by Bringmann, Karl, Kisfaludi-Bak, Sándor, Künnemann, Marvin +2 · 3 citations
    #Computational Geometry (cs.CG) #FOS: Computer and information sciences
  12. Tight Fine-Grained Bounds for Direct Access on Join Queries
    2022/01/07 by Bringmann, Karl, Carmeli, Nofar, Mengel, Stefan · 3 citations
    #Computational Complexity (cs.CC) #Databases (cs.DB) #FOS: Computer and information sciences
  13. The Time Complexity of Fully Sparse Matrix Multiplication
    2023/09/12 by Abboud, Amir, Bringmann, Karl, Fischer, Nick +1 · 3 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  14. Counting Triangulations and other Crossing-Free Structures Approximately
    2014/04/01 by Alvarez, Victor, Bringmann, Karl, Ray, Saurabh +1 · 1 citation
    #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #I.3.5
  15. Parameterized Complexity Dichotomy for Steiner Multicut
    2014/04/28 by Bringmann, Karl, Hermelin, Danny, Mnich, Matthias +1 · 1 citation
    #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
  16. Improved approximation for Fréchet distance on c-packed curves matching conditional lower bounds
    2014/08/06 by Bringmann, Karl, Künnemann, Marvin · 1 citation
    #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  17. Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance
    2019/01/06 by Karl Bringmann, Marvin Künnemann, Bringmann, Karl +3 · 1 citation
    Computer Science · Social Sciences · #Data Management and Algorithms #Advanced Image and Video Retrieval Techniques #Human Mobility and Location-Based Analysis
  18. Dynamic Dynamic Time Warping
    2023/10/27 by Karl Bringmann, Nick Fischer, Bringmann, Karl +9 · 2 citations
    Computer Science · #Anomaly Detection Techniques and Applications #Computational Geometry (cs.CG) #Data Management and Algorithms #FOS: Computer and information sciences #Time Series Analysis and Forecasting
  19. A Fine-grained Classification of Subquadratic Patterns for Subgraph Listing and Friends
    2024/04/05 by Bringmann, Karl, Gorbachev, Egor · 2 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  20. Current Algorithms for Detecting Subgraphs of Bounded Treewidth are Probably Optimal
    2021/05/11 by Bringmann, Karl, Slusallek, Jasper · 1 citation
    #05C85 #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences
  21. Greedy Routing and the Algorithmic Small-World Phenomenom
    2016/12/16 by Bringmann, Karl, Keusch, Ralph, Lengler, Johannes +2 · 1 citation
    #68R05 #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #G.2.2 #Networking and Internet Architecture (cs.NI) #Social and Information Networks (cs.SI)
  22. Top-k-Convolution and the Quest for Near-Linear Output-Sensitive Subset\n Sum
    2021/07/28 by Karl Bringmann, Vasileios Nakos, Bringmann, Karl +1 · 1 citation
    Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Digital Image Processing Techniques #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Optimization and Search Problems
  23. A Linear-Time n0.4-Approximation for Longest Common Subsequence
    2021/06/15 by Karl Bringmann, Vincent Cohen-Addad, Bringmann, Karl +3 · 1 citation
    Computer Science · #68W25 #68W32 #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #Machine Learning and Algorithms #Optimization and Search Problems
  24. Average Distance in a General Class of Scale-Free Networks with Underlying Geometry
    2016/02/18 by Bringmann, Karl, Keusch, Ralph, Lengler, Johannes · 1 citation
    #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Social and Information Networks (cs.SI)
  25. Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics
    2022/11/14 by Abboud, Amir, Bringmann, Karl, Fischer, Nick · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  26. Fine-Grained Complexity of Earth Mover’s Distance Under Translation
    2024/01/01 by Karl Bringmann, Frank Staals, Bringmann, Karl +6 · 1 citation
    Computer Science · Business, Management and Accounting · #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Facility Location and Emergency Management
  27. Fine-Grained Complexity of Earth Mover's Distance under Translation
    2024/03/07 by Bringmann, Karl, Staals, Frank, Węgrzycki, Karol +1 · 1 citation
    #Computational Geometry (cs.CG) #FOS: Computer and information sciences
  28. Near-Optimal Directed Low-Diameter Decompositions
    2025/02/08 by Bringmann, Karl, Fischer, Nick, Haeupler, Bernhard +1 · 2 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  29. Translating Hausdorff is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation
    2021/01/19 by Bringmann, Karl, Nusser, André · 1 citation
    #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #FOS: Computer and information sciences