# Seth Pettie

According to our database

Collaborative distances:

^{1}, Seth Pettie authored at least 87 papers between 1999 and 2019.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### On csauthors.net:

## Bibliography

2019

Thorup-Zwick emulators are universally optimal hopsets.

Inf. Process. Lett., 2019

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

Algorithmica, 2019

Distributed Triangle Detection via Expander Decomposition.

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

Simple Contention Resolution via Multiplicative Weight Updates.

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

2018

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

SIAM J. Comput., 2018

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

Discrete Mathematics, 2018

A resource-competitive jamming defense.

Distributed Computing, 2018

Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing shortcuts.

Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, 2018

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

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

The Complexity of Distributed Edge Coloring with Small Palettes.

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

The Energy Complexity of Broadcast.

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

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

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

Fine-grained Lower Bounds on Cops and Robbers.

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

2017

Exponential separations in the energy complexity of leader election.

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

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

Scaling Algorithms for Weighted Matching in General Graphs.

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

Connectivity Oracles for Graphs Subject to Vertex Failures.

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

A Hierarchy of Lower Bounds for Sublinear Additive Spanners.

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

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

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

A Time Hierarchy Theorem for the LOCAL Model.

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016

Single-Source Shortest Paths.

Encyclopedia of Algorithms, 2016

Minimum Spanning Trees.

Encyclopedia of Algorithms, 2016

All Pairs Shortest Paths in Sparse Graphs.

Encyclopedia of Algorithms, 2016

Structure and Hardness in P (Dagstuhl Seminar 16451).

Dagstuhl Reports, 2016

Contention resolution with log-logstar channel accesses.

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

Higher Lower Bounds from the 3SUM Conjecture.

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.

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.

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

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

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

Faster Worst Case Deterministic Dynamic Connectivity.

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

2015

Resource-Competitive Algorithms.

SIGACT News, 2015

Three Generalizations of Davenport-Schinzel Sequences.

SIAM J. Discrete Math., 2015

Distributed coloring algorithms for triangle-free graphs.

Inf. Comput., 2015

Dynamic Set Intersection.

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

Sharp Bounds on Formation-free Sequences.

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.

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

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

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

2014

Linear-Time Approximation for Maximum Weight Matching.

J. ACM, 2014

(Near) optimal resource-competitive broadcast with jamming.

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

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

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

Threesomes, Degenerates, and Love Triangles.

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

Fast Distributed Coloring Algorithms for Triangle-Free Graphs.

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

Sharp bounds on Davenport-Schinzel sequences of every order.

Proceedings of the Symposuim on Computational Geometry 2013, 2013

2012

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

SIAM J. Comput., 2012

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

Inf. Process. Lett., 2012

Connectivity Oracles for Planar Graphs.

Proceedings of the Algorithm Theory - SWAT 2012, 2012

The Locality of Distributed Symmetry Breaking.

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011

Origins of Nonlinearity in Davenport-Schinzel Sequences.

SIAM J. Discrete Math., 2011

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

J. Comb. Theory, Ser. A, 2011

Degrees of nonlinearity in forbidden 0-1 matrix problems.

Discrete Mathematics, 2011

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

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

2010

Additive spanners and (alpha, beta)-spanners.

ACM Trans. Algorithms, 2010

Connectivity oracles for failure prone graphs.

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.

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.

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

Approximating Maximum Weight Matching in Near-Linear Time.

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

2009

Dual-failure distance and connectivity oracles.

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

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

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

2008

Single-Source Shortest Paths.

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Minimum Spanning Trees.

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

All Pairs Shortest Paths in Sparse Graphs.

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Randomized minimum spanning tree algorithms using exponentially fewer random bits.

ACM Trans. Algorithms, 2008

Improved distributed approximate matching.

Proceedings of the SPAA 2008: Proceedings of the 20th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2008

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

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

Bounded-leg distance and reachability oracles.

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

Distributed algorithms for ultrasparse spanners and linear size skeletons.

Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing, 2008

Testudo: Heavyweight security analysis via statistical sampling.

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

Sources of Superlinearity in Davenport-Schinzel Sequences.

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

2007

Low Distortion Spanners.

Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

2006

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

Combinatorica, 2006

Towards a Final Analysis of Pairing Heaps.

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

2005

A Shortest Path Algorithm for Real-Weighted Undirected Graphs.

SIAM J. Comput., 2005

The Complexity of Implicit and Space Efficient Priority Queues.

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

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

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

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

Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

Towards a Final Analysis of Pairing Heaps.

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

2004

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

Theor. Comput. Sci., 2004

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

Inf. Process. Lett., 2004

2002

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

Proceedings of the Algorithm Theory, 2002

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

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

Computing shortest paths with comparisons and additions.

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

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

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

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

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

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

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

Experimental Evaluation of a New Shortest Path Algorithm.

Proceedings of the Algorithm Engineering and Experiments, 4th International Workshop, 2002

2000

An Optimal Minimum Spanning Tree Algorithm.

Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

1999

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

Proceedings of the Randomization, 1999