Seth Pettie

Leqi Zhu

J. ACM, April, 2024

Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies.

[BibT_eX]

[DOI]

Yaowei Long

Thatchaphol Saranurak

CoRR, 2024

Sketching, Moment Estimation, and the Lévy-Khintchine Representation Theorem.

[BibT_eX]

[DOI]

CoRR, 2024

Universal Perfect Samplers for Incremental Streams.

[BibT_eX]

[DOI]

CoRR, 2024

A Refutation of the Pach-Tardos Conjecture for 0-1 Matrices.

[BibT_eX]

[DOI]

Gábor Tardos

CoRR, 2024

Fourier Transform-based Estimators for Data Sketches.

[BibT_eX]

[DOI]

CoRR, 2024

Connectivity Labeling and Routing with Multiple Vertex Failures.

[BibT_eX]

[DOI]

Merav Parter

Asaf Petruschka

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

On the Extremal Functions of Acyclic Forbidden 0-1 Matrices.

[BibT_eX]

[DOI]

Gábor Tardos

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Sorting Pattern-Avoiding Permutations via 0-1 Matrices Forbidding Product Patterns.

[BibT_eX]

[DOI]

Parinya Chalermsook

Sorrachai Yingchareonthawornchai

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Fraud Detection for Random Walks.

[BibT_eX]

[DOI]

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

2023

Wake up and join me! An energy-efficient algorithm for maximal matching in radio networks.

[BibT_eX]

[DOI]

Distributed Comput., September, 2023

Almost Optimal Exact Distance Oracles for Planar Graphs.

[BibT_eX]

[DOI]

Panagiotis Charalampopoulos

Christian Wulff-Nilsen

J. ACM, April, 2023

Fully Dynamic Connectivity in O(log n(loglog n)2) Amortized Expected Time.

[BibT_eX]

[DOI]

TheoretiCS, 2023

Connectivity Labeling for Multiple Vertex Failures.

[BibT_eX]

[DOI]

Merav Parter

Asaf Petruschka

CoRR, 2023

Better Cardinality Estimators for HyperLogLog, PCSA, and Beyond.

[BibT_eX]

[DOI]

Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2023

2022

Simpler and Better Cardinality Estimators for HyperLogLog and PCSA.

[BibT_eX]

[DOI]

CoRR, 2022

Approximate Generalized Matching: f-Matchings and f-Edge Covers.

[BibT_eX]

[DOI]

Dawei Huang

Algorithmica, 2022

Optimal vertex connectivity oracles.

[BibT_eX]

[DOI]

Thatchaphol Saranurak

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Byzantine agreement in polynomial time with near-optimal resilience.

[BibT_eX]

[DOI]

Leqi Zhu

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

2021

Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing Shortcuts.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2021

The Communication Complexity of Set Intersection and Multiple Equality Testing.

[BibT_eX]

[DOI]

SIAM J. Comput., 2021

Near-optimal Distributed Triangle Enumeration via Expander Decompositions.

[BibT_eX]

[DOI]

Thatchaphol Saranurak

Hengjie Zhang

J. ACM, 2021

Information theoretic limits of cardinality estimation: Fisher meets Shannon.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Planar Distance Oracles with Better Time-Space Tradeoffs.

[BibT_eX]

[DOI]

Yaowei Long

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Brief Announcement: Wake Up and Join Me! An Energy Efficient Algorithm for Maximal Matching in Radio Networks.

[BibT_eX]

[DOI]

Proceedings of the PODC '21: ACM Symposium on Principles of Distributed Computing, 2021

The Structure of Minimum Vertex Cuts.

[BibT_eX]

[DOI]

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Non-Mergeable Sketching for Cardinality Estimation.

[BibT_eX]

[DOI]

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Incremental SCC Maintenance in Sparse Graphs.

[BibT_eX]

[DOI]

Aaron Bernstein

Aditi Dudeja

Proceedings of the 29th Annual European Symposium on Algorithms, 2021

2020

Distributed Edge Coloring and a Special Case of the Constructive Lovász Local Lemma.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2020

