Seth Pettie

2260 Hayward St.
Department of EECS
University of Michigan
Ann Arbor, MI 48109

Office: CSE Building Room 3628
Phone: (734) 615-4210
Fax: (734) 763-1260



Curriculum Vitae: PDF



Professional Service:
Editorial Board, Algorithmica
Editorial Board, The Encyclopedia of Algorithms
PC 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2016)
PC 15th Scandinavian Symposium on Algorithm Theory (SWAT 2016)
PC 56th IEEE Symposium on Foundations of Computer Science (FOCS 2015)
PC 23rd European Symposium on Algorithms (ESA 2015)
PC 26th Int'l Symposium on Algorithms and Computation (ISAAC 2015)
PC 22nd Int'l Colloquium on Structural Information and Communication Complexity (SIROCCO 2015)
PC 26th ACM Symposium on Parallel Algorithms and Architectures (SPAA 2014)
PC 10th Annual Conference on Theory and Applications of Models of Computation (TAMC 2013)
PC 24th ACM-SIAM Symposium on Discrete Algorithms (SODA 2013)
PC 43rd Symposium on Theory of Computing (STOC 2011)
PC 36th Symposium on Mathematical Foundations of Computer Science (MFCS 2011)
PC 31st Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)
PC 25th Int'l Symposiums on Theoretical Aspects of Computer Science (STACS 2008)
PC 10th Workshop on Algorithm Engineering and Experiments (ALENEX 2008)
PC 15th European Symposium on Algorithms (part of ALGO 2007)
PC 18th Symposium on Discrete Algorithms (SODA 2007)
PC 32nd Int'l Colloquium on Automata, Languages, and Programming (ICALP 2005)
PC 7th Workshop on Algorithm Engineering and Experiments (ALENEX 2005)



Students and Postdocs

Hsin-Hao Su (Ph.D. 2015), now postdoc at MIT. Winner of the 2016 Principles of Distributed Computing Doctoral Dissertation Award.
Tsvi Kopelowitz (postdoc)
Ran Duan (Ph.D. 2011), now Assistant Professor at IIIS, Tsinghua University, formerly postdoc at Max Planck Institute for Computer Science.
Maxwell Young (postdoc), now Assistant Professor at Mississippi State University


Journal Articles

The Locality of Distributed Symmetry Breaking
Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider
J. ACM, to appear.
PDF, BibTex

A Linear Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs
Michael Elkin and Seth Pettie
ACM Transactions on Algorithms, to appear.

Sharp Bounds on Davenport-Schinzel Sequences of Every Order
Seth Pettie
J. ACM 62(5), Article 36, 2015.
PDF, BibTex

Improved Distributed Approximate Matching
Zvi Lotker, Boaz Patt-Shamir, and Seth Pettie
J. ACM 62(5), Article 38, 2015.
PDF, BibTex

Three Generalizations of Davenport-Schinzel Sequences
Seth Pettie
SIAM J. Discrete Mathematics 29(4):2189-2238, 2015.
PDF, BibTex

Sensitivity Analysis of Minimum Spanning Trees in Sub-Inverse-Ackermann Time
Seth Pettie
J. Graph Algorithms and Applications 19(1):375-391, 2015.
PDF, BibTex

Distributed Coloring Algorithms for Triangle-free Graphs
Seth Pettie and Hsin-Hao Su
Information and Compututation 243:263-280, 2015.
PDF, BibTex

Linear Time Approximation for Maximum Weight Matching
Ran Duan and Seth Pettie
J. ACM 61(1), Article 1, 2014.
PDF, BibTex

A Simple Reduction from Maximum Weight Matching to Maximum Cardinality Matching
Seth Pettie
Information Processing Letters 112(23):893-898, 2012.
PDF, BibTex

Degrees of Nonlinearity in Forbidden 0-1 Matrix Problems
Seth Pettie
Discrete Mathematics 311, pp. 2396-2410, 2011.
Journal submission: PDF, BibTex

Generalized Davenport-Schinzel Sequences and Their 0-1 Matrix Counterparts
Seth Pettie
J. Combinatorial Theory Series A 118(6):1863-1895, 2011.
PDF, BibTex

Origins of Nonlinearity in Davenport-Schinzel Sequences
Seth Pettie
SIAM J. Discrete Mathematics 25(1):211-233, 2011.
PDF, BibTex

Distributed Algorithms for Ultrasparse Spanners and Linear Size Skeletons
Seth Pettie
Distributed Computing 22(3):147-166, 2010.
PDF, BibTex

Low Distortion Spanners
Seth Pettie
ACM Transactions on Algorithms 6(1), 2009.
PDF, BibTex
A post-publication acknowledgment: Connection Scheme B was inspired by
an additive source-wise spanner due to M. Elkin (unpublished). In his
construction, for any set of sources S, the distances between pairs in S×S are
preserved to within +2 stretch; the size of the spanner is O(n|S|1/2). Theorem 4.2
generalizes this construction in multiple ways. One consequence is that
distances between pairs in S×V can be preserved to within +O(log n)
with the same size spanner.

