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:
Steering Committee, SIAM Symposium on Simplicity in Algorithms (SOSA).
Co-chair, SOSA 2024 which will be co-located with SODA 2024 in Alexandria, VA.
Organizing Committee, Integer Programming and Combinatorial Optimization (IPCO 2019)
Editorial Board, Algorithmica
Editorial Board, The Encyclopedia of Algorithms
PC Member of SODA 2025, ICALP 2024, FOCS 2023, LATIN 2022, PODC 2022, SIROCCO 2022, SSS 2021, SODA 2021, ESA 2020, SWAT 2020, SSS 2019, STOC 2019, ISAAC 2018, SSS 2018, ITCS 2018, ICALP 2018, WADS 2017, STACS 2017, SPAA 2016, SWAT 2016, FOCS 2015, ESA 2015, ISAAC 2015, SIROCCO 2015, SPAA 2014, TAMC 2013, SODA 2013, STOC 2011, MFCS 2011, FSTTCS 2011, STACS 2008, ALENEX 2008, ESA 2007, SODA 2007, ICALP 2005, ALENEX 2005.

Together with M. Lewenstein and V. V. Williams I organized a Dagstuhl workshop on Structure and Hardness in P, which was held in November 2016. Feel free to solve any of the 26 Open Problems that came out of this workshop.

With R. Krauthgamer, B. Saha, and V. V. Williams I organized a Bertinoro Workshop on Fine-grained Approximation Algorithms and Complexity, held May 27-31, 2019.

With David Bevan, Miklós Bóna, and István Miklós I organized a Dagstuhl workshop on Pattern Avoidance, Statistical Mechanics, and Computational Complexity, held March 19-24, 2023.

Students, Postdocs, and Visitors

Dingyu Wang (Ph.D. student)
Leqi (Jimmy) Zhu (postdoc), postdoc @ IST Austria, Professor University of Manitoba.
Shang-En Huang (Ph.D 2022), now postdoc @ Boston College.
Ohad Trabelsi (postdoc), now Research Professor @ TTI-Chicago.
Dawei Huang (Ph.D. 2020), now @ Google.
Yi-Jun Chang (Ph.D. 2019), postdoc @ ETH Zurich, now Professor @ NUS Singapore. Winner of the 2020 Principles of Distributed Computing Doctoral Dissertation Award.
Hsin-Hao Su (Ph.D. 2015), postdoc @ MIT, now Professor @ Boston College. Winner of the 2016 Principles of Distributed Computing Doctoral Dissertation Award.
Tsvi Kopelowitz (postdoc), now Professor @ Bar-Ilan University.
Ran Duan (Ph.D. 2011), postdoc @ MPI, now Professor @ IIIS, Tsinghua University
Maxwell Young (postdoc), now Professor @ Mississippi State University.
Veronika Loitzenbauer, Visitor, June-August, 2016. Now researcher @ Johannes Kepler Universität Linz.
Julian Wellman, Greenhills High School. Summer 2016. Now Ph.D. student @ MIT Mathematics.
Ruosong Wang, Tsinghua University. Visitor, February-June, 2016. Ph.D. student @ Carnegie Mellon, Postdoc @ Univ. of Washington, Professor @ Peiking University.
Wei Zhan, Tsinghua University. Visitor, February-June, 2016. Ph.D. student @ Princeton University, Postdoc @ University of Chicago.
Qizheng He, Tsinghua University. Visitor, March-August, 2017. Ph.D. student @ UIUC now @ Huawei TopMinds.
Wenzheng Li, Tsinghua University. Visitor, March-August, 2017. Now Ph.D. student @ Stanford.
Hengjie Zhang, Tsinghua University. Visitor, March-August, 2018. Now Ph.D. student @ Columbia University.
Yixiang Zhang, Tsinghua University. Visitor, March-August, 2019.
Zhijun Zhang, Tsinghua University. Visitor, March-August, 2019. Now Ph.D. student @ Princeton University.
Longhui Yin, Tsinghua University. Visitor, February-August, 2020. Now Ph.D. student @ IIIS, Tsinghua.
Yaowei Long, Tsinghua University. Visitor, February-August, 2020. Now Ph.D. student @ University of Michigan.
Zhongtian He, Tsinghua University. February-August, 2021. Now Ph.D. student @ Princeton University.
Benyu Wang, Tsinghua University. Visitor, February-August, 2022. Now Ph.D. student @ University of Michigan.
Zhiyi Huang, Tsinghua University. Visitor, February-August, 2022. Now Ph.D. student @ UT Austin.


See my Google Scholar and DBLP pages for more citation information.

Conference Papers

Connectivity Labeling and Routing with Multiple Vertex Failures
Merav Parter, Asaf Petruschka, and Seth Pettie
STOC 2024
arXiv:2307.06276

