|
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
STOC 2025,
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), now Professor @ University of Manitoba.
Shang-En Huang (Ph.D 2022), postdoc @ Boston College, now Professor @ National Taiwan University.
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.
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
Sketching, Moment Estimation, and the Lévy-Khintchine Representation Theorem
Seth Pettie and Dingyu Wang
ITCS 2025
arXiv:2410.17426
A Refutation of the Pach-Tardos Conjecture for 0-1 Matrices
Seth Pettie and Gabor Tardos
SODA 2025
arXiv:2407.02638
Connectivity Labeling Schemes for Multiple Edge and Vertex Faults via Expander Hierarchies
Yaowei Long,
Seth Pettie, and
Thatchaphol Saranurak
SODA 2025
arXiv:2410.18885
Universal Perfect Sampling for Incremental Streams
Seth Pettie
and
Dingyu Wang
SODA 2025
arXiv:2407.04931
Connectivity Labeling and Routing with Multiple Vertex Failures
Merav Parter,
Asaf Petruschka,
and Seth Pettie
STOC 2024
arXiv:2307.06276
link to paper
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
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 71(2), Article 12, pp. 1-37, 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
|
