| Publication | Date of Publication | Type |
|---|
Improved girth approximation in weighted undirected graphs
SIAM Journal on Computing | 2026-07-29 | Paper |
Separating \textsc{max} 2-and, \textsc{max di-cut}, and \textsc{max cut}
SIAM Journal on Computing | 2026-07-08 | Paper |
| Improved dynamic reachability algorithms for directed graphs | 2026-05-29 | Paper |
| Dynamic approximate all-pairs shortest paths in undirected graphs | 2026-05-29 | Paper |
| A 7/8-approximation algorithm for MAX 3SAT? | 2026-05-21 | Paper |
| All pairs shortest paths in undirected graphs with integer weights | 2026-05-06 | Paper |
| All pairs shortest paths in weighted directed graphs-exact and almost exact algorithms | 2025-10-29 | Paper |
| Separating \textsc{max} 2-\textsc{and}, \textsc{max di}-cut and \textsc{max cut} | 2025-08-15 | Paper |
| Random k-out subgraph leaves only O(n/k) inter-component edges | 2025-08-12 | Paper |
| A forward-backward single-source shortest paths algorithm | 2025-05-20 | Paper |
| All-pairs shortest paths in O(n^2) time with high probability | 2025-04-29 | Paper |
On the mysteries of MAX NAE-SAT
SIAM Journal on Discrete Mathematics | 2025-02-07 | Paper |
| Optimal energetic paths for electric cars | 2025-01-06 | Paper |
| Tight approximability of MAX 2-SAT and relatives, under UGC | 2024-11-28 | Paper |
Optimal resizable arrays
SIAM Journal on Computing | 2024-10-21 | Paper |
| Selection from heaps, row-sorted matrices, and X+Y using soft heaps | 2024-08-26 | Paper |
| Algorithmic trade-offs for girth approximation in undirected graphs | 2024-07-19 | Paper |
| Simulating a stack using queues | 2024-07-19 | Paper |
Finding strong components using depth-first search
European Journal of Combinatorics | 2024-06-28 | Paper |
| Minimum-cost paths for electric cars | 2024-05-29 | Paper |
| Improved girth approximation in weighted undirected graphs | 2024-05-14 | Paper |
| Optimal resizable arrays | 2024-05-14 | Paper |
On the mysteries of MAX NAE-SAT
(available as arXiv preprint) | 2024-01-15 | Paper |
The complexity of mean payoff games
Lecture Notes in Computer Science | 2023-12-12 | Paper |
| Dynamic ordered sets with approximate queries, approximate heaps and soft heaps | 2022-07-21 | Paper |
| A faster deterministic exponential time algorithm for energy games and mean payoff games | 2022-07-21 | Paper |
Pairing heaps: the forward variant
(available as arXiv preprint) | 2021-08-04 | Paper |
Improved bounds for multipass pairing heaps and path-balanced binary search trees
(available as arXiv preprint) | 2021-08-04 | Paper |
Public vs. private randomness in simultaneous multi-party communication complexity
Theoretical Computer Science | 2020-02-06 | Paper |
Faster k-SAT algorithms using biased-PPSZ
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
A sort of an adversary
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Dantzig's pivoting rule for shortest paths, deterministic MDPs, and minimum cost to time ratio cycles
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
Improved upper bounds for Random-Edge and Random-Jump on abstract cubes
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
| Efficient algorithms for the 2-gathering problem | 2019-05-06 | Paper |
| A simpler implementation and analysis of Chazelle's soft heaps | 2019-05-06 | Paper |
| Discounted deterministic Markov decision processes and discounted all-pairs shortest paths | 2019-05-06 | Paper |
Finding even cycles even faster
Automata, Languages and Programming | 2019-04-29 | Paper |
Adjacency labeling schemes and induced-universal graphs
SIAM Journal on Discrete Mathematics | 2019-01-16 | Paper |
Hollow heaps
ACM Transactions on Algorithms | 2018-11-12 | Paper |
Roundtrip spanners and roundtrip routing in directed graphs
ACM Transactions on Algorithms | 2018-11-05 | Paper |
Union-find with constant time deletions
ACM Transactions on Algorithms | 2018-10-30 | Paper |
Improved bounds for multipass pairing heaps and path-balanced binary search trees
(available as arXiv preprint) | 2018-06-22 | Paper |
| scientific article; zbMATH DE number 6829368 (Why is no real title available?) | 2018-01-24 | Paper |
| Random-Edge Is Slower Than Random-Facet on Abstract Cubes | 2017-12-19 | Paper |
The amortized cost of finding the minimum
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
| A subexponential lower bound for the random facet algorithm for parity games | 2017-09-29 | Paper |
| Collapse | 2017-09-29 | Paper |
Looking for MUM and DAD: text-text comparisons do help
Lecture Notes in Computer Science | 2017-01-19 | Paper |
Public vs. private randomness in simultaneous multi-party communication complexity
Structural Information and Communication Complexity | 2016-12-01 | Paper |
All pairs lightest shortest paths
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
Connection caching
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs (extended abstract)
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 | 2016-09-01 | Paper |
A fully dynamic reachability algorithm for directed graphs with an almost linear update time
SIAM Journal on Computing | 2016-06-01 | Paper |
Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences
ACM Transactions on Algorithms | 2016-04-11 | Paper |
All pairs shortest paths using bridging sets and rectangular matrix multiplication
Journal of the ACM | 2015-12-07 | Paper |
Hollow Heaps
Automata, Languages, and Programming | 2015-10-27 | Paper |
Fast sparse matrix multiplication
ACM Transactions on Algorithms | 2015-09-02 | Paper |
Melding priority queues
ACM Transactions on Algorithms | 2015-09-02 | Paper |
An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
Adjacency labeling schemes and induced-universal graphs
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
| scientific article; zbMATH DE number 6472582 (Why is no real title available?) | 2015-08-14 | Paper |
| scientific article; zbMATH DE number 6469130 (Why is no real title available?) | 2015-08-03 | Paper |
| Detecting short directed cycles using rectangular matrix multiplication and dynamic programming | 2015-08-03 | Paper |
A forward-backward single-source shortest paths algorithm
SIAM Journal on Computing | 2015-06-11 | Paper |
Approximate distance oracles
Proceedings of the thirty-third annual ACM symposium on Theory of computing | 2015-02-27 | Paper |
| Maximum matching in graphs with an excluded minor | 2014-12-18 | Paper |
| Deterministic rendezvous, treasure hunts and strongly universal exploration sequences | 2014-12-18 | Paper |
| All-pairs bottleneck paths in vertex weighted graphs | 2014-12-18 | Paper |
Discounted deterministic Markov decision processes and discounted all-pairs shortest paths
ACM Transactions on Algorithms | 2014-11-18 | Paper |
Efficient algorithms for the 2-gathering problem
ACM Transactions on Algorithms | 2014-11-18 | Paper |
Replacement paths and k simple shortest paths in unweighted directed graphs
ACM Transactions on Algorithms | 2014-09-09 | Paper |
Listing triangles
Automata, Languages, and Programming | 2014-07-01 | Paper |
Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor
Journal of the ACM | 2014-02-17 | Paper |
All-pairs shortest paths in \(O(n^2)\) time with high probability
(available as arXiv preprint) | 2014-02-17 | Paper |
Soft heaps simplified
SIAM Journal on Computing | 2013-11-14 | Paper |
Dynamic approximate all-pairs shortest paths in undirected graphs
SIAM Journal on Computing | 2012-09-12 | Paper |
On the approximability of reachability-preserving network orientations
Internet Mathematics | 2012-08-29 | Paper |
Maximum overhang
American Mathematical Monthly | 2012-01-01 | Paper |
On dynamic shortest paths problems
Algorithmica | 2011-09-20 | Paper |
All-pairs bottleneck paths in vertex weighted graphs
Algorithmica | 2011-03-30 | Paper |
Lower bounds for Howard's algorithm for finding minimum mean-cost cycles
Algorithms and Computation | 2010-12-09 | Paper |
A deterministic subexponential algorithm for solving parity games
Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 | 2010-08-16 | Paper |
Overhang
Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 | 2010-08-16 | Paper |
Spanners and emulators with sublinear distance errors
Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 | 2010-08-16 | Paper |
A fully dynamic reachability algorithm for directed graphs with an almost linear update time
Proceedings of the thirty-sixth annual ACM symposium on Theory of computing | 2010-08-15 | Paper |
| Maximum overhang | 2010-08-06 | Paper |
A Deterministic Subexponential Algorithm for Solving Parity Games
SIAM Journal on Computing | 2009-08-20 | Paper |
| Overhang | 2009-02-26 | Paper |
An Efficient Algorithm for the Nearly Equitable Edge Coloring Problem
Journal of Graph Algorithms and Applications | 2009-01-19 | Paper |
Approximate distance oracles
Journal of the ACM | 2008-12-21 | Paper |
Improved Dynamic Reachability Algorithms for Directed Graphs
SIAM Journal on Computing | 2008-10-28 | Paper |
New Bounds for the Nearly Equitable Edge Coloring Problem
Algorithms and Computation | 2008-05-27 | Paper |
Approximation and Online Algorithms
Lecture Notes in Computer Science | 2007-02-12 | Paper |
A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths
Algorithmica | 2006-11-06 | Paper |
Multicriteria global minimum cuts
Algorithmica | 2006-10-16 | Paper |
Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
Lecture Notes in Computer Science | 2006-07-07 | Paper |
Automata, Languages and Programming
Lecture Notes in Computer Science | 2006-01-10 | Paper |
Automata, Languages and Programming
Lecture Notes in Computer Science | 2006-01-10 | Paper |
