Karl Bringmann

According to our database1, Karl Bringmann authored at least 86 papers between 2009 and 2019.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

On csauthors.net:

Bibliography

2019
Geometric inhomogeneous random graphs.
Theor. Comput. Sci., 2019

Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product.
SIAM J. Comput., 2019

Approximating Subset Sum is equivalent to Min-Plus-Convolution.
CoRR, 2019

Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Fine-Grained Complexity Theory (Tutorial).
Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

Few Matches or Almost Periodicity: Faster Pattern Matching with Mismatches in Compressed Texts.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

A PTAS for ℓp-Low Rank Approximation.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

SETH-Based Lower Bounds for Subset Sum and Bicriteria Path.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

On Geometric Set Cover for Orthants.
Proceedings of the 27th Annual European Symposium on Algorithms, 2019

Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance.
Proceedings of the 35th International Symposium on Computational Geometry, 2019

Polyline Simplification has Cubic Complexity.
Proceedings of the 35th International Symposium on Computational Geometry, 2019

A Fine-Grained Analogue of Schaefer's Theorem in P: Dichotomy of Exists^k-Forall-Quantified First-Order Graph Properties.
Proceedings of the 34th Computational Complexity Conference, 2019

2018
On Algebraic Branching Programs of Small Width.
J. ACM, 2018

A note on hardness of diameter approximation.
Inf. Process. Lett., 2018

A PTAS for 𝓁p-Low Rank Approximation.
CoRR, 2018

Multivariate Analysis of Orthogonal Range Searching and Graph Distances Parameterized by Treewidth.
CoRR, 2018

De-anonymization of Heterogeneous Random Graphs in Quasilinear Time.
Algorithmica, 2018

Fast fencing.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

More consequences of falsifying SETH and the orthogonal vectors conjecture.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Multivariate Fine-Grained Complexity of Longest Common Subsequence.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can).
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Multivariate Analysis of Orthogonal Range Searching and Graph Distances.
Proceedings of the 13th International Symposium on Parameterized and Exact Computation, 2018

Tighter Connections Between Formula-SAT and Shaving Logs.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS.
Proceedings of the 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2018

2017
Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds.
Int. J. Comput. Geometry Appl., 2017

Approximation Algorithms for ࡁ0-Low Rank Approximation.
CoRR, 2017

Efficient Sampling Methods for Discrete Distributions.
Algorithmica, 2017

Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines.
Algorithmica, 2017

Brief Announcement: A Note on Hardness of Diameter Approximation.
Proceedings of the 31st International Symposium on Distributed Computing, 2017

A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Greedy Routing and the Algorithmic Small-World Phenomenon.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2017

Approximation Algorithms for l0-Low Rank Approximation.
Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

A fast implementation of near neighbors queries for Fréchet distance (GIS Cup).
Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2017

A Dichotomy for Regular Expression Membership Testing.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Sampling Geometric Inhomogeneous Random Graphs in Linear Time.
Proceedings of the 25th Annual European Symposium on Algorithms, 2017

Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars.
Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching, 2017

Maximum Volume Subset Selection for Anchored Boxes.
Proceedings of the 33rd International Symposium on Computational Geometry, 2017

2016
Balls into bins via local search: Cover time and maximum load.
Random Struct. Algorithms, 2016

Approximability of the discrete Fréchet distance.
JoCG, 2016

Parameterized complexity dichotomy for Steiner Multicut.
J. Comput. Syst. Sci., 2016

Greedy Routing and the Algorithmic Small-World Phenomenom.
CoRR, 2016

Average Distance in a General Class of Scale-Free Networks with Underlying Geometry.
CoRR, 2016

Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product.
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

Hitting Set for Hypergraphs of Low VC-dimension.
Proceedings of the 24th Annual European Symposium on Algorithms, 2016

2015
Sampling from discrete distributions and computing Fréchet distances.
PhD thesis, 2015

Online Checkpointing with Improved Worst-Case Guarantees.
INFORMS Journal on Computing, 2015

Efficient optimization of many objectives by approximation-guided evolution.
Eur. J. Oper. Res., 2015

