| Publication | Date of Publication | Type |
|---|
| 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 |
| 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 |
| A faster deterministic exponential time algorithm for energy games and mean payoff games | 2022-07-21 | Paper |
| scientific article; zbMATH DE number 7561588 (Why is no real title available?) | 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 |
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 |
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 |
| Efficient algorithms for the 2-gathering problem | 2019-05-06 | Paper |
| Discounted deterministic Markov decision processes and discounted all-pairs shortest paths | 2019-05-06 | Paper |
| A simpler implementation and analysis of Chazelle's soft heaps | 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 |
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 |
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 |
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 |
Adjacency labeling schemes and induced-universal graphs
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | 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 |
| scientific article; zbMATH DE number 6472582 (Why is no real title available?) | 2015-08-14 | Paper |
| Detecting short directed cycles using rectangular matrix multiplication and dynamic programming | 2015-08-03 | Paper |
| scientific article; zbMATH DE number 6469130 (Why is no real title available?) | 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 |
| Deterministic rendezvous, treasure hunts and strongly universal exploration sequences | 2014-12-18 | Paper |
| Maximum matching in graphs with an excluded minor | 2014-12-18 | Paper |
| All-pairs bottleneck paths in vertex weighted graphs | 2014-12-18 | Paper |
Efficient algorithms for the 2-gathering problem
ACM Transactions on Algorithms | 2014-11-18 | Paper |
Discounted deterministic Markov decision processes and discounted all-pairs shortest paths
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 |
All-pairs shortest paths in \(O(n^2)\) time with high probability
(available as arXiv preprint) | 2014-02-17 | 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 |
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 |
Spanners and emulators with sublinear distance errors
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 |
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 |
Automata, Languages and Programming
Lecture Notes in Computer Science | 2006-01-10 | Paper |
Algorithms and Computation
Lecture Notes in Computer Science | 2005-12-22 | Paper |
Algorithms and Computation
Lecture Notes in Computer Science | 2005-12-22 | Paper |
Algorithm Theory - SWAT 2004
Lecture Notes in Computer Science | 2005-09-07 | Paper |
Algorithms – ESA 2004
Lecture Notes in Computer Science | 2005-08-18 | Paper |
Algorithms – ESA 2004
Lecture Notes in Computer Science | 2005-08-18 | Paper |
Approximating MIN 2-SAT and MIN 3-SAT
Theory of Computing Systems | 2005-06-14 | Paper |
MAX CUT in cubic graphs
Journal of Algorithms | 2005-02-16 | Paper |
| scientific article; zbMATH DE number 2119703 (Why is no real title available?) | 2004-11-29 | Paper |
| scientific article; zbMATH DE number 2119746 (Why is no real title available?) | 2004-11-29 | Paper |
| scientific article; zbMATH DE number 2119758 (Why is no real title available?) | 2004-11-29 | Paper |
| scientific article; zbMATH DE number 2119704 (Why is no real title available?) | 2004-11-29 | Paper |
| scientific article; zbMATH DE number 2119667 (Why is no real title available?) | 2004-11-29 | Paper |
| scientific article; zbMATH DE number 2086914 (Why is no real title available?) | 2004-08-11 | Paper |
| scientific article; zbMATH DE number 2081093 (Why is no real title available?) | 2004-08-04 | Paper |
Reachability and Distance Queries via 2-Hop Labels
SIAM Journal on Computing | 2003-09-28 | Paper |
| Combinatorial approximation algorithms for the maximum directed cut problem | 2003-09-15 | Paper |
| scientific article; zbMATH DE number 1979522 (Why is no real title available?) | 2003-09-14 | Paper |
Connection caching: Model and algorithms.
Journal of Computer and System Sciences | 2003-08-19 | Paper |
On the number of ANDs versus the number of ORs in monotone Boolean circuits
Information Processing Letters | 2003-06-24 | Paper |
Coloring -colorable graphs using relatively small palettes
Journal of Algorithms | 2003-05-14 | Paper |
| scientific article; zbMATH DE number 1875406 (Why is no real title available?) | 2003-03-02 | Paper |
Cell identification codes for tracking mobile users
Wireless Networks | 2003-02-19 | Paper |
Competitive analysis of the LRFU paging algorithm
Algorithmica | 2002-12-01 | Paper |
Approximation algorithms for MAX-4-SAT and rounding procedures for semidefinite programs
Journal of Algorithms | 2002-12-01 | Paper |
| scientific article; zbMATH DE number 1830729 (Why is no real title available?) | 2002-11-18 | Paper |
| Coloring \(k\)-colorable graphs using smaller palettes | 2002-10-24 | Paper |
| scientific article; zbMATH DE number 1775443 (Why is no real title available?) | 2002-08-01 | Paper |
Which bases admit non-trivial shrinkage of formulae?
Computational Complexity | 2002-07-22 | Paper |
| scientific article; zbMATH DE number 1762086 (Why is no real title available?) | 2002-07-01 | Paper |
A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
Random Structures & Algorithms | 2002-07-01 | Paper |
Constructing worst case instances for semidefinite programming based approximation algorithms
SIAM Journal on Discrete Mathematics | 2002-04-23 | Paper |
| Which formulae shrink under random restrictions? | 2002-03-24 | Paper |
| Constructing worst case instances for semidefinite programming based approximation algorithms | 2002-01-30 | Paper |
Optimal randomized EREW PRAM algorithms for finding spanning forests
Journal of Algorithms | 2001-09-20 | Paper |
All-pairs small-stretch paths
Journal of Algorithms | 2001-07-23 | Paper |
On lower bounds for selecting the median
SIAM Journal on Discrete Mathematics | 2001-06-21 | Paper |
Median selection requires \((2+\varepsilon)n\) comparisons
SIAM Journal on Discrete Mathematics | 2001-06-21 | Paper |
All-Pairs Almost Shortest Paths
SIAM Journal on Computing | 2000-03-19 | Paper |
| scientific article; zbMATH DE number 1303558 (Why is no real title available?) | 2000-02-09 | Paper |
SOKOBAN and other motion planning problems
Computational Geometry | 2000-01-04 | Paper |
Selecting the Median
SIAM Journal on Computing | 1999-10-28 | Paper |
| scientific article; zbMATH DE number 1342131 (Why is no real title available?) | 1999-09-22 | Paper |
| scientific article; zbMATH DE number 1303607 (Why is no real title available?) | 1999-08-16 | Paper |
Amplification and percolation (probabilistic Boolean functions)
Proceedings., 33rd Annual Symposium on Foundations of Computer Science | 1999-03-01 | Paper |
Growth Functions and Automatic Groups
Experimental Mathematics | 1998-08-09 | Paper |
Growth Functions and Automatic Groups
Experimental Mathematics | 1998-08-09 | Paper |
Growth Functions and Automatic Groups
Experimental Mathematics | 1998-08-09 | Paper |
Color-coding
Journal of the ACM | 1998-01-28 | Paper |
An optimal randomised logarithmic time connectivity algorithm for the EREW PRAM
Journal of Computer and System Sciences | 1997-09-07 | Paper |
Amplification by Read-Once Formulas
SIAM Journal on Computing | 1997-08-17 | Paper |
Finding Even Cycles Even Faster
SIAM Journal on Discrete Mathematics | 1997-05-26 | Paper |
Finding and counting given length cycles
Algorithmica | 1997-03-06 | Paper |
The smallest networks on which the Ford-Fulkerson maximum flow procedure may fail to terminate
Theoretical Computer Science | 1997-02-28 | Paper |
The complexity of mean payoff games on graphs
Theoretical Computer Science | 1997-02-27 | Paper |
| scientific article; zbMATH DE number 910857 (Why is no real title available?) | 1996-12-12 | Paper |
Finding the n-th largest element
Combinatorica | 1996-10-07 | Paper |
A note on busy beavers and other creatures
Mathematical Systems Theory | 1996-08-05 | Paper |
| scientific article; zbMATH DE number 871942 (Why is no real title available?) | 1996-04-28 | Paper |
How Do Read-Once Formulae Shrink?
Combinatorics, Probability and Computing | 1995-07-02 | Paper |
Tighter Lower Bounds on the Exact Complexity of String Matching
SIAM Journal on Computing | 1995-03-27 | Paper |
Shallow circuits and concise formulae for multiple addition and multiplication
Computational Complexity | 1994-11-29 | Paper |
Faster Parallel String Matching via Larger Deterministic Samples
Journal of Algorithms | 1994-03-22 | Paper |
The memory game
Theoretical Computer Science | 1993-08-30 | Paper |
Shrinkage of de Morgan formulae under restriction
Random Structures & Algorithms | 1993-06-29 | Paper |
| scientific article; zbMATH DE number 176877 (Why is no real title available?) | 1993-05-18 | Paper |
A $4n$ Lower Bound on the Combinational Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean Functions
SIAM Journal on Computing | 1991-01-01 | Paper |
An extension of Khrapchenko's theorem
Information Processing Letters | 1991-01-01 | Paper |
On Nečiporuk's theorem for branching programs
Theoretical Computer Science | 1989-01-01 | Paper |
