2025
Near-Optimal Directed Low-Diameter Decompositions.
CoRR, February, 2025
Beating Bellman's Algorithm for Subset Sum.
Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 2025
2024
Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation.
CoRR, 2024
A Fine-grained Classification of Subquadratic Patterns for Subgraph Listing and Friends.
CoRR, 2024
Knapsack with Small Items in Near-Quadratic Time.
Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024
Dynamic Dynamic Time Warping.
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024
Faster Sublinear-Time Edit Distance.
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024
Approximating Subset Sum Ratio faster than Subset Sum.
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024
The Time Complexity of Fully Sparse Matrix Multiplication.
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024
The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds.
Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024
Exploring the Approximability Landscape of 3SUM.
Proceedings of the 32nd Annual European Symposium on Algorithms, 2024
Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing.
Proceedings of the 32nd Annual European Symposium on Algorithms, 2024
Fine-Grained Complexity of Earth Mover's Distance Under Translation.
Proceedings of the 40th International Symposium on Computational Geometry, 2024
2023
A Linear-Time <i>n</i><sup>0.4</sup>-Approximation for Longest Common Subsequence.
ACM Trans. Algorithms, January, 2023
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023
Traversing the FFT Computation Tree for Dimension-Independent Sparse Fourier Transforms.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023
Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023
Faster 0-1-Knapsack via Near-Convex Min-Plus-Convolution.
Proceedings of the 31st Annual European Symposium on Algorithms, 2023
2022
SETH-based Lower Bounds for Subset Sum and Bicriteria Path.
ACM Trans. Algorithms, 2022
Dynamic time warping under translation: Approximation guided by space-filling curves.
J. Comput. Geom., 2022
Greedy routing and the algorithmic small-world phenomenon.
J. Comput. Syst. Sci., 2022
Scheduling lower bounds via AND subset sum.
J. Comput. Syst. Sci., 2022
Unbalanced Triangle Detection and Enumeration Hardness for Unions of Conjunctive Queries.
CoRR, 2022
Faster Minimization of Tardy Processing Time on a Single Machine.
Algorithmica, 2022
Almost-optimal sublinear-time edit distance in the low distance regime.
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.
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.
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.
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022
Tight Fine-Grained Bounds for Direct Access on Join Queries.
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.
Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022
A Structural Investigation of the Approximability of Polynomial-Time Problems.
Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022
Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution.
Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022
Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs.
Proceedings of the 38th International Symposium on Computational Geometry, 2022
Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds.
Proceedings of the 38th International Symposium on Computational Geometry, 2022
2021
Discrete Fréchet Distance under Translation: Conditional Hardness and an Improved Algorithm.
ACM Trans. Algorithms, 2021
Translating Hausdorff is hard: fine-grained lower bounds for Hausdorff distance under translation.
J. Comput. Geom., 2021
Walking the dog fast in practice: Algorithm engineering of the Fréchet distance.
J. Comput. Geom., 2021
Sparse Fourier Transform by traversing Cooley-Tukey FFT computation graphs.
CoRR, 2021
A Linear-Time n<sup>0.4</sup>-Approximation for Longest Common Subsequence.
CoRR, 2021
Sparse nonnegative convolution is equivalent to dense nonnegative convolution.
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021
Fast and Simple Modular Subset Sum.
Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021
On Near-Linear-Time Algorithms for Dense Subset Sum.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021
A Fine-Grained Perspective on Approximating Subset Sum and Partition.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021
Current Algorithms for Detecting Subgraphs of Bounded Treewidth Are Probably Optimal.
Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021
Fast n-Fold Boolean Convolution via Additive Combinatorics.
Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021
A Linear-Time n<sup>0.4</sup>-Approximation for Longest Common Subsequence.
Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021
Fine-Grained Complexity Theory: Conditional Lower Bounds for Computational Geometry.
Proceedings of the Connecting with Computability, 2021
Fine-Grained Completeness for Optimization in P.
Proceedings of the Approximation, 2021
2020
Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (Unless APSP Can).
ACM Trans. Algorithms, 2020
Polyline simplification has cubic complexity.
J. Comput. Geom., 2020
Multivariate Analysis of Orthogonal Range Searching and Graph Distances.
Algorithmica, 2020
Top-k-convolution and the quest for near-linear output-sensitive subset sum.
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020
Impossibility Results for Grammar-Compressed Linear Algebra.
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.
Proceedings of the 28th Annual European Symposium on Algorithms, 2020
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
On Geometric Set Cover for Orthants.
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.
Proceedings of the 34th Computational Complexity Conference, 2019
2018
A note on hardness of diameter approximation.
Inf. Process. Lett., 2018
A PTAS for 𝓁<sub>p</sub>-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
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
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. Geom. Appl., 2017
On algebraic branching programs of small width.
Electron. Colloquium Comput. Complex., 2017
Approximation Algorithms for ࡁ<sub>0</sub>-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
Approximation Algorithms for l<sub>0</sub>-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.
J. Comput. Geom., 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 J. Comput., 2015
Efficient optimization of many objectives by approximation-guided evolution.
Eur. J. Oper. Res., 2015
Sampling from Discrete Distributions and Computing Frechet Distances.
Bull. EATCS, 2015
Counting Triangulations and Other Crossing-Free Structures via Onion Layers.
Discret. Comput. Geom., 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. Evol. Comput., 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 28th ACM Symposium on Computational Geometry, 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.
Evol. Comput., 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 (<i>n</i><sup>(<i>d</i>+2)/3</sup>).
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