Sampling from Discrete Distributions and Computing Frechet Distances.
Bulletin of the EATCS, 2015

Counting Triangulations and Other Crossing-Free Structures via Onion Layers.
Discrete & Computational Geometry, 2015

Counting triangulations and other crossing-free structures approximately.
Comput. Geom., 2015

Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems.
Algorithmica, 2015

Ultra-Fast Load Balancing on Scale-Free Networks.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Efficient computation of two-dimensional solution sets maximizing the epsilon-indicator.
Proceedings of the IEEE Congress on Evolutionary Computation, 2015

2014
Convergence of Hypervolume-Based Archiving Algorithms.
IEEE Trans. Evolutionary Computation, 2014

Generic Postprocessing via Subset Selection for Hypervolume and Epsilon-Indicator.
Proceedings of the Parallel Problem Solving from Nature - PPSN XIII, 2014

Internal DLA: Efficient Simulation of a Physical Growth Model - (Extended Abstract).
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Generierung diskreter Zufallsvariablen und Berechnung der Fréchetdistanz.
Proceedings of the Ausgezeichnete Informatikdissertationen 2014, 2014

Two-dimensional subset selection for hypervolume and epsilon-indicator.
Proceedings of the Genetic and Evolutionary Computation Conference, 2014

Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013
A Simple Sweep Line Algorithm for Counting Triangulations and Pseudo-triangulations.
CoRR, 2013

Speeding up many-objective optimization by Monte Carlo approximations.
Artif. Intell., 2013

Approximation quality of the hypervolume indicator.
Artif. Intell., 2013

Succinct sampling from discrete distributions.
Proceedings of the Symposium on Theory of Computing Conference, 2013

Bringing Order to Special Cases of Klee's Measure Problem.
Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

Exact and Efficient Generation of Geometric Random Variates and Random Graphs.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Parameterized average-case complexity of the hypervolume indicator.
Proceedings of the Genetic and Evolutionary Computation Conference, 2013

Counting Triangulations Approximately.
Proceedings of the 25th Canadian Conference on Computational Geometry, 2013

2012
Approximating the least hypervolume contributor: NP-hard in general, but fast in practice.
Theor. Comput. Sci., 2012

Remarks on Category-Based Routing in Social Networks
CoRR, 2012

An improved algorithm for Kleeʼs measure problem on fat boxes.
Comput. Geom., 2012

Convergence of hypervolume-based archiving algorithms ii: competitiveness.
Proceedings of the Genetic and Evolutionary Computation Conference, 2012

Counting crossing-free structures.
Proceedings of the Symposuim on Computational Geometry 2012, 2012

2011
Approximation-Guided Evolutionary Multi-Objective Optimization.
Proceedings of the IJCAI 2011, 2011

Convergence of hypervolume-based archiving algorithms I: effectiveness.
Proceedings of the 13th Annual Genetic and Evolutionary Computation Conference, 2011

The logarithmic hypervolume indicator.
Proceedings of the Foundations of Genetic Algorithms, 11th International Workshop, 2011

2010
An Efficient Algorithm for Computing Hypervolume Contributions.
Evolutionary Computation, 2010

Approximating the volume of unions and intersections of high-dimensional geometric objects.
Comput. Geom., 2010

Tight Bounds for the Approximation Ratio of the Hypervolume Indicator.
Proceedings of the Parallel Problem Solving from Nature, 2010

Scaling up indicator-based MOEAs by approximating the least hypervolume contributor: a preliminary study.
Proceedings of the Genetic and Evolutionary Computation Conference, 2010

The maximum hypervolume set yields near-optimal approximation.
Proceedings of the Genetic and Evolutionary Computation Conference, 2010

Klee's measure problem on fat boxes in time PARTIAL DIFFERENTIAL (n(d+2)/3).
Proceedings of the 26th ACM Symposium on Computational Geometry, 2010

2009
Don't be greedy when calculating hypervolume contributions.
Proceedings of the Foundations of Genetic Algorithms, 2009


  Loading...