Additive Spanners and (α, β)-Spanners
S. Baswana, T. Kavitha, K. Mehlhorn, and Seth Pettie
ACM Transactions on Algorithms 7(1), 2010.
PDF, BibTex

Randomized Minimum Spanning Tree Algorithms Using Exponentially Fewer Random Bits
Seth Pettie and Vijaya Ramachandran
ACM Transactions on Algorithms 4(1):1-27, 2008.
PDF, BibTex

A Shortest Path Algorithm for Real-Weighted Undirected Graphs
Seth Pettie and Vijaya Ramachandran
SIAM J. Comput. 34(6):1398-1431, 2005.
Link to article, PDF, BibTeX

An Inverse-Ackermann Type Lower Bound for Online Minimum Spanning Tree Verification
Seth Pettie
Combinatorica 26(2):207-230, 2006.
PostScript, PDF, BibTex

A Simpler Linear Time 2/3 - ε Approximation for Maximum Weight Matching
Seth Pettie and Peter Sanders
Information Processing Letters 91(6):271-276, 2004.
PostScript, PDF, BibTex

A New Approach to All-Pairs Shortest Paths on Real-Weighted Graphs
Seth Pettie
Theoretical Computer Science, special issue on papers from ICALP 2002, 312(1):47-74, 2003.
Link to article, PostScript, PDF, BibTex

An Optimal Minimum Spanning Tree Algorithm
Seth Pettie and Vijaya Ramachandran
J. ACM 49(1):16-34, 2002.
Link to article, PostScript, PDF, BibTex

A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest
Seth Pettie and Vijaya Ramachandran
SIAM J. on Computing 31(6):1879-1895, 2002.
Link to article, PostScript, PDF, BibTex


Manuscripts / In Submission

Scaling Algorithms for Weighted Matching in General Graphs
Ran Duan, Seth Pettie, and Hsin-Hao Su
arXiv:1411.1919v3

Mind the Gap
Amihood Amir, Tsvi Kopelowitz, Avivit Levy, Seth Pettie, Ely Porat, and B. Riva Shalom
arXiv:1503.07563

Distributed Algorithms for the Lovász Local Lemma and Graph Coloring
Kai-Min Chung, Seth Pettie, and Hsin-Hao Su
PDF


Conference Papers

An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model
Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie
FOCS 2016
See arXiv:1602.08166

Faster Worst Case Deterministic Dynamic Connectivity
Casper Kejlberg-Rasmussen, Tsvi Kopelowitz, Seth Pettie, and Mikkel Thorup
ESA 2016
BibTex
See arXiv:1507.05944v2

Contention Resolution with Log-Logstar Channel Accesses
Michael Bender, Tsvi Kopelowitz, Seth Pettie, and Maxwell Young
STOC 2016
PDF, BibTex

Higher Lower Bounds from the 3SUM Conjecture
Tsvi Kopelowitz, Seth Pettie, and Ely Porat
SODA 2016
See arXiv:1407.6756

Dynamic Set Intersection
Tsvi Kopelowitz, Seth Pettie, and Ely Porat
WADS 2015
PDF, BibTex

(2Δ-1)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting
Michael Elkin, Seth Pettie, and Hsin-Hao Su
SODA 2015
PDF, BibTex

Sharp Bounds on Formation-free Sequences
Seth Pettie
SODA 2015
See journal version: Three Generalizations of Davenport-Schinzel Sequences.

A Linear Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs
Michael Elkin and Seth Pettie
SODA 2015
PDF, BibTex

Threesomes, Degenerates, and Love Triangles
Allan Grønlund, Seth Pettie
FOCS 2014
arXiv:1404.0799

Distributed Algorithms for the Lovász Local Lemma and Graph Coloring
Kai-Min Chung, Seth Pettie, and Hsin-Hao Su
PODC 2014
PDF, BibTex

(Near) Optimal Resource-Competitive Broadcast with Jamming
Seth Gilbert, Valerie King, Seth Pettie, Ely Porat, Jared Saia, and Maxwell Young
SPAA 2014
PDF, BibTex

Sharp Bounds on Davenport-Schinzel Sequences of Every Order
Seth Pettie
SoCG 2013
PDF, BibTex
Conference presentation (extended) PPTX

Fast Distributed Coloring Algorithms for Triangle-Free Graphs
Seth Pettie and Hsin-Hao Su
ICALP 2013
PDF, BibTex

The Locality of Distributed Symmetry Breaking
Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider
FOCS 2012
PDF, BibTex

Connectivity Oracles for Planar Graphs
Glencora Borradaile, Seth Pettie, and Christian Wulff-Nilsen
SWAT 2012
arXiv:1204.4159, BibTex

On the Structure and Composition of Forbidden Sequences, with Geometric Applications
Seth Pettie
SoCG 2011
PDF, BibTex

Approximating Maximum Weight Matching in Near-linear Time
Ran Duan and Seth Pettie
FOCS 2010
PDF, BibTex

Connectivity Oracles for Failure Prone Graphs
Ran Duan and Seth Pettie
STOC 2010
Conference version: PDF, BibTex

