| Publication | Date of Publication | Type |
|---|
| Map graphs in polynomial time | 2025-10-29 | Paper |
| Pseudorandom hashing for space-bounded computation with applications in streaming | 2025-08-15 | Paper |
| Locally uniform hashing | 2025-08-15 | Paper |
| Fitting distances by tree metrics minimizing the total error within a constant factor | 2025-08-13 | Paper |
| Random k-out subgraph leaves only O(n/k) inter-component edges | 2025-08-12 | Paper |
| Fast similarity sketching | 2025-08-06 | Paper |
| Heavy hitters via cluster-preserving clustering | 2025-08-06 | Paper |
| Hashing for statistics over k-partitions | 2025-08-05 | Paper |
| \(Sample(x) = (a \cdot x <= t)\) is a distinguisher with probability 1/8 | 2025-08-05 | Paper |
| Planar reachability in linear space and constant time | 2025-08-05 | Paper |
| Dynamic integer sets with optimal rank, select, and predecessor search | 2025-08-05 | Paper |
| Simple tabulation, fast expanders, double tabulation, and high independence | 2025-05-20 | Paper |
| A new infinity of distance oracles for sparse graphs | 2025-05-05 | Paper |
| Combinatorial coloring of 3-colorable graphs | 2025-05-05 | Paper |
Fitting distances by tree metrics minimizing the total error within a constant factor
Journal of the ACM | 2025-02-06 | Paper |
| Fully dynamic min-cut of superconstant size in subpolynomial time | 2024-11-28 | Paper |
| Optimal decremental connectivity in non-sparse graphs | 2024-11-14 | Paper |
| A sparse Johnson-Lindenstrauss transform using fast hashing | 2024-11-14 | Paper |
| Dijkstra's single source shortest path algorithm | 2024-10-28 | Paper |
Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
TheoretiCS | 2024-07-03 | Paper |
| Understanding the moments of tabulation hashing via chaoses | 2024-06-24 | Paper |
| Minimum-cost paths for electric cars | 2024-05-29 | Paper |
| Reconstructing the tree of life (fitting distances by tree metrics) (invited paper) | 2024-05-27 | Paper |
| Fully dynamic exact edge connectivity in sublinear time | 2024-05-14 | Paper |
Edge sampling and graph parameter estimation via vertex neighborhood accesses
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
Load balancing with dynamic set of balls and bins
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
How to cut corners and get bounded convex curvature
Discrete & Computational Geometry | 2023-05-12 | Paper |
Computing the agreement of trees with bounded degrees
Lecture Notes in Computer Science | 2023-05-08 | Paper |
On sums of monotone random integer variables
Electronic Communications in Probability | 2023-01-23 | Paper |
Optimal pointer algorithms for finding nearest common ancestors in dynamic trees
Algorithm Theory — SWAT'96 | 2022-12-09 | Paper |
Efficient preprocessing of simple binary pattern forests
Algorithm Theory — SWAT '94 | 2022-12-09 | Paper |
Finding cores of limited length
Lecture Notes in Computer Science | 2022-08-19 | Paper |
| scientific article; zbMATH DE number 7561588 (Why is no real title available?) | 2022-07-21 | Paper |
scientific article; zbMATH DE number 7525511 (Why is no real title available?)
(available as arXiv preprint) | 2022-05-11 | Paper |
Generalized dominators for structured programs
Static Analysis | 2022-02-16 | Paper |
Compact cactus representations of all non-trivial min-cuts
Discrete Applied Mathematics | 2021-09-15 | Paper |
Power of \(d\) choices with simple tabulation
(available as arXiv preprint) | 2021-07-28 | Paper |
Faster Algorithms for Edge Connectivity via Random 2-Out Contractions
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
Three-in-a-tree in near linear time
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
Fast hashing with strong concentration bounds
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
Disks in curves of bounded convex curvature
The American Mathematical Monthly | 2020-08-03 | Paper |
Non-empty bins with simple tabulation hashing
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Three-in-a-Tree in Near Linear Time
(available as arXiv preprint) | 2019-09-16 | Paper |
Tabulation based 5-universal hashing and linear probing
2010 Proceedings of the Twelfth Workshop on Algorithm Engineering and Experiments (ALENEX) | 2019-09-11 | Paper |
Fast fencing
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
More compact oracles for approximate distances in undirected planar graphs
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-05-15 | Paper |
Twisted tabulation hashing
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-05-15 | Paper |
| scientific article; zbMATH DE number 7051297 (Why is no real title available?) | 2019-05-06 | Paper |
| String hashing for linear probing | 2019-05-06 | Paper |
| Discounted deterministic Markov decision processes and discounted all-pairs shortest paths | 2019-05-06 | Paper |
Deterministic Edge Connectivity in Near-Linear Time
Journal of the ACM | 2019-02-25 | Paper |
Deterministic Edge Connectivity in Near-Linear Time
Journal of the ACM | 2019-02-25 | Paper |
Adjacency labeling schemes and induced-universal graphs
SIAM Journal on Discrete Mathematics | 2019-01-16 | Paper |
\texttt{Sample(x)=(a*x<=t)} is a distinguisher with probability \(1/8\)
SIAM Journal on Computing | 2018-12-19 | Paper |
Incremental exact min-cut in polylogarithmic amortized update time
ACM Transactions on Algorithms | 2018-11-13 | Paper |
Incremental exact min-cut in polylogarithmic amortized update time
ACM Transactions on Algorithms | 2018-11-13 | Paper |
Compact name-independent routing with minimum stretch
ACM Transactions on Algorithms | 2018-11-05 | 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 |
On the \(k\)-independence required by linear probing and minwise independence
ACM Transactions on Algorithms | 2018-10-30 | Paper |
| scientific article; zbMATH DE number 6931784 (Why is no real title available?) | 2018-09-04 | Paper |
Coloring 3-colorable graphs with less than \(n^{1/5}\) colors
Journal of the ACM | 2018-08-02 | Paper |
The power of two choices with simple tabulation
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Minimizing diameters of dynamic trees
Automata, Languages and Programming | 2018-07-04 | Paper |
| The entropy of backwards analysis | 2018-03-15 | Paper |
The entropy of backwards analysis
(available as arXiv preprint) | 2018-03-15 | Paper |
| Consistent hashing with bounded loads | 2018-03-15 | Paper |
Consistent hashing with bounded loads
(available as arXiv preprint) | 2018-03-15 | Paper |
| Dynamic bridge-finding in \(\tilde{O}(\log^2 n)\) amortized time | 2018-03-15 | Paper |
Dynamic bridge-finding in \(\tilde{O}(\log^2 n)\) amortized time
(available as arXiv preprint) | 2018-03-15 | Paper |
Faster worst case deterministic dynamic connectivity
(available as arXiv preprint) | 2018-03-02 | Paper |
| scientific article; zbMATH DE number 6846417 (Why is no real title available?) | 2018-03-02 | Paper |
| Finding the Maximum Subset with Bounded Convex Curvature | 2018-01-30 | Paper |
| scientific article; zbMATH DE number 6829368 (Why is no real title available?) | 2018-01-24 | Paper |
| Coloring 3-colorable graphs with \(o(n^{1/5})\) colors | 2017-03-03 | Paper |
Rounding algorithms for a geometric embedding of minimum multiway cut
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
Construction and impromptu repair of an MST in a distributed network with o(m) communication
Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing | 2016-03-23 | Paper |
RAM-efficient external memory sorting
Algorithmica | 2016-02-19 | Paper |
Maintaining information in fully dynamic trees with top trees
ACM Transactions on Algorithms | 2015-09-02 | Paper |
Black box for constant-time insertion in priority queues (note)
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 |
From independence to expansion and back again
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
Deterministic global minimum cut of a simple graph in near-linear time
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
| scientific article; zbMATH DE number 6472605 (Why is no real title available?) | 2015-08-14 | Paper |
| scientific article; zbMATH DE number 6472610 (Why is no real title available?) | 2015-08-14 | Paper |
| Tabulation based 4-universal hashing with applications to second moment estimation | 2015-08-03 | Paper |
| scientific article; zbMATH DE number 6469130 (Why is no real title available?) | 2015-08-03 | Paper |
Approximate distance oracles
Proceedings of the thirty-third annual ACM symposium on Theory of computing | 2015-02-27 | Paper |
Fully-dynamic MIN-cut
Proceedings of the thirty-third annual ACM symposium on Theory of computing | 2015-02-27 | Paper |
| scientific article; zbMATH DE number 6381684 (Why is no real title available?) | 2014-12-18 | Paper |
Time-space trade-offs for predecessor search
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
Discounted deterministic Markov decision processes and discounted all-pairs shortest paths
ACM Transactions on Algorithms | 2014-11-18 | Paper |
Near-optimal fully-dynamic graph connectivity
Proceedings of the thirty-second annual ACM symposium on Theory of computing | 2014-09-26 | Paper |
Tight(er) worst-case bounds on dynamic searching and priority queues
Proceedings of the thirty-second annual ACM symposium on Theory of computing | 2014-09-26 | Paper |
Approximately minwise independence with twisted tabulation
Algorithm Theory – SWAT 2014 | 2014-09-02 | Paper |
Changing base without losing space
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
Bottom-k and priority sampling, set similarity and subset sums with minimal independence
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2014-08-07 | Paper |
The minimum \(k\)-way cut of bounded size is fixed-parameter tractable
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
Algorithms and estimators for summarization of unaggregated data streams
Journal of Computer and System Sciences | 2014-06-10 | Paper |
Don't rush into a union, take time to find your roots
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
The power of simple tabulation hashing
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
| Regular expression matching with multi-strings and intervals | 2014-05-22 | Paper |
The power of simple tabulation hashing
Journal of the ACM | 2014-02-17 | Paper |
RAM-efficient external memory sorting
Lecture Notes in Computer Science | 2014-01-14 | Paper |
Intra-domain traffic engineering with shortest path routing protocols
Annals of Operations Research | 2013-08-08 | Paper |
Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation
SIAM Journal on Computing | 2012-08-10 | Paper |
Speeding up dynamic shortest-path algorithms
INFORMS Journal on Computing | 2012-07-28 | Paper |
| Combinatorial coloring of 3-colorable graphs | 2012-05-06 | Paper |
Efficient stream sampling for variance-optimal estimation of subset sums
SIAM Journal on Computing | 2012-02-11 | Paper |
Maximum overhang
American Mathematical Monthly | 2012-01-01 | Paper |
On the \(k\)-independence required by linear probing and minwise independence
Automata, Languages and Programming | 2010-09-07 | 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 |
Worst-case update times for fully-dynamic all-pairs shortest paths
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Integer priority queues with decrease key in constant time and the single source shortest paths problem
Proceedings of the thirty-fifth annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Space efficient dynamic stabbing with fast queries
Proceedings of the thirty-fifth annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
OPT versus LOAD in dynamic storage allocation
Proceedings of the thirty-fifth annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
| Maximum overhang | 2010-08-06 | Paper |
Intra-domain traffic engineering with shortest path routing protocols
4OR | 2010-06-16 | Paper |
Higher lower bounds for near-neighbor and further rich problems
SIAM Journal on Computing | 2010-04-29 | Paper |
Faster Regular Expression Matching
Automata, Languages and Programming | 2009-07-14 | Paper |
| scientific article; zbMATH DE number 5485527 (Why is no real title available?) | 2009-01-05 | Paper |
Approximate distance oracles
Journal of the ACM | 2008-12-21 | Paper |
Priority sampling for estimation of arbitrary subset sums
Journal of the ACM | 2008-12-21 | Paper |
Dynamic ordered sets with exponential search trees
Journal of the ACM | 2008-12-21 | Paper |
Equivalence between priority queues and sorting
Journal of the ACM | 2008-12-21 | Paper |
Learn More, Sample Less: Control of Volume and Variance in Network Measurement
IEEE Transactions on Information Theory | 2008-12-21 | Paper |
Oracles for Distances Avoiding a Failed Node or Link
SIAM Journal on Computing | 2008-10-28 | Paper |
On the Variance of Subset Sum Estimation
Algorithms – ESA 2007 | 2008-09-25 | Paper |
Compact Oracles for Approximate Distances Around Obstacles in the Plane
Algorithms – ESA 2007 | 2008-09-25 | Paper |
Does Path Cleaning Help in Dynamic All-Pairs Shortest Paths?
Lecture Notes in Computer Science | 2008-03-11 | Paper |
Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
Journal of the ACM | 2008-02-11 | Paper |
Compact oracles for reachability and approximate distances in planar digraphs
Journal of the ACM | 2008-01-14 | Paper |
Survivable IP network design with OSPF routing
Networks | 2007-02-02 | Paper |
Fast comparison of evolutionary trees
Information and Computation | 2006-10-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 |
Rounding algorithms for a geometric embedding of minimum multiway cut.
Mathematics of Operations Research | 2005-11-11 | Paper |
A hybrid genetic algorithm for the weight setting problem in OSPF/IS‐IS routing
Networks | 2005-09-22 | Paper |
Algorithm Theory - SWAT 2004
Lecture Notes in Computer Science | 2005-09-07 | 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 |
An Experimental Study of Polylogarithmic, Fully Dynamic, Connectivity Algorithms
ACM Journal of Experimental Algorithmics | 2005-08-04 | Paper |
<i>OPT</i>Versus<i>LOAD</i>in Dynamic Storage Allocation
SIAM Journal on Computing | 2005-02-21 | Paper |
Quick <i>k</i>-Median, <i>k</i>-Center, and Facility Location for Sparse Graphs
SIAM Journal on Computing | 2005-02-21 | Paper |
Undirected single-source shortest paths with positive integer weights in linear time
Journal of the ACM | 2005-01-25 | Paper |
Increasing internet capacity using local search
Computational Optimization and Applications | 2005-01-17 | Paper |
| scientific article; zbMATH DE number 2119746 (Why is no real title available?) | 2004-11-29 | Paper |
| scientific article; zbMATH DE number 2119745 (Why is no real title available?) | 2004-11-29 | Paper |
Integer priority queues with decrease key in constant time and the single source shortest paths problem
Journal of Computer and System Sciences | 2004-11-18 | Paper |
| scientific article; zbMATH DE number 2102755 (Why is no real title available?) | 2004-09-24 | Paper |
| scientific article; zbMATH DE number 2079401 (Why is no real title available?) | 2004-07-28 | Paper |
| scientific article; zbMATH DE number 2079337 (Why is no real title available?) | 2004-07-28 | Paper |
| scientific article; zbMATH DE number 1947376 (Why is no real title available?) | 2003-07-08 | Paper |
| scientific article; zbMATH DE number 1798166 (Why is no real title available?) | 2002-11-04 | Paper |
Randomized Sorting in O(nloglogn) Time and Linear Space Using Addition, Shift, and Bit-wise Boolean Operations
Journal of Algorithms | 2002-07-11 | Paper |
| scientific article; zbMATH DE number 1754597 (Why is no real title available?) | 2002-06-12 | Paper |
| scientific article; zbMATH DE number 1263249 (Why is no real title available?) | 2002-02-03 | Paper |
| Dynamic string searching | 2002-01-30 | Paper |
| scientific article; zbMATH DE number 1617242 (Why is no real title available?) | 2001-07-11 | Paper |
| scientific article; zbMATH DE number 1617247 (Why is no real title available?) | 2001-07-11 | Paper |
An \(O(n\log n)\) algorithm for the maximum agreement subtree problem for binary trees
SIAM Journal on Computing | 2001-03-19 | Paper |
On RAM Priority Queues
SIAM Journal on Computing | 2000-10-18 | Paper |
Generalized dominators for structured programs
Algorithmica | 2000-08-27 | Paper |
Floats, Integers, and Single Source Shortest Paths
Journal of Algorithms | 2000-06-05 | Paper |
Optimal Pointer Algorithms for Finding Nearest Common Ancestors in Dynamic Trees
Journal of Algorithms | 2000-06-05 | Paper |
| scientific article; zbMATH DE number 1445340 (Why is no real title available?) | 2000-05-10 | Paper |
| scientific article; zbMATH DE number 1445341 (Why is no real title available?) | 2000-05-10 | Paper |
Decremental Dynamic Connectivity
Journal of Algorithms | 2000-03-19 | Paper |
Dominators in Linear Time
SIAM Journal on Computing | 1999-10-28 | Paper |
| scientific article; zbMATH DE number 1303597 (Why is no real title available?) | 1999-08-16 | Paper |
| scientific article; zbMATH DE number 1303574 (Why is no real title available?) | 1999-06-17 | Paper |
Fusion trees can be implemented with AC^0 instructions only
Theoretical Computer Science | 1999-04-29 | Paper |
On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics)
SIAM Journal on Computing | 1999-02-22 | Paper |
All structured programs have small tree width and good register allocation
Information and Computation | 1998-11-10 | Paper |
String matching in Lempel-Ziv compressed strings
Algorithmica | 1998-05-24 | Paper |
| Sampling to provide or to bound: With applications to fully dynamic graph algorithms | 1998-05-13 | Paper |
| scientific article; zbMATH DE number 1107741 (Why is no real title available?) | 1998-01-21 | Paper |
| scientific article; zbMATH DE number 1775391 (Why is no real title available?) | 1998-01-01 | Paper |
Parallel Shortcutting of Rooted Trees
Journal of Algorithms | 1997-11-18 | Paper |
Sparse Dynamic Programming for Evolutionary-Tree Comparison
SIAM Journal on Computing | 1997-09-24 | Paper |
| scientific article; zbMATH DE number 1003280 (Why is no real title available?) | 1997-08-14 | Paper |
On the agreement of many trees
Information Processing Letters | 1997-02-27 | Paper |
| scientific article; zbMATH DE number 871934 (Why is no real title available?) | 1997-01-05 | Paper |
Efficient Preprocessing of Simple Binary Pattern Forests
Journal of Algorithms | 1996-12-11 | Paper |
Shortcutting Planar Digraphs
Combinatorics, Probability and Computing | 1996-06-05 | Paper |
| scientific article; zbMATH DE number 871900 (Why is no real title available?) | 1996-04-28 | Paper |
Disambiguating grammars by exclusion of sub-parse trees
Acta Informatica | 1995-11-16 | Paper |
| scientific article; zbMATH DE number 512931 (Why is no real title available?) | 1994-03-10 | Paper |
On conservative extensions of syntax in system development
Theoretical Computer Science | 1991-01-01 | Paper |
