Karl Bringmann

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

The Time Complexity of Fully Sparse Matrix Multiplication.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds.

[BibT_eX]

[DOI]

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

2023

A Linear-Time n0.4-Approximation for Longest Common Subsequence.

[BibT_eX]

[DOI]

Vincent Cohen-Addad

Debarati Das

ACM Trans. Algorithms, January, 2023

Knapsack with Small Items in Near-Quadratic Time.

[BibT_eX]

[DOI]

CoRR, 2023

Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics.

[BibT_eX]

[DOI]

Amir Abboud

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Traversing the FFT Computation Tree for Dimension-Independent Sparse Fourier Transforms.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!

[BibT_eX]

[DOI]

Alejandro Cassis

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Faster 0-1-Knapsack via Near-Convex Min-Plus-Convolution.

[BibT_eX]

[DOI]

Alejandro Cassis

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

2022

SETH-based Lower Bounds for Subset Sum and Bicriteria Path.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2022

Greedy routing and the algorithmic small-world phenomenon.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2022

Scheduling lower bounds via AND subset sum.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2022

Unbalanced Triangle Detection and Enumeration Hardness for Unions of Conjunctive Queries.

[BibT_eX]

[DOI]

Nofar Carmeli

CoRR, 2022

Faster Minimization of Tardy Processing Time on a Single Machine.

[BibT_eX]

[DOI]

Algorithmica, 2022

Almost-optimal sublinear-time edit distance in the low distance regime.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fréchet Distance.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Tight Fine-Grained Bounds for Direct Access on Join Queries.

[BibT_eX]

[DOI]

Nofar Carmeli

Stefan Mengel

Proceedings of the PODS '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12, 2022

Improved Sublinear-Time Edit Distance for Preprocessed Strings.

[BibT_eX]

[DOI]

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

A Structural Investigation of the Approximability of Polynomial-Time Problems.

[BibT_eX]

[DOI]

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution.

[BibT_eX]

[DOI]

Alejandro Cassis

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs.

[BibT_eX]

[DOI]

Proceedings of the 38th International Symposium on Computational Geometry, 2022

Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves.

[BibT_eX]

[DOI]

Proceedings of the 38th International Symposium on Computational Geometry, 2022

Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds.

[BibT_eX]

[DOI]

Proceedings of the 38th International Symposium on Computational Geometry, 2022

2021

Discrete Fréchet Distance under Translation: Conditional Hardness and an Improved Algorithm.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2021

Walking the dog fast in practice: Algorithm engineering of the Fréchet distance.

[BibT_eX]

[DOI]

J. Comput. Geom., 2021

Sparse Fourier Transform by traversing Cooley-Tukey FFT computation graphs.

[BibT_eX]

[DOI]

CoRR, 2021

A Linear-Time n0.4-Approximation for Longest Common Subsequence.

[BibT_eX]

[DOI]

Vincent Cohen-Addad

Debarati Das

CoRR, 2021

Sparse nonnegative convolution is equivalent to dense nonnegative convolution.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Fast and Simple Modular Subset Sum.

[BibT_eX]

[DOI]

Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021

On Near-Linear-Time Algorithms for Dense Subset Sum.

[BibT_eX]

[DOI]

Philip Wellnitz

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

A Fine-Grained Perspective on Approximating Subset Sum and Partition.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Current Algorithms for Detecting Subgraphs of Bounded Treewidth Are Probably Optimal.

[BibT_eX]

[DOI]

Jasper Slusallek

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Fast n-Fold Boolean Convolution via Additive Combinatorics.

[BibT_eX]

[DOI]

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

A Linear-Time n0.4-Approximation for Longest Common Subsequence.

[BibT_eX]

[DOI]

Debarati Das

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Translating Hausdorff Is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation.

[BibT_eX]

[DOI]

Proceedings of the 37th International Symposium on Computational Geometry, 2021

Fine-Grained Complexity Theory: Conditional Lower Bounds for Computational Geometry.

[BibT_eX]

[DOI]

Proceedings of the Connecting with Computability, 2021

Fine-Grained Completeness for Optimization in P.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2021

2020

Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (Unless APSP Can).

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2020

Polyline simplification has cubic complexity.

[BibT_eX]

[DOI]

Bhaskar Ray Chaudhury

J. Comput. Geom., 2020

Multivariate Analysis of Orthogonal Range Searching and Graph Distances.

[BibT_eX]

[DOI]

Thore Husfeldt

Måns Magnusson

Algorithmica, 2020

Top-k-convolution and the quest for near-linear output-sensitive subset sum.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Impossibility Results for Grammar-Compressed Linear Algebra.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance Under Translation.

[BibT_eX]

[DOI]

Proceedings of the 28th Annual European Symposium on Algorithms, 2020

2019

Geometric inhomogeneous random graphs.

[BibT_eX]

[DOI]

Ralph Keusch

Johannes Lengler

Theor. Comput. Sci., 2019

Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product.

[BibT_eX]

[DOI]

Virginia Vassilevska Williams