On Nonlinear Forbidden 0-1 Matrices: A Refutation of a Furedi-Hajnal Conjecture
Seth Pettie
SODA 2010
Conference version: PDF, BibTex

Applications of Forbidden 0-1 Matrices to Search Tree- and Path Compression-Based Data Structures
Seth Pettie
SODA 2010
Conference version: PDF, BibTex

Fast Algorithms for (Max,Min)-Matrix Multiplication and Bottleneck Shortest Paths
Ran Duan and Seth Pettie
SODA 2009
Conference version: PDF, BibTex

Dual-Failure Distance and Connectivity Oracles
Ran Duan and Seth Pettie
SODA 2009
Conference version: PDF, BibTex

Distributed Algorithms for Ultrasparse Spanners and Linear Size Skeletons
Seth Pettie
PODC 2008
[see journal version] BibTex

Improved Distributed Approximate Matching
Zvi Lotker, Boaz Patt-Shamir, Seth Pettie
SPAA 2008
Conference version: PDF, BibTex

Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture
Seth Pettie
SODA 2008
Preliminary Draft: PDF, BibTex

Bounded-leg Distance and Reachability Oracles
Ran Duan and Seth Pettie
SODA 2008
Preliminary Draft: PDF, BibTex

Low Distortion Spanners
Seth Pettie
ICALP 2007
Conference version: PDF, BibTex

Sensitivity Analysis of Minimum Spanning Trees in Sub-Inverse-Ackermann Time
Seth Pettie
ISAAC 2005
Conference submission: Postscript, BibTex

Towards a Final Analysis of Pairing Heaps
Seth Pettie
FOCS 2005
Conference version: PDF, BibTex

The Complexity of Implicit and Space-Efficient Priority Queues
Christian Mortensen and Seth Pettie
WADS 2005
Conference Version: PostScript, BibTex

New Constructions of (α, β)-Spanners and Purely Additive Spanners
S. Baswana, T. Kavitha, K. Mehlhorn, and Seth Pettie
Proceedings 16th Symposium on Discrete Algorithms (SODA 2005)
[see journal submission]

On the Comparison-Addition Complexity of All-pairs Shortest Paths
Seth Pettie
13th Annual International Symposium on Algorithms and Computation (ISAAC 2002).
Conference Paper: PostScript, PDF, BibTex
(See my Ph.D. thesis for the best exposition of this result.)

An Inverse-Ackermann Style Lower Bound for the Online Minimum Spanning Tree Verification Problem
Seth Pettie
43rd Annual Symposium on Foundations of Computer Science (FOCS 2002)
[see journal version]

A Faster All-Pairs Shortest Path Algorithm for Real-Weighted Sparse Graphs
Seth Pettie
Proceedings 29th Int'l Colloq. on Automata, Languages, and Programming (ICALP 2002).
Received Best Student Paper Award
[see journal version]

The Dynamic Vertex Minimum Problem and its Application to Clustering-type Approximation Algorithms
Harold Gabow and Seth Pettie
Proceedings 8th Scandinavian Workshop on Algorithm Theory (SWAT 2002).
Link to paper, PostScript, PDF, BibTex
[See Technical Report]

Experimental Evaluation of a New Shortest Path Algorithm
Seth Pettie, Vijaya Ramachandran, and Srinath Sridhar
Proceedings 4th Workshop on Algorithm Engineering and Experiments (ALENEX 2002).
Link to paper, PostScript, PDF, BibTex

Minimizing Randomness in Minimum Spanning Tree, Parallel Connectivity, and Set Maxima Algorithms
Seth Pettie and Vijaya Ramachandran
Proceedings 13th Symposium on Discrete Algorithms (SODA 2002)
[see journal version]

Computing Shortest Paths with Comparisons and Additions
Seth Pettie and Vijaya Ramachandran
Proceedings 13th Symposium on Discrete Algorithms (SODA 2002)
[see journal version]

An Optimal Minimum Spanning Tree Algorithm
Seth Pettie and Vijaya Ramachandran
Proceedings 27th Int'l Colloq. on Automata, Languages, and Programming (ICALP 2000)
Received Best Paper Award
[see journal version]

A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest
Seth Pettie and Vijaya Ramachandran
Proceedings 3rd Int'l Workshop on Randomization and Approximation in Computer Science RANDOM 1999
[see journal version]



Theses and Technical Reports

On the Shortest Path and Minimum Spanning Tree Problems
PDF, BibTex
Received The Outstanding Dissertation Award from The University of Texas Graduate School, 2004.

The Dynamic Vertex Minimum Problem and its Application to Clustering-type Approximation Algorithms
Harold Gabow and Seth Pettie
Technical Report: PostScript, PDF, BibTex

Finding Minimum Spanning Trees in O(m α(m,n)) Time
Seth Pettie
Technical Report: PostScript, PDF, BibTex


Other

A bibliography of papers on graph matching and related topics. Some of these articles were rather difficult to obtain, so I thought I'd save you the trouble and collect them in one tidy list.



Some travel photos