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, The Encyclopedia of Algorithms
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)



Journal Articles


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

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 Approximate and Exact Maximum Weight Matching
Ran Duan, Seth Pettie, and Hsin-Hao Su
arXiv:1112.0790


Conference Papers

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.