Fraud Detection for Random Walks
Varsha Dani, Thomas Hayes, Seth Pettie, and Jared Saia
ITCS 2024
link to paper

On the Extremal Functions of Acyclic Forbidden 0-1 Matrices
Seth Pettie and Gabor Tardos
SODA 2024
arXiv:2306.16365

Sorting Pattern-Avoiding Permutations via 0-1 Matrices Forbidding Product Patterns
Parinya Chalermsook, Seth Pettie, and Sorrachai Yingchareonthawornchai
SODA 2024
arXiv:2307.02294

Better Cardinality Estimators for HyperLogLog, PCSA, and Beyond
Seth Pettie and Dingyu Wang
PODS 2023
arXiv:2208.10578

Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection
Shang-En Huang, Seth Pettie, and Leqi Zhu
SODA 2023
arXiv:2206.15335

Optimal Vertex Connectivity Oracles
Seth Pettie, Thatchaphol Saranurak, and Longhui Yin
STOC 2022
arXiv:2201.00408

Byzantine Agreement in Polynomial Time with Near-Optimal Resilience
Shang-En Huang, Seth Pettie Leqi Zhu
STOC 2022
arXiv:2202.13452

Incremental SCC Maintenance in Sparse Graphs
Aaron Bernstein, Aditi Dudeja, and Seth Pettie
ESA 2021
PDF.

Wake Up and Join Me! An Energy Efficient Algorithm for Maximal Matching in Radio Networks
Varsha Dani, Aayush Gupta, Thomas Hayes, and Seth Pettie
DISC 2021; Brief Announcement at PODC 2021.
arXiv:2104.09096

Non-mergeable Sketching for Cardinality Estimation
Seth Pettie, Dingyu Wang and Longhui Yin
ICALP 2021
arXiv:2008.08739

The Structure of Minimum Vertex Cuts
Seth Pettie and Longhui Yin
ICALP 2021
arXiv:2102.06805

Information Theoretic Limits of Cardinality Estimation: Fisher meets Shannon
Seth Pettie and Dingyu Wang
STOC 2021
arXiv:2007.06865

Distance Oracles for Planar Graphs with Better Time-Space Tradeoffs
Yaowei Long and Seth Pettie
SODA 2021
arXiv:2007.08585

Contention Resolution without Collision Detection
Michael Bender, Tsvi Kopelowitz, William Kuszmaul, Seth Pettie
STOC 2020

Join on Samples: A Theoretical Guide for Practitioners
Dawei Huang, Dong Young Yoon, Seth Pettie, and Barzan Mozafari
Presented at VLDB 2020

The Energy Complexity of BFS in Radio Networks
Yi-Jun Chang, Varsha Dani, Thomas Hayes, and Seth Pettie
PODC 2020
Publisher's website

The Communication Complexity of Set Intersection and Multiple Equality Testing
Dawei Huang, Seth Pettie, Yixiang Zhang, and Zhijun Zhang
SODA 2020
arXiv:1908.11825

Simple Contention Resolution via Multiplicative Weight Updates
Yi-Jun Chang, Wenyu Jin, and Seth Pettie
SOSA 2019
Proceedings

Distributed Triangle Detection via Expander Decomposition
Yi-Jun Chang, Seth Pettie, and Hengjie Zhang
SODA 2019
arXiv:1807.06624

Fine-grained Lower Bounds on Cops and Robbers
Sebastian Brandt, Seth Pettie, and Jara Uitto
ESA 2018

Improved Bounds for Multipass Pairing Heaps and Path-balanced Binary Search Trees
Dani Dorfman, Haim Kaplan, Laszlo Kozma, Seth Pettie, and Uri Zwick
ESA 2018

The Energy Complexity of Broadcast
Yi-Jun Chang, Varsha Dani, Thomas Hayes, Qizheng He, Wenzheng Li, and Seth Pettie
PODC 2018
arXiv:1710.01800

Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing Shortcuts
Shang-En Huang and Seth Pettie
SWAT 2018
arXiv:1802.06271

An Optimal Distributed (Δ +1)-Coloring Algorithm?
Yi-Jun Chang, Wenzheng Li, and Seth Pettie
STOC 2018
arXiv:1711.01361

The Complexity of Distributed Edge Coloring with Small Palettes
Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, and Jara Uitto
SODA 2018
arXiv:1708.04290

A Time Hierarchy Theorem for the LOCAL Model
Yi-Jun Chang and Seth Pettie
FOCS 2017
arXiv:1704.06297
A 1-hour version at TCS+.
Invited presentation (PDF) at HALG 2018.

Exponential Separations in the Energy Complexity of Leader Election
Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie, Ruosong Wang, Wei Zhan
STOC 2017
arXiv:1609.08486v2

