| Publication | Date of Publication | Type |
|---|
| Hash functions bridging the gap from theory to practice (invited talk) | 2026-10-01 | Paper |
| Faster all-pairs optimal electric car routing | 2026-09-29 | Paper |
| A faster algorithm for constrained correlation clustering | 2026-06-24 | Paper |
| Equivalence between priority queues and sorting | 2026-05-29 | Paper |
| Integer sorting in \(O(n \sqrt{\log \log n})\) expected time and linear space | 2026-05-29 | Paper |
| Higher lower bounds for near-neighbor and further rich problems | 2026-05-29 | Paper |
| Undirected single source shortest paths in linear time | 2026-05-21 | Paper |
| Compact oracles for reachability and approximate distances in planar digraphs | 2026-05-08 | Paper |
| 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 |
Efficient preprocessing of simple binary pattern forests
Algorithm Theory — SWAT '94 | 2022-12-09 | Paper |
Optimal pointer algorithms for finding nearest common ancestors in dynamic trees
Algorithm Theory — SWAT'96 | 2022-12-09 | Paper |
Finding cores of limited length
Lecture Notes in Computer Science | 2022-08-19 | Paper |
| Dynamic ordered sets with approximate queries, approximate heaps and soft heaps | 2022-07-21 | Paper |
Hardness of bichromatic closest pair with Jaccard similarity
(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 |
Fast hashing with strong concentration bounds
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | 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 |
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 |
Twisted tabulation hashing
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-05-15 | 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 |
| String hashing for linear probing | 2019-05-06 | Paper |
| Discounted deterministic Markov decision processes and discounted all-pairs shortest paths | 2019-05-06 | Paper |
| Stream sampling for variance-optimal estimation of subset sums | 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 |
Roundtrip spanners and roundtrip routing in directed graphs
ACM Transactions on Algorithms | 2018-11-05 | Paper |
Compact name-independent routing with minimum stretch
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 |
Dynamic bridge-finding in \(\tilde{O}(\log^2 n)\) amortized time
(available as arXiv preprint) | 2018-03-15 | Paper |
| Dynamic bridge-finding in \(\tilde{O}(\log^2 n)\) amortized time | 2018-03-15 | Paper |
Consistent hashing with bounded loads
(available as arXiv preprint) | 2018-03-15 | Paper |
| Consistent hashing with bounded loads | 2018-03-15 | Paper |
The entropy of backwards analysis
(available as arXiv preprint) | 2018-03-15 | Paper |
| The entropy of backwards analysis | 2018-03-15 | Paper |
| scientific article; zbMATH DE number 6846417 (Why is no real title available?) | 2018-03-02 | Paper |
Faster worst case deterministic dynamic connectivity
(available as arXiv preprint) | 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 |
Black box for constant-time insertion in priority queues (note)
ACM Transactions on Algorithms | 2015-09-02 | Paper |
Maintaining information in fully dynamic trees with top trees
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 |
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 |
From independence to expansion and back again
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 |
| scientific article; zbMATH DE number 6469130 (Why is no real title available?) | 2015-08-03 | Paper |
| Tabulation based 4-universal hashing with applications to second moment estimation | 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 |
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 |
Near-optimal fully-dynamic graph connectivity
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 |
