| Publication | Date of Publication | Type |
|---|
| Distributed distance approximation | 2026-03-31 | Paper |
| New bounds for matrix multiplication: from alpha to omega | 2024-11-28 | Paper |
| Simpler and higher lower bounds for shortcut sets | 2024-11-28 | Paper |
| Improved roundtrip spanners, emulators, and directed girth approximation | 2024-11-28 | Paper |
| Fast 2-approximate all-pairs shortest paths | 2024-11-28 | Paper |
A refined laser method and faster matrix multiplication
TheoretiCS | 2024-09-10 | Paper |
| Algorithmic trade-offs for girth approximation in undirected graphs | 2024-07-19 | Paper |
| Better lower bounds for shortcut sets and additive spanners via an improved alternation product | 2024-07-19 | Paper |
| Listing 6-cycles | 2024-05-29 | Paper |
| Improved girth approximation in weighted undirected graphs | 2024-05-14 | Paper |
| Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more | 2024-05-08 | Paper |
scientific article; zbMATH DE number 7788370 (Why is no real title available?)
(available as arXiv preprint) | 2024-01-15 | Paper |
scientific article; zbMATH DE number 7788448 (Why is no real title available?)
(available as arXiv preprint) | 2024-01-15 | Paper |
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
SIAM Journal on Computing | 2023-12-19 | Paper |
Hardness for triangle problems under even more believable hypotheses: reductions from real APSP, real 3SUM, and OV
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
Hardness for triangle problems under even more believable hypotheses: reductions from real APSP, real 3SUM, and OV
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter
ACM Transactions on Algorithms | 2023-10-23 | Paper |
Quasipolynomiality of the Smallest Missing Induced Subgraph
Journal of Graph Algorithms and Applications | 2023-09-20 | Paper |
Factorization and pseudofactorization of weighted graphs
Discrete Applied Mathematics | 2023-06-15 | Paper |
Dynamic Parameterized Problems and Algorithms
ACM Transactions on Algorithms | 2023-04-26 | Paper |
Isometric Hamming embeddings of weighted graphs
Discrete Applied Mathematics | 2023-04-17 | Paper |
scientific article; zbMATH DE number 7561506 (Why is no real title available?)
(available as arXiv preprint) | 2022-07-21 | Paper |
scientific article; zbMATH DE number 7561539 (Why is no real title available?)
(available as arXiv preprint) | 2022-07-21 | Paper |
Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
(available as arXiv preprint) | 2022-07-21 | Paper |
Better Distance Preservers and Additive Spanners
ACM Transactions on Algorithms | 2022-02-22 | Paper |
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
SIAM Journal on Computing | 2022-01-07 | Paper |
Faster replacement paths and distance sensitivity oracles
ACM Transactions on Algorithms | 2021-12-16 | Paper |
Isometric Hamming embeddings of weighted graphs
(available as arXiv preprint) | 2021-12-13 | Paper |
Graph pattern detection: hardness for all induced patterns and faster noninduced cycles
SIAM Journal on Computing | 2021-11-19 | Paper |
Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
SIAM Journal on Computing | 2021-08-06 | Paper |
Further limitations of the known approaches for matrix multiplication
(available as arXiv preprint) | 2021-06-15 | Paper |
Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
New algorithms and hardness for incremental single-source shortest paths in directed graphs
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
| Knockout tournaments | 2020-11-12 | Paper |
On some fine-grained questions in algorithms and complexity
Proceedings of the International Congress of Mathematicians (ICM 2018) | 2020-09-22 | Paper |
Limits on all known (and some unknown) approaches to matrix multiplication
Proceedings of the 2019 on International Symposium on Symbolic and Algebraic Computation | 2020-09-10 | Paper |
Nearly optimal separation between partially and fully retroactive data structures
(available as arXiv preprint) | 2020-08-25 | Paper |
Preserving distances in very faulty graphs
(available as arXiv preprint) | 2020-05-27 | Paper |
Dynamic parameterized problems and algorithms
(available as arXiv preprint) | 2020-05-27 | Paper |
| Public-key cryptography in the fine-grained setting | 2020-03-09 | Paper |
Graph pattern detection: hardness for all induced patterns and faster non-induced cycles
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
Towards tight approximation bounds for graph diameter and eccentricities
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
Better approximation algorithms for the graph diameter
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
| scientific article; zbMATH DE number 7053319 (Why is no real title available?) | 2019-05-10 | 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 |
Subcubic equivalences between path, matrix, and triangle problems
Journal of the ACM | 2019-02-25 | Paper |
If the current clique algorithms are optimal, so is Valiant's parser
SIAM Journal on Computing | 2018-12-19 | Paper |
Subtree isomorphism revisited
ACM Transactions on Algorithms | 2018-11-13 | Paper |
Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Subtree isomorphism revisited
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Better distance preservers and additive spanners
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
SIAM Journal on Computing | 2018-07-04 | Paper |
Conditional hardness for sensitivity problems
(available as arXiv preprint) | 2018-05-03 | Paper |
| Tight hardness for shortest cycles and paths in sparse graphs | 2018-03-15 | Paper |
Tight hardness for shortest cycles and paths in sparse graphs
(available as arXiv preprint) | 2018-03-15 | Paper |
| Approximating cycles in directed graphs: fast algorithms for girth and roundtrip spanners | 2018-03-15 | Paper |
Approximating cycles in directed graphs: fast algorithms for girth and roundtrip spanners
(available as arXiv preprint) | 2018-03-15 | Paper |
| Optimal Vertex Fault Tolerant Spanners (for fixed stretch) | 2018-03-15 | Paper |
Optimal Vertex Fault Tolerant Spanners (for fixed stretch)
(available as arXiv preprint) | 2018-03-15 | Paper |
A 7/3-approximation for feedback vertex sets in tournaments
(available as arXiv preprint) | 2018-03-02 | Paper |
Deterministic time-space trade-offs for \(k\)-SUM
(available as arXiv preprint) | 2017-12-19 | Paper |
Subcubic equivalences between graph centrality problems, APSP and diameter
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
Finding four-node subgraphs in triangle time
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
| Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk) | 2017-09-29 | Paper |
| Faster replacement paths | 2017-09-29 | Paper |
Faster replacement paths
(available as arXiv preprint) | 2017-09-29 | Paper |
Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
Who can win a single-elimination tournament?
SIAM Journal on Discrete Mathematics | 2017-08-18 | Paper |
Very sparse additive spanners and emulators
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science | 2017-05-19 | Paper |
Matching triangles and basing hardness on an extremely popular conjecture
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
Finding, minimizing, and counting weighted subgraphs
Proceedings of the forty-first annual ACM symposium on Theory of computing | 2015-02-04 | Paper |
Finding a maximum weight triangle in n 3-Δ time, with applications
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
Finding heaviest \(H\)-subgraphs in real weighted graphs, with applications
ACM Transactions on Algorithms | 2014-11-18 | Paper |
Nondecreasing paths in a weighted graph or: how to optimally read a train schedule
ACM Transactions on Algorithms | 2014-11-18 | Paper |
Fast approximation algorithms for the diameter and radius of sparse graphs
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2014-08-07 | Paper |
Minimum Weight Cycles and Triangles: Equivalences and Algorithms
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
Listing triangles
Automata, Languages, and Programming | 2014-07-01 | Paper |
Consequences of Faster Alignment of Sequences
Automata, Languages, and Programming | 2014-07-01 | Paper |
Multiplying matrices faster than coppersmith-winograd
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
Finding, minimizing, and counting weighted subgraphs
SIAM Journal on Computing | 2013-09-25 | Paper |
scientific article; zbMATH DE number 5899282 (Why is no real title available?)
Theory of Computing | 2011-05-24 | Paper |
Confronting hardness using a hybrid approach
Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 | 2010-08-16 | Paper |
| scientific article; zbMATH DE number 5764853 (Why is no real title available?) | 2010-08-06 | Paper |
Efficient algorithms for clique problems
Information Processing Letters | 2010-06-16 | Paper |
Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems
Automata, Languages and Programming | 2009-03-12 | Paper |
| scientific article; zbMATH DE number 5485494 (Why is no real title available?) | 2009-01-05 | Paper |
A New Combinatorial Approach for Sparse Graph Problems
Automata, Languages and Programming | 2008-08-28 | Paper |
Uniquely Represented Data Structures for Computational Geometry
Algorithm Theory – SWAT 2008 | 2008-07-15 | Paper |
Finding nonoverlapping substructures of a sparse matrix
ETNA - Electronic Transactions on Numerical Analysis | 2007-03-16 | Paper |
Finding nonoverlapping substructures of a sparse matrix
ETNA - Electronic Transactions on Numerical Analysis | 2007-03-16 | Paper |
Mathematical Foundations of Computer Science 2005
Lecture Notes in Computer Science | 2006-10-20 | Paper |