Connectivity Oracles for Graphs Subject to Vertex Failures.

[BibT_eX]

[DOI]

SIAM J. Comput., 2020

Distributed (Δ+1)-Coloring via Ultrafast Graph Shattering.

[BibT_eX]

[DOI]

Wenzheng Li

SIAM J. Comput., 2020

Simple and Efficient Cardinality Estimation in Data Streams.

[BibT_eX]

[DOI]

CoRR, 2020

Contention resolution without collision detection.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

The Energy Complexity of BFS in Radio Networks.

[BibT_eX]

[DOI]

Proceedings of the PODC '20: ACM Symposium on Principles of Distributed Computing, 2020

2019

Exponential Separations in the Energy Complexity of Leader Election.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2019

A Time Hierarchy Theorem for the LOCAL Model.

[BibT_eX]

[DOI]

SIAM J. Comput., 2019

An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model.

[BibT_eX]

[DOI]

SIAM J. Comput., 2019

Join on Samples: A Theoretical Guide for Practitioners.

[BibT_eX]

[DOI]

Proc. VLDB Endow., 2019

Thorup-Zwick emulators are universally optimal hopsets.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2019

Joins on Samples: A Theoretical Guide for Practitioners.

[BibT_eX]

[DOI]

CoRR, 2019

Mind the Gap! - Online Dictionary Matching with One Gap.

[BibT_eX]

[DOI]

Algorithmica, 2019

Distributed Triangle Detection via Expander Decomposition.

[BibT_eX]

[DOI]

Hengjie Zhang

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Simple Contention Resolution via Multiplicative Weight Updates.

[BibT_eX]

[DOI]

Wenyu Jin

Proceedings of the 2nd Symposium on Simplicity in Algorithms, 2019

2018

Scaling Algorithms for Weighted Matching in General Graphs.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2018

Contention Resolution with Constant Throughput and Log-Logstar Channel Accesses.

[BibT_eX]

[DOI]

SIAM J. Comput., 2018

A Hierarchy of Lower Bounds for Sublinear Additive Spanners.

[BibT_eX]

[DOI]

Amir Abboud

Greg Bodwin

SIAM J. Comput., 2018

Threesomes, Degenerates, and Love Triangles.

[BibT_eX]

[DOI]

Allan Grønlund

J. ACM, 2018

Lower bounds on Davenport-Schinzel sequences via rectangular Zarankiewicz matrices.

[BibT_eX]

[DOI]

Julian Wellman

Discret. Math., 2018

A resource-competitive jamming defense.

[BibT_eX]

[DOI]

Distributed Comput., 2018

An optimal distributed (Δ+1)-coloring algorithm?

[BibT_eX]

[DOI]

Wenzheng Li

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

The Complexity of Distributed Edge Coloring with Small Palettes.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

The Energy Complexity of Broadcast.

[BibT_eX]

[DOI]

Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

Improved Bounds for Multipass Pairing Heaps and Path-Balanced Binary Search Trees.

[BibT_eX]

[DOI]

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

Fine-grained Lower Bounds on Cops and Robbers.

[BibT_eX]

[DOI]

Sebastian Brandt

Jara Uitto

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

2017

Distributed algorithms for the Lovász local lemma and graph coloring.

[BibT_eX]

[DOI]

Kai-Min Chung

Distributed Comput., 2017

Approximate Generalized Matching: $f$-Factors and $f$-Edge Covers.

[BibT_eX]

[DOI]

Dawei Huang

CoRR, 2017

Fully Dynamic Connectivity in O(log n(log log n)2) Amortized Expected Time.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Simultaneously Load Balancing for Every p-norm, With Reassignments.

[BibT_eX]

[DOI]

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

2016

Single-Source Shortest Paths.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Minimum Spanning Trees.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

All Pairs Shortest Paths in Sparse Graphs.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs.

[BibT_eX]

[DOI]

Michael Elkin

ACM Trans. Algorithms, 2016

The Locality of Distributed Symmetry Breaking.

[BibT_eX]

[DOI]