Fabrizio Grandoni

Barna Saha

SIAM J. Comput., 2019

Approximating Subset Sum is equivalent to Min-Plus-Convolution.

[BibT_eX]

[DOI]

CoRR, 2019

Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max.

[BibT_eX]

[DOI]

Karol Wegrzycki

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Fine-Grained Complexity Theory (Tutorial).

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Philip Wellnitz

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.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

A PTAS for ℓp-Low Rank Approximation.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

On Geometric Set Cover for Orthants.

[BibT_eX]

[DOI]

Proceedings of the 27th Annual European Symposium on Algorithms, 2019

A Fine-Grained Analogue of Schaefer's Theorem in P: Dichotomy of Exists^k-Forall-Quantified First-Order Graph Properties.

[BibT_eX]

[DOI]

Proceedings of the 34th Computational Complexity Conference, 2019

2018

On Algebraic Branching Programs of Small Width.

[BibT_eX]

[DOI]

Christian Ikenmeyer

Jeroen Zuiddam

J. ACM, 2018

A note on hardness of diameter approximation.

[BibT_eX]

[DOI]

Sebastian Krinninger

Inf. Process. Lett., 2018

A PTAS for 𝓁p-Low Rank Approximation.

[BibT_eX]

[DOI]

CoRR, 2018

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

[BibT_eX]

[DOI]

Thore Husfeldt

Måns Magnusson

CoRR, 2018

De-anonymization of Heterogeneous Random Graphs in Quasilinear Time.

[BibT_eX]

[DOI]

Anton Krohmer

Algorithmica, 2018

Fast fencing.

[BibT_eX]

[DOI]

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

More consequences of falsifying SETH and the orthogonal vectors conjecture.

[BibT_eX]

[DOI]

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

Multivariate Fine-Grained Complexity of Longest Common Subsequence.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Tighter Connections Between Formula-SAT and Shaving Logs.

[BibT_eX]

[DOI]

Amir Abboud

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS.

[BibT_eX]

[DOI]

Bhaskar Ray Chaudhury

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.

[BibT_eX]

[DOI]

Int. J. Comput. Geom. Appl., 2017

Approximation Algorithms for ࡁ0-Low Rank Approximation.

[BibT_eX]

[DOI]

Pavel Kolev

David P. Woodruff

CoRR, 2017

Efficient Sampling Methods for Discrete Distributions.

[BibT_eX]

[DOI]

Konstantinos Panagiotou

Algorithmica, 2017

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

[BibT_eX]

[DOI]

Algorithmica, 2017

Brief Announcement: A Note on Hardness of Diameter Approximation.

[BibT_eX]

[DOI]

Sebastian Krinninger

Proceedings of the 31st International Symposium on Distributed Computing, 2017

A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Approximation Algorithms for l0-Low Rank Approximation.

[BibT_eX]

[DOI]

Pavel Kolev

David P. Woodruff

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.

[BibT_eX]

[DOI]

Thomas Dueholm Hansen

Sebastian Krinninger

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).

[BibT_eX]

[DOI]

Julian Baldus

Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2017

A Dichotomy for Regular Expression Membership Testing.

[BibT_eX]

[DOI]

Allan Grønlund

Kasper Green Larsen

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.

[BibT_eX]

[DOI]

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Sampling Geometric Inhomogeneous Random Graphs in Linear Time.

[BibT_eX]

[DOI]

Ralph Keusch

Johannes Lengler

Proceedings of the 25th Annual European Symposium on Algorithms, 2017

Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars.

[BibT_eX]

[DOI]

Philip Wellnitz

Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching, 2017

Maximum Volume Subset Selection for Anchored Boxes.

[BibT_eX]

[DOI]

Sergio Cabello

Michael T. M. Emmerich

Proceedings of the 33rd International Symposium on Computational Geometry, 2017

2016

Balls into bins via local search: Cover time and maximum load.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2016

Approximability of the discrete Fréchet distance.

[BibT_eX]

[DOI]

Wolfgang Mulzer

J. Comput. Geom., 2016

Parameterized complexity dichotomy for Steiner Multicut.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2016

Greedy Routing and the Algorithmic Small-World Phenomenom.

[BibT_eX]

[DOI]

CoRR, 2016

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

[BibT_eX]

[DOI]

Ralph Keusch

Johannes Lengler

CoRR, 2016

Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product.

[BibT_eX]

[DOI]

Virginia Vassilevska Williams

Fabrizio Grandoni

Barna Saha

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

Hitting Set for Hypergraphs of Low VC-dimension.

[BibT_eX]

[DOI]

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

2015

Sampling from discrete distributions and computing Fréchet distances.

[BibT_eX]

[DOI]

PhD thesis, 2015

Online Checkpointing with Improved Worst-Case Guarantees.

[BibT_eX]

[DOI]

INFORMS J. Comput., 2015

Efficient optimization of many objectives by approximation-guided evolution.

[BibT_eX]

[DOI]

Eur. J. Oper. Res., 2015

