Seth Pettie

Orcid: 0000-0002-2610-1630

Affiliations:
  • University of Michigan, Ann Arbor, USA


According to our database1, Seth Pettie authored at least 124 papers between 2002 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Fraud Detection for Random Walks.
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.
Distributed Comput., September, 2023

Almost Optimal Exact Distance Oracles for Planar Graphs.
J. ACM, April, 2023

Fully Dynamic Connectivity in O(log n(loglog n)<sup>2</sup>) Amortized Expected Time.
TheoretiCS, 2023

Connectivity Labeling for Multiple Vertex Failures.
CoRR, 2023

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

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

Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Better Cardinality Estimators for HyperLogLog, PCSA, and Beyond.
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.
CoRR, 2022

Approximate Generalized Matching: f-Matchings and f-Edge Covers.
Algorithmica, 2022

Optimal vertex connectivity oracles.
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.
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.
SIAM J. Discret. Math., 2021

The Communication Complexity of Set Intersection and Multiple Equality Testing.
SIAM J. Comput., 2021

Near-optimal Distributed Triangle Enumeration via Expander Decompositions.
J. ACM, 2021

Information theoretic limits of cardinality estimation: Fisher meets Shannon.
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Planar Distance Oracles with Better Time-Space Tradeoffs.
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.
Proceedings of the PODC '21: ACM Symposium on Principles of Distributed Computing, 2021

The Structure of Minimum Vertex Cuts.
Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Non-Mergeable Sketching for Cardinality Estimation.
Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Incremental SCC Maintenance in Sparse Graphs.
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.
ACM Trans. Algorithms, 2020

Connectivity Oracles for Graphs Subject to Vertex Failures.
SIAM J. Comput., 2020

Distributed (Δ+1)-Coloring via Ultrafast Graph Shattering.
SIAM J. Comput., 2020

Simple and Efficient Cardinality Estimation in Data Streams.
CoRR, 2020

Contention resolution without collision detection.
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

The Energy Complexity of BFS in Radio Networks.
Proceedings of the PODC '20: ACM Symposium on Principles of Distributed Computing, 2020

2019
Exponential Separations in the Energy Complexity of Leader Election.
ACM Trans. Algorithms, 2019

A Time Hierarchy Theorem for the LOCAL Model.
SIAM J. Comput., 2019

An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model.
SIAM J. Comput., 2019

Join on Samples: A Theoretical Guide for Practitioners.
Proc. VLDB Endow., 2019

Thorup-Zwick emulators are universally optimal hopsets.
Inf. Process. Lett., 2019

Joins on Samples: A Theoretical Guide for Practitioners.
CoRR, 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
Scaling Algorithms for Weighted Matching in General Graphs.
ACM Trans. Algorithms, 2018

Contention Resolution with Constant Throughput and Log-Logstar Channel Accesses.
SIAM J. Comput., 2018

A Hierarchy of Lower Bounds for Sublinear Additive Spanners.
SIAM J. Comput., 2018

Threesomes, Degenerates, and Love Triangles.
J. ACM, 2018

Lower bounds on Davenport-Schinzel sequences via rectangular Zarankiewicz matrices.
Discret. Math., 2018

A resource-competitive jamming defense.
Distributed Comput., 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
Distributed algorithms for the Lovász local lemma and graph coloring.
Distributed Comput., 2017

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

Fully Dynamic Connectivity in <i>O</i>(log <i>n</i>(log log <i>n</i>)<sup>2</sup>) Amortized Expected Time.
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

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

A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs.
ACM Trans. Algorithms, 2016

The Locality of Distributed Symmetry Breaking.
J. ACM, 2016

Structure and Hardness in P (Dagstuhl Seminar 16451).
Dagstuhl Reports, 2016

Fully Dynamic Connectivity in O(log n(log log n)<sup>2</sup>) Amortized Expected Time.
CoRR, 2016

How to Elect a Low-energy Leader.
CoRR, 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

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. Discret. Math., 2015

Sensitivity Analysis of Minimum Spanning Trees in Sub-Inverse-Ackermann Time.
J. Graph Algorithms Appl., 2015

Sharp Bounds on Davenport-Schinzel Sequences of Every Order.
J. ACM, 2015

Improved Distributed Approximate Matching.
J. ACM, 2015

Distributed coloring algorithms for triangle-free graphs.
Inf. Comput., 2015

Deterministic Worst Case Dynamic Connectivity: Simpler and Faster.
CoRR, 2015

Online Dictionary Matching with One Gap.
CoRR, 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

2014
Linear-Time Approximation for Maximum Weight Matching.
J. ACM, 2014

3SUM Hardness in (Dynamic) Data Structures.
CoRR, 2014

Word-packing Algorithms for Dynamic Connectivity and Dynamic Sets.
CoRR, 2014

(Near) optimal resource-competitive broadcast with jamming.
Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures, 2014

2013
Fast Distributed Coloring Algorithms for Triangle-Free Graphs.
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).
SIAM J. Comput., 2012

A simple reduction from maximum weight matching to maximum cardinality matching.
Inf. Process. Lett., 2012

Tightish Bounds on Davenport-Schinzel Sequences
CoRR, 2012

Fast Distributed Algorithms for Maximal Matching and Maximal Independent Set
CoRR, 2012

Connectivity Oracles for Planar Graphs.
Proceedings of the Algorithm Theory - SWAT 2012, 2012

2011
Origins of Nonlinearity in Davenport-Schinzel Sequences.
SIAM J. Discret. 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.
Discret. Math., 2011

Scaling algorithms for approximate and exact maximum weight matching
CoRR, 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

Distributed algorithms for ultrasparse spanners and linear size skeletons.
Distributed Comput., 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
Low distortion spanners.
ACM Trans. Algorithms, 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

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

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

2006
An Inverse-Ackermann Type Lower Bound For Online Minimum Spanning Tree Verification.
Comb., 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

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
A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest.
SIAM J. Comput., 2002

An optimal minimum spanning tree algorithm.
J. ACM, 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


  Loading...