| Publication | Date of Publication | Type |
|---|
| Near-optimal directed low-diameter decompositions | 2026-09-10 | Paper |
| Approximating Klee's measure problem and a lower bound for union volume estimation | 2026-08-11 | Paper |
| Even faster knapsack via rectangular monotone min-plus convolution and balancing | 2026-05-26 | Paper |
| Exploring the approximability landscape of 3SUM | 2026-05-26 | Paper |
| A linear-time \(n^{0.4}\)-approximation for longest common subsequence | 2026-05-12 | Paper |
| Current algorithms for detecting subgraphs of bounded treewidth are probably optimal | 2026-05-12 | Paper |
| Fast n-fold Boolean convolution via additive combinatorics | 2026-05-12 | Paper |
| Translating Hausdorff is hard: fine-grained lower bounds for Hausdorff distance under translation | 2026-04-27 | Paper |
| Faster minimization of tardy processing time on a single machine | 2026-03-18 | Paper |
| Scheduling lower bounds via and subset sum | 2026-03-18 | Paper |
Average distance in a general class of scale-free networks
Advances in Applied Probability | 2025-12-16 | Paper |
Fine-grained complexity of Earth mover's distance under translation
Journal of Computational Geometry | 2025-12-04 | Paper |
| Fine-grained complexity of Earth mover's distance under translation | 2025-11-24 | Paper |
| The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds | 2025-11-04 | Paper |
| Negative-weight single-source shortest paths in near-linear time: now faster! | 2025-08-15 | Paper |
| A dichotomy for regular expression membership testing | 2025-08-06 | Paper |
| Fine-grained complexity of analyzing compressed data: quantifying improvements over decompress-and-solve | 2025-08-06 | Paper |
| Truly sub-cubic algorithms for language edit distance and RNA-folding via fast bounded-difference min-plus product | 2025-08-06 | Paper |
| Quadratic conditional lower bounds for string problems and dynamic time warping | 2025-08-05 | Paper |
| Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails | 2025-08-05 | Paper |
Unbalanced triangle detection and enumeration hardness for unions of conjunctive queries
Logical Methods in Computer Science | 2025-05-06 | Paper |
| Faster 0-1-knapsack via near-convex min-plus-convolution | 2025-01-06 | Paper |
| Dynamic dynamic time warping | 2024-11-28 | Paper |
| Approximating Subset Sum Ratio faster than Subset Sum | 2024-11-28 | Paper |
| Faster sublinear-time edit distance | 2024-11-28 | Paper |
| The time complexity of fully sparse matrix multiplication | 2024-11-28 | Paper |
The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
TheoretiCS | 2024-11-05 | Paper |
| Tight bounds for approximate near neighbor searching for time series under the Fréchet distance | 2024-07-19 | Paper |
| Deterministic and Las Vegas algorithms for sparse nonnegative convolution | 2024-07-19 | Paper |
| A structural investigation of the approximability of polynomial-time problems | 2024-06-24 | Paper |
| Faster knapsack algorithms via bounded monotone min-plus-convolution | 2024-06-24 | Paper |
| Improved sublinear-time edit distance for preprocessed strings | 2024-06-24 | Paper |
| Traversing the FFT computation tree for dimension-independent sparse Fourier transforms | 2024-05-14 | Paper |
| Fast and simple modular subset sum | 2024-05-14 | Paper |
| Unlabeled multi-robot motion planning with tighter separation bounds | 2024-05-14 | Paper |
| Dynamic time warping under translation: approximation guided by space-filling curves | 2024-05-14 | Paper |
| Towards sub-quadratic diameter computation in geometric intersection graphs | 2024-05-14 | Paper |
| Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics | 2024-05-08 | Paper |
scientific article; zbMATH DE number 7788445 (Why is no real title available?)
(available as arXiv preprint) | 2024-01-15 | Paper |
scientific article; zbMATH DE number 7788446 (Why is no real title available?)
(available as arXiv preprint) | 2024-01-15 | Paper |
Dynamic time warping under translation: approximation guided by space-filling curves
(available as arXiv preprint) | 2023-12-20 | Paper |
| Dynamic time warping under translation: approximation guided by space-filling curves | 2023-12-20 | Paper |
Almost-optimal sublinear-time edit distance in the low distance regime
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
scientific article; zbMATH DE number 7768354 (Why is no real title available?)
(available as arXiv preprint) | 2023-11-20 | Paper |
Sparse nonnegative convolution is equivalent to dense nonnegative convolution
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
SETH-based Lower Bounds for Subset Sum and Bicriteria Path
ACM Transactions on Algorithms | 2023-10-31 | Paper |
A Linear-Time <i>n</i> <sup>0.4</sup> -Approximation for Longest Common Subsequence
ACM Transactions on Algorithms | 2023-10-23 | Paper |
Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (Unless APSP Can)
ACM Transactions on Algorithms | 2023-04-26 | Paper |
When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation
(available as arXiv preprint) | 2023-02-07 | Paper |
scientific article; zbMATH DE number 7610223 (Why is no real title available?)
(available as arXiv preprint) | 2022-10-31 | Paper |
| A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties | 2022-07-27 | Paper |
Sketching, streaming, and fine-grained complexity of (weighted) LCS
(available as arXiv preprint) | 2022-07-21 | Paper |
| Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance | 2022-07-18 | Paper |
| Polyline simplification has cubic complexity | 2022-07-18 | Paper |
| Fine-Grained Complexity Theory (Tutorial) | 2022-07-18 | Paper |
| On Geometric Set Cover for Orthants | 2022-05-11 | Paper |
Faster minimization of tardy processing time on a single machine
Algorithmica | 2022-05-03 | Paper |
Scheduling lower bounds via AND subset sum
Journal of Computer and System Sciences | 2022-04-04 | Paper |
Fine-grained complexity theory: conditional lower bounds for computational geometry
(available as arXiv preprint) | 2022-03-22 | Paper |
Discrete Fréchet Distance under Translation
ACM Transactions on Algorithms | 2022-02-16 | Paper |
Greedy routing and the algorithmic small-world phenomenon
Journal of Computer and System Sciences | 2022-01-31 | Paper |
Walking the dog fast in practice: algorithm engineering of the Fréchet distance
(available as arXiv preprint) | 2021-09-07 | Paper |
| Multivariate analysis of orthogonal range searching and graph distances | 2021-08-04 | Paper |
Tighter connections between Formula-SAT and shaving logs
(available as arXiv preprint) | 2021-07-28 | Paper |
Polyline simplification has cubic complexity
(available as arXiv preprint) | 2021-03-17 | Paper |
Top-𝑘-convolution and the quest for near-linear output-sensitive subset sum
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
Multivariate analysis of orthogonal range searching and graph distances
Algorithmica | 2020-08-12 | Paper |
scientific article; zbMATH DE number 7204576 (Why is no real title available?)
(available as arXiv preprint) | 2020-05-27 | Paper |
| Sampling geometric inhomogeneous random graphs in linear time | 2020-05-27 | Paper |
| On algebraic branching programs of small width | 2020-05-26 | Paper |
Clique-based lower bounds for parsing tree-adjoining grammars
(available as arXiv preprint) | 2020-05-25 | Paper |
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 | 2020-01-30 | Paper |
SETH-based lower bounds for subset sum and bicriteria path
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
A PTAS for <i>ℓ<sub>p</sub></i>-Low Rank Approximation
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
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-10-15 | Paper |
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-10-15 | Paper |
More consequences of falsifying SETH and the orthogonal vectors conjecture
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
Fast fencing
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
Truly subcubic algorithms for language edit distance and RNA folding via fast bounded-difference min-plus product
SIAM Journal on Computing | 2019-05-07 | Paper |
On Algebraic Branching Programs of Small Width
Journal of the ACM | 2019-02-25 | Paper |
On Algebraic Branching Programs of Small Width
Journal of the ACM | 2019-02-25 | Paper |
Geometric inhomogeneous random graphs
Theoretical Computer Science | 2019-01-25 | Paper |
Geometric inhomogeneous random graphs
Theoretical Computer Science | 2019-01-25 | Paper |
De-anonymization of heterogeneous random graphs in quasilinear time
Algorithmica | 2019-01-11 | Paper |
Maximum volume subset selection for anchored boxes
(available as arXiv preprint) | 2018-08-13 | Paper |
A near-linear pseudopolynomial time algorithm for subset sum
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
A note on hardness of diameter approximation
Information Processing Letters | 2018-03-16 | Paper |
Tree edit distance cannot be computed in strongly subcubic time (unless APSP can)
(available as arXiv preprint) | 2018-03-15 | Paper |
| Tree edit distance cannot be computed in strongly subcubic time (unless APSP can) | 2018-03-15 | Paper |
Multivariate fine-grained complexity of longest common subsequence
(available as arXiv preprint) | 2018-03-15 | Paper |
| Multivariate fine-grained complexity of longest common subsequence | 2018-03-15 | Paper |
Hitting Set for hypergraphs of low VC-dimension
(available as arXiv preprint) | 2018-03-02 | Paper |
Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds
International Journal of Computational Geometry & Applications | 2017-10-20 | Paper |
Greedy routing and the algorithmic small-world phenomenon
Proceedings of the ACM Symposium on Principles of Distributed Computing | 2017-10-11 | Paper |
Efficient sampling methods for discrete distributions
Algorithmica | 2017-10-10 | Paper |
| Approximability of the discrete Fréchet distance | 2017-10-10 | Paper |
Don't be greedy when calculating hypervolume contributions
Proceedings of the tenth ACM SIGEVO workshop on Foundations of genetic algorithms | 2017-07-14 | Paper |
The logarithmic hypervolume indicator
Proceedings of the 11th workshop proceedings on Foundations of genetic algorithms | 2017-07-14 | Paper |
| Approximability of the discrete Fréchet distance | 2017-03-30 | Paper |
Balls into bins via local search: cover time and maximum load
(available as arXiv preprint) | 2017-03-03 | Paper |
| Parameterized complexity dichotomy for Steiner Multicut | 2017-01-24 | Paper |
Efficient optimization of many objectives by approximation-guided evolution
European Journal of Operational Research | 2016-10-06 | Paper |
Balls into bins via local search: cover time and maximum load
Random Structures & Algorithms | 2016-07-25 | Paper |
Parameterized complexity dichotomy for \textsc{Steiner Multicut}
Journal of Computer and System Sciences | 2016-06-13 | Paper |