J. ACM, 2016

Structure and Hardness in P (Dagstuhl Seminar 16451).

[BibT_eX]

[DOI]

Moshe Lewenstein

Virginia Vassilevska Williams

Dagstuhl Reports, 2016

Fully Dynamic Connectivity in O(log n(log log n)2) Amortized Expected Time.

[BibT_eX]

[DOI]

CoRR, 2016

How to Elect a Low-energy Leader.

[BibT_eX]

[DOI]

CoRR, 2016

Contention resolution with log-logstar channel accesses.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Higher Lower Bounds from the 3SUM Conjecture.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Brief Announcement: An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model.

[BibT_eX]

[DOI]

Casper Kejlberg-Rasmussen

Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

Mind the Gap: Essentially Optimal Algorithms for Online Dictionary Matching with One Gap.

[BibT_eX]

[DOI]

Proceedings of the 27th International Symposium on Algorithms and Computation, 2016

Faster Worst Case Deterministic Dynamic Connectivity.

[BibT_eX]

[DOI]

Mikkel Thorup

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

2015

Resource-Competitive Algorithms.

[BibT_eX]

[DOI]

SIGACT News, 2015

Three Generalizations of Davenport-Schinzel Sequences.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2015

Sensitivity Analysis of Minimum Spanning Trees in Sub-Inverse-Ackermann Time.

[BibT_eX]

[DOI]

J. Graph Algorithms Appl., 2015

Sharp Bounds on Davenport-Schinzel Sequences of Every Order.

[BibT_eX]

[DOI]

J. ACM, 2015

Improved Distributed Approximate Matching.

[BibT_eX]

[DOI]

Zvi Lotker

Boaz Patt-Shamir

J. ACM, 2015

Distributed coloring algorithms for triangle-free graphs.

[BibT_eX]

[DOI]

Casper Kejlberg-Rasmussen

Inf. Comput., 2015

Deterministic Worst Case Dynamic Connectivity: Simpler and Faster.

[BibT_eX]

[DOI]

Mikkel Thorup

CoRR, 2015

Online Dictionary Matching with One Gap.

[BibT_eX]

[DOI]

CoRR, 2015

Dynamic Set Intersection.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures - 14th International Symposium, 2015

Sharp Bounds on Formation-free Sequences.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

(2Δ - l)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting.

[BibT_eX]

[DOI]

Michael Elkin

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

2014

Linear-Time Approximation for Maximum Weight Matching.

[BibT_eX]

[DOI]

J. ACM, 2014

3SUM Hardness in (Dynamic) Data Structures.

[BibT_eX]

[DOI]

Casper Kejlberg-Rasmussen

CoRR, 2014

Word-packing Algorithms for Dynamic Connectivity and Dynamic Sets.

[BibT_eX]

[DOI]

CoRR, 2014

(Near) optimal resource-competitive broadcast with jamming.

[BibT_eX]

[DOI]

Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures, 2014

2013

Fast Distributed Coloring Algorithms for Triangle-Free Graphs.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012

Special Section on the Forty-Third Annual ACM Symposium on Theory of Computing (STOC 2011).

[BibT_eX]

[DOI]

SIAM J. Comput., 2012

A simple reduction from maximum weight matching to maximum cardinality matching.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2012

Tightish Bounds on Davenport-Schinzel Sequences

[BibT_eX]

[DOI]

CoRR, 2012

Fast Distributed Algorithms for Maximal Matching and Maximal Independent Set

[BibT_eX]

[DOI]

CoRR, 2012

Connectivity Oracles for Planar Graphs.

[BibT_eX]

[DOI]

Glencora Borradaile

Christian Wulff-Nilsen

Proceedings of the Algorithm Theory - SWAT 2012, 2012

2011

Origins of Nonlinearity in Davenport-Schinzel Sequences.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2011

Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts.

[BibT_eX]

[DOI]

J. Comb. Theory A, 2011

Degrees of nonlinearity in forbidden 0-1 matrix problems.

[BibT_eX]

[DOI]

Discret. Math., 2011

