| Publication | Date of Publication | Type |
|---|
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
| 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
| 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
| 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 |
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 |
Error Amplification for Pairwise Spanner Lower Bounds
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 |
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
| 2018-03-15 | Paper |
Reachability preservers: new extremal bounds and approximation algorithms
| 2018-03-15 | 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 |
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 |
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 |