Sampling from Discrete Distributions and Computing Frechet Distances.

[BibT_eX]

[DOI]

Bull. EATCS, 2015

Counting Triangulations and Other Crossing-Free Structures via Onion Layers.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2015

Counting triangulations and other crossing-free structures approximately.

[BibT_eX]

[DOI]

Comput. Geom., 2015

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

[BibT_eX]

[DOI]

Christian Engels

Bodo Manthey

B. V. Raghavendra Rao

Algorithmica, 2015

Ultra-Fast Load Balancing on Scale-Free Networks.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping.

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Efficient computation of two-dimensional solution sets maximizing the epsilon-indicator.

[BibT_eX]

[DOI]

Patrick Klitzke

Proceedings of the IEEE Congress on Evolutionary Computation, 2015

2014

Convergence of Hypervolume-Based Archiving Algorithms.

[BibT_eX]

[DOI]

IEEE Trans. Evol. Comput., 2014

Generic Postprocessing via Subset Selection for Hypervolume and Epsilon-Indicator.

[BibT_eX]

[DOI]

Patrick Klitzke

Proceedings of the Parallel Problem Solving from Nature - PPSN XIII, 2014

Internal DLA: Efficient Simulation of a Physical Growth Model - (Extended Abstract).

[BibT_eX]

[DOI]

Fabian Kuhn

Konstantinos Panagiotou

Ueli Peter

Henning Thomas

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Generierung diskreter Zufallsvariablen und Berechnung der Fréchetdistanz.

[BibT_eX]

[DOI]

Proceedings of the Ausgezeichnete Informatikdissertationen 2014, 2014

Two-dimensional subset selection for hypervolume and epsilon-indicator.

[BibT_eX]

[DOI]

Patrick Klitzke

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.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Victor Alvarez

Saurabh Ray

CoRR, 2013

Speeding up many-objective optimization by Monte Carlo approximations.

[BibT_eX]

[DOI]

Artif. Intell., 2013

Approximation quality of the hypervolume indicator.

[BibT_eX]

[DOI]

Artif. Intell., 2013

Succinct sampling from discrete distributions.

[BibT_eX]

[DOI]

Kasper Green Larsen

Proceedings of the Symposium on Theory of Computing Conference, 2013

Bringing Order to Special Cases of Klee's Measure Problem.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

Exact and Efficient Generation of Geometric Random Variates and Random Graphs.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Parameterized average-case complexity of the hypervolume indicator.

[BibT_eX]

[DOI]

Proceedings of the Genetic and Evolutionary Computation Conference, 2013

Counting Triangulations Approximately.

[BibT_eX]

[DOI]

Proceedings of the 25th Canadian Conference on Computational Geometry, 2013

2012

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

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2012

Remarks on Category-Based Routing in Social Networks

[BibT_eX]

[DOI]

Kurt Mehlhorn

Adrian Neumann

CoRR, 2012

An improved algorithm for Kleeʼs measure problem on fat boxes.

[BibT_eX]

[DOI]

Comput. Geom., 2012

Convergence of hypervolume-based archiving algorithms ii: competitiveness.

[BibT_eX]

[DOI]

Proceedings of the Genetic and Evolutionary Computation Conference, 2012

Counting crossing-free structures.

[BibT_eX]

[DOI]

Proceedings of the 28th ACM Symposium on Computational Geometry, 2012

2011

Approximation-Guided Evolutionary Multi-Objective Optimization.

[BibT_eX]

[DOI]

Proceedings of the IJCAI 2011, 2011

Convergence of hypervolume-based archiving algorithms I: effectiveness.

[BibT_eX]

[DOI]

Proceedings of the 13th Annual Genetic and Evolutionary Computation Conference, 2011

The logarithmic hypervolume indicator.

[BibT_eX]

[DOI]

Proceedings of the Foundations of Genetic Algorithms, 11th International Workshop, 2011

2010

An Efficient Algorithm for Computing Hypervolume Contributions.

[BibT_eX]

[DOI]

Evol. Comput., 2010

Approximating the volume of unions and intersections of high-dimensional geometric objects.

[BibT_eX]

[DOI]

Comput. Geom., 2010

Tight Bounds for the Approximation Ratio of the Hypervolume Indicator.

[BibT_eX]

[DOI]

Proceedings of the Parallel Problem Solving from Nature, 2010

Scaling up indicator-based MOEAs by approximating the least hypervolume contributor: a preliminary study.

[BibT_eX]

[DOI]

Proceedings of the Genetic and Evolutionary Computation Conference, 2010

The maximum hypervolume set yields near-optimal approximation.

[BibT_eX]

[DOI]

Proceedings of the Genetic and Evolutionary Computation Conference, 2010

Klee's measure problem on fat boxes in time PARTIAL DIFFERENTIAL (n(d+2)/3).

[BibT_eX]

[DOI]

Proceedings of the 26th ACM Symposium on Computational Geometry, 2010

2009

Don't be greedy when calculating hypervolume contributions.

[BibT_eX]

[DOI]