| Publication | Date of Publication | Type |
|---|
Faster combinatorial k-clique algorithms
Algorithmica | 2026-06-17 | Paper |
| From donkeys to kings in tournaments | 2026-05-26 | Paper |
| Worst-case to expander-case reductions: derandomized and generalized | 2026-05-26 | Paper |
| Fine-grained hardness for edit distance to a fixed sequence | 2026-05-12 | Paper |
| On the fine-grained complexity of parity problems | 2026-03-18 | Paper |
| Scheduling lower bounds via and subset sum | 2026-03-18 | Paper |
| All-pairs max-flow is no harder than single-pair max-flow: Gomory-Hu trees in almost-linear time | 2025-08-15 | Paper |
| Breaking the cubic barrier for all-pairs max-flow: Gomory-Hu tree in nearly quadratic time | 2025-08-15 | Paper |
| APMF < APSP? Gomory-Hu tree for unweighted graphs in almost-quadratic time | 2025-08-13 | Paper |
| Cut-equivalent trees are optimal for min-cut queries | 2025-08-12 | Paper |
| Fine-grained complexity of analyzing compressed data: quantifying improvements over decompress-and-solve | 2025-08-06 | Paper |
| Distributed PCP theorems for hardness of approximation in P | 2025-08-06 | Paper |
| Popular conjectures as a barrier for dynamic planar graph algorithms | 2025-08-06 | Paper |
| If the current clique algorithms are optimal, so is Valiant's parser | 2025-08-05 | Paper |
| Tight hardness results for LCS and other sequence similarity measures | 2025-08-05 | Paper |
| Popular conjectures imply strong lower bounds for dynamic problems | 2025-08-05 | Paper |
| Listing 4-cycles | 2025-07-28 | Paper |
| On complexity of 1-center in various metrics | 2025-01-14 | Paper |
| On diameter approximation in directed graphs | 2025-01-06 | Paper |
| Can you solve closest string faster than exhaustive search? | 2025-01-06 | Paper |
| What else can Voronoi diagrams do for diameter in planar graphs? | 2025-01-06 | Paper |
| The time complexity of fully sparse matrix multiplication | 2024-11-28 | Paper |
| Worst-case to expander-case reductions | 2024-09-25 | Paper |
| Friendly cut sparsifiers and faster Gomory-Hu trees | 2024-07-19 | Paper |
| Improved approximation algorithms and lower bounds for search-diversification problems | 2024-06-24 | Paper |
| Faster combinatorial \(k\)-clique algorithms | 2024-05-31 | Paper |
| On the fine-grained complexity of approximating \(k\)-center in sparse graphs | 2024-05-14 | Paper |
| Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics | 2024-05-08 | Paper |
Reachability Preservers: New Extremal Bounds and Approximation Algorithms
SIAM Journal on Computing | 2024-03-19 | 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 |
Subcubic algorithms for Gomory–Hu tree in unweighted graphs
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 |
Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter
ACM Transactions on Algorithms | 2023-10-23 | Paper |
Faster algorithms for all-pairs bounded min-cuts
(available as arXiv preprint) | 2022-07-21 | Paper |
| Fine-Grained Reductions and Quantum Speedups for Dynamic Programming. | 2022-07-21 | Paper |
Scheduling lower bounds via AND subset sum
Journal of Computer and System Sciences | 2022-04-04 | Paper |
Smaller Cuts, Higher Lower Bounds
ACM Transactions on Algorithms | 2022-02-22 | Paper |
New algorithms and lower bounds for all-pairs max-flow in undirected graphs
Theory of Computing | 2021-10-25 | Paper |
Tighter connections between Formula-SAT and shaving logs
(available as arXiv preprint) | 2021-07-28 | Paper |
| Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds | 2021-06-15 | Paper |
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
Fooling views: a new lower bound technique for distributed computations under congestion
Distributed Computing | 2021-01-22 | Paper |
New hardness results for planar graph problems in p and an algorithm for sparsest cut
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
Dynamic set cover: improved algorithms and lower bounds
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 |
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 |
If the current clique algorithms are optimal, so is Valiant's parser
SIAM Journal on Computing | 2018-12-19 | Paper |
A hierarchy of lower bounds for sublinear additive spanners
SIAM Journal on Computing | 2018-12-05 | Paper |
Subtree isomorphism revisited
ACM Transactions on Algorithms | 2018-11-13 | Paper |
Near-linear lower bounds for distributed distance computations, even in sparse networks
(available as arXiv preprint) | 2018-08-16 | 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 |
Error Amplification for Pairwise Spanner Lower Bounds
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 |
A Hierarchy of Lower Bounds for Sublinear Additive Spanners
Proceedings of the Twenty-Eighth 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 |
The 4/3 additive spanner exponent is tight
Journal of the ACM | 2018-05-17 | Paper |
| Towards hardness of approximation for polynomial time problems | 2018-05-03 | Paper |
Near-optimal compression for the planar graph metric
(available as arXiv preprint) | 2018-03-15 | Paper |
| Near-optimal compression for the planar graph metric | 2018-03-15 | Paper |
Reachability preservers: new extremal bounds and approximation algorithms
(available as arXiv preprint) | 2018-03-15 | Paper |
| Reachability preservers: new extremal bounds and approximation algorithms | 2018-03-15 | Paper |
More applications of the polynomial method to algorithm design
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | 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 |
The 4/3 additive spanner exponent is tight
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 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 |
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 |
Losing weight by gaining edges
Algorithms - ESA 2014 | 2014-10-08 | Paper |
Consequences of Faster Alignment of Sequences
Automata, Languages, and Programming | 2014-07-01 | Paper |
Exact weight subgraphs and the k-sum conjecture
Automata, Languages, and Programming | 2013-08-06 | Paper |