Fully Dynamic Connectivity in O(log n (log log n)2) Amortized Expected Time
Shang-En Huang, Dawei Huang, Tsvi Kopelowitz, and Seth Pettie
SODA 2017
arXiv:1609.05867

A Hierarchy of Lower Bounds for Sublinear Additive Spanners
Amir Abboud, Greg Bodwin, and Seth Pettie
SODA 2017
arXiv:1607.07497

Connectivity Oracles for Graphs Subject to Vertex Failures
Ran Duan and Seth Pettie
SODA 2017
arXiv:1607.06865

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

Simultaneously Load Balancing for Every p-norm, With Reassignments
Aaron Bernstein, Tsvi Kopelowitz, Seth Pettie, Ely Porat, and Cliff Stein
ITCS 2017
PDF

Mind the Gap: Essentially Optimal Algorithms for Online Dictionary Matching with One Gap
Amihood Amir, Tsvi Kopelowitz, Avivit Levy, Seth Pettie, Ely Porat, and B. Riva Shalom
ISAAC 2016
arXiv:1503.07563

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

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

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

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

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

(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

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
See journal version.

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
See journal submission.
PDF

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

Sharp Bounds on Davenport-Schinzel Sequences of Every Order
Seth Pettie
SoCG 2013
See journal version.
Conference presentation (extended) PPTX

Fast Distributed Coloring Algorithms for Triangle-Free Graphs
Seth Pettie and Hsin-Hao Su
ICALP 2013
See journal version.

The Locality of Distributed Symmetry Breaking
Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider
FOCS 2012
See journal version.

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

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

Approximating Maximum Weight Matching in Near-linear Time
Ran Duan and Seth Pettie
FOCS 2010
PDF
See journal version.

Connectivity Oracles for Failure Prone Graphs
Ran Duan and Seth Pettie
STOC 2010
PDF
See journal version.

On Nonlinear Forbidden 0-1 Matrices: A Refutation of a Furedi-Hajnal Conjecture
Seth Pettie
SODA 2010
See journal version: Degrees of Nonlinearity in Forbidden 0-1 Matrix Problems.

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

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

Dual-Failure Distance and Connectivity Oracles
Ran Duan and Seth Pettie
SODA 2009
PDF

Distributed Algorithms for Ultrasparse Spanners and Linear Size Skeletons
Seth Pettie
PODC 2008
See journal version.

Improved Distributed Approximate Matching
Zvi Lotker, Boaz Patt-Shamir, Seth Pettie
SPAA 2008
See journal version.

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

Bounded-leg Distance and Reachability Oracles
Ran Duan and Seth Pettie
SODA 2008
PDF

Low Distortion Spanners
Seth Pettie
ICALP 2007
See journal version.

Sensitivity Analysis of Minimum Spanning Trees in Sub-Inverse-Ackermann Time
Seth Pettie
ISAAC 2005
See journal version.

Towards a Final Analysis of Pairing Heaps
Seth Pettie
FOCS 2005
PDF

The Complexity of Implicit and Space-Efficient Priority Queues
Christian Mortensen and Seth Pettie
WADS 2005
PostScript

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 version.

On the Comparison-Addition Complexity of All-pairs Shortest Paths
Seth Pettie
13th Annual International Symposium on Algorithms and Computation (ISAAC 2002).
PostScript, PDF
(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
See technical report below.

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

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.
Manuscripts / In Submission

Fourier Transform-based Estimators for Data Sketches
Seth Pettie and Dingyu Wang

Detecting Data Fraud Attacks in Sketching and Streaming
Seth Pettie and Dingyu Wang

Optimal Vertex Connectivity Oracles
Seth Pettie, Thatchaphol Saranurak, and Longhui Yin
Journal submission: arXiv:2201.00408


Journal Articles

Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection
Shang-En Huang, Seth Pettie, and Leqi Zhu
J. ACM, 2024.
Publisher's website

Almost Optimal Exact Distance Oracles for Planar Graphs
Panagiotis Charalampopoulos, Pawel Gawrychowski, Yaowei Long, Shay Mozes, Seth Pettie, Oren Weimann, and Christian Wulff-Nilsen
J. ACM 70(2), Article 12, pp 1-50, 2023.
Publisher's website

Fully Dynamic Connectivity in O(log n(log log n)2) Amortized Expected Time
Shang-En Huang, Dawei Huang, Tsvi Kopelowitz, Seth Pettie, and Mikkel Thorup
TheoretiCS Vol. 2, Article 6, 2023.
Publisher's website

Wake Up and Join Me! An Energy Efficient Algorithm for Maximal Matching in Radio Networks
Varsha Dani, Aayush Gupta, Thomas Hayes, and Seth Pettie
Distributed Computing, 2022.
arXiv:2104.09096
Publisher's website

Approximate Generalized Matching: f-Factors and f-Edge Covers
Dawei Huang and Seth Pettie
Algorithmica 84(7):1952-1992, 2022.
arXiv:1706.05761

Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing Shortcuts
Shang-En Huang and Seth Pettie
SIAM J. Discrete Mathematics 35(3):2129-2144, 2021.

Near-optimal Distributed Triangle Enumeration via Expander Decompositions
Yi-Jun Chang, Seth Pettie, Thatchaphol Saranurak, and Hengjie Zhang
J. ACM 68(3):1-36, 2021.
Publisher's website

The Communication Complexity of Set Intersection and Multiple Equality Testing
Dawei Huang, Seth Pettie, Yixiang Zhang, and Zhijun Zhang
SIAM J. Comput. 50(2):674-717, 2021.
Publisher's website.

Connectivity Oracles for Graphs Subject to Vertex Failures
Ran Duan and Seth Pettie
SIAM J. Comput. 49(6):1363-1396, 2020.
arXiv:1607.06865
Publisher's website

Distributed (Δ +1)-Coloring via Ultrafast Graph Shattering
Yi-Jun Chang, Wenzheng Li, Seth Pettie
SIAM J. Comput. 49(3):497-539, 2020.
Publisher's website

Distributed Edge Coloring and a Special Case of the Constructive Lovasz Local Lemma
Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, and Jara Uitto
ACM Transactions on Algorithms 16(1), Article 8, 2020.
Publisher's website

Join on Samples: A Theoretical Guide for Practitioners
Dawei Huang, Dong Young Yoon, Seth Pettie, and Barzan Mozafari
Proceedings of the VLDB Endowment 13(4):547-560, 2019.
PDF

Exponential Separations in the Energy Complexity of Leader Election
Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie, Ruosong Wang, Wei Zhan
ACM Transactions on Algorithms 15(4), Article 49, 2019.
Publisher's website

An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model
Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie
SIAM J. Comput. 48(1):122-143, 2019.
Publisher's website

Mind the Gap! Online Dictionary Matching with One Gap
Amihood Amir, Tsvi Kopelowitz, Avivit Levy, Seth Pettie, Ely Porat, and B. Riva Shalom
Algorithmica 81(6):2123-2157, 2019.
Publisher's website

A Time Hierarchy Theorem for the LOCAL Model
Yi-Jun Chang and Seth Pettie
SIAM J. Comput. 48(1):33-69, 2019.
Publisher's website, PDF

A Hierarchy of Lower Bounds for Sublinear Additive Spanners
Amir Abboud, Greg Bodwin, and Seth Pettie
SIAM J. Comput. 47(6):2203-2236, 2018.
Publisher's website, PDF

Thorup-Zwick Emulators are Universally Optimal Hopsets
Shang-En Huang and Seth Pettie
Information Processing Letters 142, pp. 9-13, 2019.
Publisher's website

Contention Resolution with Constant Throughput and Log-Logstar Channel Accesses
Michael Bender, Tsvi Kopelowitz, Seth Pettie, and Maxwell Young
SIAM J. Comput. 47(5):1735-1754, 2018.
Publisher's website, PDF

Threesomes, Degenerates, and Love Triangles
Allan Grønlund and Seth Pettie
J. ACM 65(4), Article 22, 2018.
PDF

Scaling Algorithms for Weighted Matching in General Graphs
Ran Duan, Seth Pettie, and Hsin-Hao Su
ACM Transactions on Algorithms 14(1), Article 8, 2018.
Publisher website, PDF

Lower Bounds on Davenport-Schinzel Sequences via Rectangular Zarankiewicz Matrices
Julian Wellman and Seth Pettie
Discrete Mathematics 341(7):1987-1993, 2018.
arXiv:1610.09774

A Resource-competitive Jamming Defense
Valerie King, Seth Pettie, Jared Saia, and Maxwell Young
Distributed Computing 31(6):419-439, 2018.
Publisher website, PDF

Distributed Algorithms for the Lovász Local Lemma and Graph Coloring
Kai-Min Chung, Seth Pettie, and Hsin-Hao Su
Distributed Computing 30(4):261-280, 2017.
Publisher website, PDF

The Locality of Distributed Symmetry Breaking
Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider
J. ACM 63(3), Article 20, 2016.
PDF

A Linear Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs
Michael Elkin and Seth Pettie
ACM Transactions on Algorithms 12(4), Article 50, 2016.
PDF

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

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

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

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

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

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

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

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

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

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

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

Low Distortion Spanners
Seth Pettie
ACM Transactions on Algorithms 6(1), 2009.
PDF, post-publication acknowledgement

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

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

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

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

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

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

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

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


Theses and Technical Reports

On the Shortest Path and Minimum Spanning Tree Problems
PDF
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,

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



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