Scaling algorithms for approximate and exact maximum weight matching

[BibT_eX]

[DOI]

CoRR, 2011

On the structure and composition of forbidden sequences, with geometric applications.

[BibT_eX]

[DOI]

Proceedings of the 27th ACM Symposium on Computational Geometry, 2011

2010

Additive spanners and (alpha, beta)-spanners.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2010

Distributed algorithms for ultrasparse spanners and linear size skeletons.

[BibT_eX]

[DOI]

Distributed Comput., 2010

Connectivity oracles for failure prone graphs.

[BibT_eX]

[DOI]

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Applications of Forbidden 0-1 Matrices to Search Tree and Path Compression-Based Data Structures.

[BibT_eX]

[DOI]

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

On Nonlinear Forbidden 0-1 Matrices: A Refutation of a Füredi-Hajnal Conjecture.

[BibT_eX]

[DOI]

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Approximating Maximum Weight Matching in Near-Linear Time.

[BibT_eX]

[DOI]

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009

Low distortion spanners.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2009

Dual-failure distance and connectivity oracles.

[BibT_eX]

[DOI]

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths.

[BibT_eX]

[DOI]

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

2008

Single-Source Shortest Paths.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Minimum Spanning Trees.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

All Pairs Shortest Paths in Sparse Graphs.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Randomized minimum spanning tree algorithms using exponentially fewer random bits.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2008

Splay trees, Davenport-Schinzel sequences, and the deque conjecture.

[BibT_eX]

[DOI]

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Bounded-leg distance and reachability oracles.

[BibT_eX]

[DOI]

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Testudo: Heavyweight security analysis via statistical sampling.

[BibT_eX]

[DOI]

Proceedings of the 41st Annual IEEE/ACM International Symposium on Microarchitecture (MICRO-41 2008), 2008

Sources of Superlinearity in Davenport-Schinzel Sequences.

[BibT_eX]

[DOI]

Proceedings of the Data Structures, 17.02. - 22.02.2008, 2008

2006

An Inverse-Ackermann Type Lower Bound For Online Minimum Spanning Tree Verification.

[BibT_eX]

[DOI]

Comb., 2006

Towards a Final Analysis of Pairing Heaps.

[BibT_eX]

[DOI]

Proceedings of the Data Structures, 26.02. - 03.03.2006, 2006

2005

A Shortest Path Algorithm for Real-Weighted Undirected Graphs.

[BibT_eX]

[DOI]

SIAM J. Comput., 2005

The Complexity of Implicit and Space Efficient Priority Queues.

[BibT_eX]

[DOI]

Christian Worm Mortensen

Proceedings of the Algorithms and Data Structures, 9th International Workshop, 2005

New constructions of (alpha, beta)-spanners and purely additive spanners.

[BibT_eX]

[DOI]

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

2004

A new approach to all-pairs shortest paths on real-weighted graphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2004

A simpler linear time 2/3-epsilon approximation for maximum weight matching.

[BibT_eX]

[DOI]

Peter Sanders

Inf. Process. Lett., 2004

2002

A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest.

[BibT_eX]

[DOI]

SIAM J. Comput., 2002

An optimal minimum spanning tree algorithm.

[BibT_eX]

[DOI]

J. ACM, 2002

The Dynamic Vertex Minimum Problem and Its Application to Clustering-Type Approximation Algorithms.

[BibT_eX]

[DOI]

Harold N. Gabow

Proceedings of the Algorithm Theory, 2002

Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms.

[BibT_eX]

[DOI]

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Computing shortest paths with comparisons and additions.

[BibT_eX]

[DOI]

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

On the Comparison-Addition Complexity of All-Pairs Shortest Paths.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 13th International Symposium, 2002

A Faster All-Pairs Shortest Path Algorithm for Real-Weighted Sparse Graphs.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

An Inverse-Ackermann Style Lower Bound for the Online Minimum Spanning Tree.

[BibT_eX]

[DOI]

Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

Experimental Evaluation of a New Shortest Path Algorithm.

[BibT_eX]

[DOI]