| Publication | Date of Publication | Type |
|---|
| An inverse-Ackermann style lower bound for the online minimum spanning tree verification problem | 2026-05-29 | Paper |
| Non-mergeable sketching for cardinality estimation | 2026-05-12 | Paper |
| The structure of minimum vertex cuts | 2026-05-12 | Paper |
Space complexity of vertex connectivity oracles
SIAM Journal on Computing | 2026-03-11 | Paper |
A refutation of the Pach-Tardos conjecture for 0-1 matrices
Combinatorica | 2026-01-20 | Paper |
| Fraud detection for random walks | 2025-11-04 | Paper |
| A time hierarchy theorem for the LOCAL model | 2025-08-06 | Paper |
| An exponential separation between randomized and deterministic complexity in the LOCAL model | 2025-08-06 | Paper |
| Threesomes, degenerates, and love triangles | 2025-08-05 | Paper |
| The locality of distributed symmetry breaking | 2025-05-05 | Paper |
| Approximating maximum weight matching in near-linear time | 2025-04-29 | Paper |
Byzantine agreement with optimal resilience via statistical fraud detection
Journal of the ACM | 2025-02-06 | Paper |
Almost optimal exact distance oracles for planar graphs
Journal of the ACM | 2025-02-05 | Paper |
| Sorting pattern-avoiding permutations via 0-1 matrices forbidding product patterns | 2024-11-28 | Paper |
| On the extremal functions of acyclic forbidden 0-1 matrices | 2024-11-28 | Paper |
| Simple contention resolution via multiplicative weight updates | 2024-08-26 | Paper |
Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
TheoretiCS | 2024-07-03 | Paper |
Brief Announcement: Wake Up and Join Me! An Energy Efficient Algorithm for Maximal Matching in Radio Networks
Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing | 2024-03-26 | Paper |
scientific article; zbMATH DE number 7788487 (Why is no real title available?)
(available as arXiv preprint) | 2024-01-15 | Paper |
| scientific article; zbMATH DE number 7774270 (Why is no real title available?) | 2023-12-08 | Paper |
Optimal vertex connectivity oracles
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
Byzantine agreement in polynomial time with near-optimal resilience
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
Information theoretic limits of cardinality estimation: Fisher meets Shannon
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
| Incremental SCC maintenance in sparse graphs | 2023-09-20 | Paper |
Wake up and join me! An energy-efficient algorithm for maximal matching in radio networks
Distributed Computing | 2023-09-11 | Paper |
| Sorting Pattern-Avoiding Permutations via 0-1 Matrices Forbidding Product Patterns | 2023-07-05 | Paper |
| On the Extremal Functions of Acyclic Forbidden 0-1 Matrices | 2023-06-28 | Paper |
Near-optimal Distributed Triangle Enumeration via Expander Decompositions
Journal of the ACM | 2022-12-08 | Paper |
| Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection | 2022-06-30 | Paper |
Approximate generalized matching: \(f\)-matchings and \(f\)-edge covers
Algorithmica | 2022-06-28 | Paper |
A resource-competitive jamming defense
Distributed Computing | 2022-02-15 | Paper |
Lower bounds on sparse spanners, emulators, and diameter-reducing shortcuts
SIAM Journal on Discrete Mathematics | 2021-10-18 | Paper |
| Fine-grained Lower Bounds on Cops and Robbers | 2021-08-04 | Paper |
Improved bounds for multipass pairing heaps and path-balanced binary search trees
(available as arXiv preprint) | 2021-08-04 | Paper |
The communication complexity of set intersection and multiple equality testing
SIAM Journal on Computing | 2021-04-14 | Paper |
The Energy Complexity of BFS in Radio Networks
Proceedings of the 39th Symposium on Principles of Distributed Computing | 2021-03-15 | Paper |
| The Structure of Minimum Vertex Cuts | 2021-02-12 | Paper |
The communication complexity of set intersection and multiple equality testing
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
Contention resolution without collision detection
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
Connectivity oracles for graphs subject to vertex failures
SIAM Journal on Computing | 2021-01-13 | Paper |
scientific article; zbMATH DE number 7238981 (Why is no real title available?)
(available as arXiv preprint) | 2020-08-25 | Paper |
Distributed (+1)-coloring via ultrafast graph shattering
SIAM Journal on Computing | 2020-05-28 | Paper |
Exponential Separations in the Energy Complexity of Leader Election
ACM Transactions on Algorithms | 2019-12-02 | Paper |
Distributed edge coloring and a special case of the constructive Lovász local lemma
ACM Transactions on Algorithms | 2019-12-02 | Paper |
Distributed triangle detection via expander decomposition
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
The energy complexity of broadcast
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing | 2019-09-19 | Paper |
An optimal distributed (+1)-coloring algorithm?
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
Mind the gap!
Algorithmica | 2019-05-17 | Paper |
| Fast algorithms for (, )-matrix multiplication and bottleneck shortest paths | 2019-05-06 | Paper |
| Dual-failure distance and connectivity oracles | 2019-05-06 | Paper |
An exponential separation between randomized and deterministic complexity in the LOCAL model
SIAM Journal on Computing | 2019-02-08 | Paper |
A time hierarchy theorem for the LOCAL model
SIAM Journal on Computing | 2019-01-14 | Paper |
Threesomes, degenerates, and love triangles
Journal of the ACM | 2018-12-06 | Paper |
Thorup-Zwick emulators are universally optimal hopsets
Information Processing Letters | 2018-12-05 | Paper |
A hierarchy of lower bounds for sublinear additive spanners
SIAM Journal on Computing | 2018-12-05 | Paper |
Scaling algorithms for weighted matching in general graphs
ACM Transactions on Algorithms | 2018-11-12 | Paper |
A linear-size logarithmic stretch path-reporting distance oracle for general graphs
ACM Transactions on Algorithms | 2018-11-05 | Paper |
Randomized minimum spanning tree algorithms using exponentially fewer random bits
ACM Transactions on Algorithms | 2018-11-05 | Paper |
Contention resolution with constant throughput and log-logstar channel accesses
SIAM Journal on Computing | 2018-10-11 | Paper |
Sharp bounds on Davenport-Schinzel sequences of every order
Journal of the ACM | 2018-08-02 | Paper |
Improved Distributed Approximate Matching
Journal of the ACM | 2018-08-02 | Paper |
Higher lower bounds from the 3SUM conjecture
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Connectivity oracles for graphs subject to vertex failures
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
Proceedings of the Twenty-Eighth 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 |
Scaling algorithms for weighted matching in general graphs
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Improved bounds for multipass pairing heaps and path-balanced binary search trees
(available as arXiv preprint) | 2018-06-22 | Paper |
Lower bounds on Davenport-Schinzel sequences via rectangular Zarankiewicz matrices
Discrete Mathematics | 2018-05-24 | Paper |
| Simultaneously load balancing for every p-norm, with reassignments | 2018-05-03 | Paper |
| Mind the gap: essentially optimal algorithms for online dictionary matching with one gap | 2018-04-19 | Paper |
scientific article; zbMATH DE number 6850477 (Why is no real title available?)
(available as arXiv preprint) | 2018-03-15 | Paper |
| scientific article; zbMATH DE number 6850477 (Why is no real title available?) | 2018-03-15 | Paper |
Faster worst case deterministic dynamic connectivity
(available as arXiv preprint) | 2018-03-02 | Paper |
(2-1)-edge-coloring is much easier than maximal matching in the distributed setting
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
Sharp bounds on formation-free sequences
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
Contention resolution with log-logstar channel accesses
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
Brief announcement: An exponential separation between randomized and deterministic complexity in the LOCAL model
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing | 2017-09-29 | Paper |
Distributed algorithms for the Lovász local lemma and graph coloring
Distributed Computing | 2017-09-04 | Paper |
Exponential separations in the energy complexity of leader election
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Three generalizations of Davenport-Schinzel sequences
SIAM Journal on Discrete Mathematics | 2015-11-18 | Paper |
An optimal minimum spanning tree algorithm
Journal of the ACM | 2015-10-30 | Paper |
Dynamic set intersection
Lecture Notes in Computer Science | 2015-10-30 | Paper |
Sensitivity analysis of minimum spanning trees in sub-inverse-Ackermann time
Journal of Graph Algorithms and Applications | 2015-10-29 | Paper |
Distributed algorithms for the Lovász local lemma and graph coloring
Proceedings of the 2014 ACM symposium on Principles of distributed computing | 2015-09-03 | Paper |
Distributed coloring algorithms for triangle-free graphs
Information and Computation | 2015-06-09 | Paper |
Sharp bounds on Davenport-Schinzel sequences of every order
Proceedings of the twenty-ninth annual symposium on Computational geometry | 2015-02-17 | Paper |
Distributed algorithms for ultrasparse spanners and linear size skeletons
Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing | 2014-12-12 | Paper |
Low distortion spanners
ACM Transactions on Algorithms | 2014-11-18 | Paper |
| New constructions of \(({\alpha}, {\beta})\)-spanners and purely additive spanners | 2014-10-13 | Paper |
Linear-time approximation for maximum weight matching
Journal of the ACM | 2014-09-12 | Paper |
Additive spanners and \(({\alpha}, {\beta})\)-spanners
ACM Transactions on Algorithms | 2014-09-09 | Paper |
Connectivity oracles for failure prone graphs
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
| On nonlinear forbidden 0--1 matrices, a refutation of a Füredi-Hajnal conjecture | 2014-05-22 | Paper |
| scientific article; zbMATH DE number 6297801 (Why is no real title available?) | 2014-05-22 | Paper |
On the structure and composition of forbidden sequences, with geometric applications
Proceedings of the twenty-seventh annual symposium on Computational geometry | 2014-03-24 | Paper |
Fast distributed coloring algorithms for triangle-free graphs
Automata, Languages, and Programming | 2013-08-07 | Paper |
Distributed algorithms for ultrasparse spanners and linear size skeletons
Distributed Computing | 2013-06-28 | Paper |
A simple reduction from maximum weight matching to maximum cardinality matching
Information Processing Letters | 2012-10-23 | Paper |
Connectivity Oracles for Planar Graphs
Algorithm Theory – SWAT 2012 | 2012-08-14 | Paper |
Degrees of nonlinearity in forbidden 0-1 matrix problems
Discrete Mathematics | 2012-04-13 | Paper |
