Karl Bringmann | Academic Influence

Karl Bringmann's AcademicInfluence.com Rankings

Karl Bringmann

Computer Science

#3420

World Rank

#3589

Historical Rank

Theoretical Computer Science

#65

World Rank

#65

Historical Rank

Database

#8545

World Rank

#8951

Historical Rank

computer-science Degrees

Download Badge

Computer Science

Karl Bringmann's Degrees

PhD Computer Science Saarland University
Masters Computer Science Saarland University
Bachelors Computer Science Saarland University

Similar Degrees You Can Earn

Why Is Karl Bringmann Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Karl Bringmann is a German theoretical computer scientist. He is currently senior researcher at Max Planck Institute for Informatics. Biography Bringmann earned his doctorate from Saarland University under the supervision of Kurt Mehlhorn.

(See a Problem?)

Karl Bringmann's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails (2014) (236)
Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping (2015) (212)
Approximating the volume of unions and intersections of high-dimensional geometric objects (2008) (187)
Approximating the least hypervolume contributor: NP-hard in general, but fast in practice (2008) (142)
An Efficient Algorithm for Computing Hypervolume Contributions (2010) (94)
Geometric Inhomogeneous Random Graphs (2015) (89)
Approximation-Guided Evolutionary Multi-Objective Optimization (2011) (84)
A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum (2016) (80)
Approximability of the discrete Fréchet distance (2015) (71)
Approximation quality of the hypervolume indicator (2013) (68)
SETH-based Lower Bounds for Subset Sum and Bicriteria Path (2017) (68)
Two-dimensional subset selection for hypervolume and epsilon-indicator (2014) (66)
Multivariate Fine-Grained Complexity of Longest Common Subsequence (2018) (57)
Don't be greedy when calculating hypervolume contributions (2009) (54)
Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product (2016) (49)
Efficient Sampling Methods for Discrete Distributions (2012) (46)
Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (Unless APSP Can) (2017) (45)
A Dichotomy for Regular Expression Membership Testing (2016) (42)
Sampling Geometric Inhomogeneous Random Graphs in Linear Time (2015) (39)
Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds (2014) (35)
A PTAS for 𝓁p-Low Rank Approximation (2019) (35)
Generic Postprocessing via Subset Selection for Hypervolume and Epsilon-Indicator (2014) (35)
Speeding up many-objective optimization by Monte Carlo approximations (2013) (35)
The maximum hypervolume set yields near-optimal approximation (2010) (34)
Tighter Connections Between Formula-SAT and Shaving Logs (2018) (34)
Average Distance in a General Class of Scale-Free Networks with Underlying Geometry (2016) (34)
Greedy Routing and the Algorithmic Small-World Phenomenon (2016) (33)
More consequences of falsifying SETH and the orthogonal vectors conjecture (2018) (32)
The logarithmic hypervolume indicator (2011) (32)
Bringing Order to Special Cases of Klee's Measure Problem (2013) (31)
Efficient optimization of many objectives by approximation-guided evolution (2015) (30)
Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve (2017) (28)
Maximum Volume Subset Selection for Anchored Boxes (2018) (28)
A fast implementation of near neighbors queries for Fréchet distance (GIS Cup) (2017) (27)
On Algebraic Branching Programs of Small Width (2017) (26)
Exact and Efficient Generation of Geometric Random Variates and Random Graphs (2013) (26)
Multivariate Analysis of Orthogonal Range Searching and Graph Distances (2018) (25)
An improved algorithm for Kleeʼs measure problem on fat boxes (2012) (24)
Parameterized average-case complexity of the hypervolume indicator (2013) (20)
Tight Bounds for the Approximation Ratio of the Hypervolume Indicator (2010) (20)
Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max (2019) (20)
Fine-Grained Complexity Theory (Tutorial) (2019) (20)
Succinct sampling from discrete distributions (2013) (18)
De-anonymization of Heterogeneous Random Graphs in Quasilinear Time (2014) (18)
Convergence of hypervolume-based archiving algorithms I: effectiveness (2011) (16)
Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance (2019) (16)
Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability (2018) (15)
Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines (2013) (15)
Hitting Set in hypergraphs of low VC-dimension (2015) (14)
Polyline Simplification has Cubic Complexity (2018) (14)
Counting Triangulations and Other Crossing-Free Structures via Onion Layers (2013) (14)
Internal DLA: Efficient Simulation of a Physical Growth Model - (Extended Abstract) (2014) (14)
Counting crossing-free structures (2012) (13)
Parameterized complexity dichotomy for Steiner Multicut (2014) (12)
APPROXIMABILITY OF THE DISCRETE FRÉCHET (2016) (12)
Counting triangulations and other crossing-free structures approximately (2014) (11)
Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS (2018) (11)
Convergence of Hypervolume-Based Archiving Algorithms (2014) (11)
On Near-Linear-Time Algorithms for Dense Subset Sum (2020) (10)
Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond (2022) (10)
Fast and Simple Modular Subset Sum (2020) (10)
Scaling up indicator-based MOEAs by approximating the least hypervolume contributor: a preliminary study (2010) (9)
Convergence of hypervolume-based archiving algorithms ii: competitiveness (2012) (9)
A Simple Sweep Line Algorithm for Counting Triangulations and Pseudo-triangulations (2013) (9)
A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties (2019) (9)
Saarland University , Saarbrücken , Germany Klee ’ s Measure Problem on Fat Boxes in Time O ( n ( d + 2 ) / 3 ) (2009) (9)
Approximation Algorithms for ࡁ0-Low Rank Approximation (2017) (9)
Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems (2013) (8)
A note on hardness of diameter approximation (2017) (8)
Klee's measure problem on fat boxes in time ∂(n(d+2)/3) (2010) (8)
Scheduling Lower Bounds via AND Subset Sum (2020) (8)
A Fine-Grained Perspective on Approximating Subset Sum and Partition (2020) (8)
Approximation Algorithms for l0-Low Rank Approximation (2017) (7)
Current Algorithms for Detecting Subgraphs of Bounded Treewidth are Probably Optimal (2021) (7)
Balls into bins via local search: Cover time and maximum load (2013) (7)
Efficient computation of two-dimensional solution sets maximizing the epsilon-indicator (2015) (6)
Fast fencing (2018) (6)
Sparse nonnegative convolution is equivalent to dense nonnegative convolution (2021) (6)
Top-𝑘-convolution and the quest for near-linear output-sensitive subset sum (2020) (6)
Faster Minimization of Tardy Processing Time on a Single Machine (2022) (6)
Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars (2018) (6)
A Linear-Time n0.4-Approximation for Longest Common Subsequence (2021) (6)
Translating Hausdorff is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation (2021) (5)
Online Checkpointing with Improved Worst-Case Guarantees (2013) (5)
Few Matches or Almost Periodicity: Faster Pattern Matching with Mismatches in Compressed Texts (2019) (5)
Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution (2022) (5)
Fast n-fold Boolean Convolution via Additive Combinatorics (2021) (4)
On Geometric Set Cover for Orthants (2019) (4)
Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fréchet Distance (2021) (4)
Impossibility Results for Grammar-Compressed Linear Algebra (2020) (4)
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics (2022) (4)
Almost-optimal sublinear-time edit distance in the low distance regime (2022) (3)
Discrete Fréchet Distance under Translation (2021) (3)
Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines (2015) (3)
Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs (2022) (3)
Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution (2021) (3)
Discrete Fréchet Distance Under Translation: Conditional Hardness and an Improved Algorithm (2021) (3)
Counting Triangulations Approximately (2013) (3)
When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation (2020) (2)
Approximation Algorithms for l 0 -Low Rank Approximation. (2017) (2)
Sampling from Discrete Distributions and Computing Frechet Distances (2015) (2)
Fine-Grained Complexity Theory: Conditional Lower Bounds for Computational Geometry (2021) (2)
Improved Sublinear-Time Edit Distance for Preprocessed Strings (2022) (2)
A PTAS for l p-Low Rank Approximation (2018) (2)
Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs (2017) (2)
Unbalanced Triangle Detection and Enumeration Hardness for Unions of Conjunctive Queries (2022) (2)
Approximating Subset Sum is equivalent to Min-Plus-Convolution (2019) (2)
Brief Announcement: A Note on Hardness of Diameter Approximation (2017) (2)
Parameterized Complexity Dichotomy for Steiner Multicut (Full Version) (2014) (1)
38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, March 16-19, 2021, Saarbrücken, Germany (Virtual Conference) (2021) (1)
Remarks on Category-Based Routing in Social Networks (2012) (1)
Multivariate Analysis of Orthogonal Range Searching and Graph Distances (2020) (1)
Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds (2022) (1)
Fine-Grained Completeness for Optimization in P (2021) (1)
De-anonymization of Heterogeneous Random Graphs in Quasilinear Time (2017) (1)
New Algorithms and Lower Bounds for the Discrete Frechet Distance (システム数理と応用) (2014) (1)
A PTAS for $\ell_p$-Low Rank Approximation (2018) (1)
Tight Fine-Grained Bounds for Direct Access on Join Queries (2022) (1)
C C ] 2 4 M ay 2 01 7 On algebraic branching programs of small width ∗ (2017) (1)
1 Sampling from Discrete Distributions (2015) (0)
Approximation Algorithms for $\ell_0$-Low Rank Approximation (2017) (0)
Randomized Algorithms and Probabilistic Methods: Advanced Topics (2015) (0)
Automata, Languages, and Programming (2013) (0)
Protection against wind. I. Basic facts of agricultural meteorology and general husbandry. (1955) (0)
Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves (2022) (0)
Sparse Fourier Transform by traversing Cooley-Tukey FFT computation graphs (2021) (0)
Efficient Sampling Methods for Discrete Distributions (2016) (0)
Counting Triangulations and Other Crossing-Free Structures via Onion Layers (2015) (0)
A Primer to Randomness (2020) (0)
A Structural Investigation of the Approximability of Polynomial-Time Problems (2022) (0)
Klee's measure problem on fat boxes in time PARTIAL DIFFERENTIAL ( n ( d +2)/3 ). (2010) (0)
Fine-Grained Complexity Theory (2019) (0)
Faster 0-1-Knapsack via Near-Convex Min-Plus-Convolution (2023) (0)
On algebraic branching programs of small width Bringmann (2017) (0)
Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems (2014) (0)
Traversing the FFT Computation Tree for Dimension-Independent Sparse Fourier Transforms (2021) (0)
Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster! (2023) (0)
Faster Minimization of Tardy Processing\newline Time on a Single Machine (2020) (0)
Ultra-Fast Load Balancing on Scale-Free Networks (2015) (0)
UvA-DARE (Digital Academic Repository) On algebraic branching programs of small width (2017) (0)
Fe b 20 16 Geometric Inhomogeneous Random Graphs (2016) (0)

This paper list is powered by the following services:

Other Resources About Karl Bringmann

en.wikipedia.org

What Schools Are Affiliated With Karl Bringmann?

Karl Bringmann is affiliated with the following schools: