Ph.D. Thesis

@PhDThesis{Pet-thesis, author = "Seth Pettie", title = "On the Shortest Path and Minimum Spanning Tree Problems", school = "The University of Texas at Austin", year = "2003", type = "{P}h.{D}. Thesis", note = "Department of Computer Sciences Technical Report TR-03-35, http://www.cs.utexas.edu/ftp/pub/techreports/tr03-35.ps.gz", month = "August", }

Journal Articles

@article{GronlundP18, author = {A. Gr\o nlund and S. Pettie}, title = {Threesomes, degenerates, and love triangles}, journal = {J. ACM}, volume = {?}, issue = {?}, note = {?}, year = {?}, } @article{KingPSY, author = {V. King and S. Pettie and J. Saia and M. Young}, title = {A Resource-competitive Jamming Defense}, journal = {Distributed Computing}, volume = {?}, issue = {?}, pages = {?}, year = {?}, } @article{ChungPS17, author = {K.-M. Chung and S. Pettie and H.-H. Su}, title = {Distributed Algorithms for the {L}ov\'{a}sz Local Lemma and Graph Coloring}, journal = {Distributed Computing}, volume = {30}, issue = {4}, pages = {261--280}, year = {2017}, } @article{BEPS16, author = {L. Barenboim and M. Elkin and S. Pettie and J. Schneider}, title = {The Locality of Distributed Symmetry Breaking}, journal = {J. ACM}, volume = {63}, issue = {3}, note = {Article 20}, year = {2016}, } @article{ElkinP16, author = {S. Pettie}, title = {A Linear Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs}, journal = {ACM Transactions on Algorithms}, volume = {12}, number = {4}, note = {Article 50}, year = {2016}, } @article{Pettie-DS, author = {S. Pettie}, title = {Sharp Bounds on {D}avenport-{S}chinzel Sequences of Every Order}, journal = {J. ACM}, volume = {62}, issue = {5}, note = {Article 36}, year = {2015}, } @article{LotkerPP-distrmatch, author = {Z. Lotker and B. Patt-Shamir and S. Pettie}, title = {Improved Distributed Approximate Matching}, journal = {J. ACM}, volume = {62}, issue = {5}, note = {Article 38}, year = {2015}, } @article{Pettie-FormFree, author = {S. Pettie}, title = {Three Generalizations of {D}avenport-{S}chinzel Sequences}, journal = {SIAM J. Discr. Math.}, volume = {29}, issue = {4}, pages = {2189—2238}, year = {2015}, } @article{Pettie15-sensitivity, author = {S. Pettie}, title = {Sensitivity Analysis of Minimum Spanning Trees in Sub-Inverse-{A}ckermann Time}, journal = {J. Graph Algorithms and Applications}, volume = {19}, number = {1}, pages = {375--391}, year = {2015}, } @article{PettieS-trianglefree, author = {S. Pettie and H.-H. Su}, title = {Distributed algorithms for coloring triangle-free graphs}, journal = {Information and Computation}, volume = {243}, year = {2015}, pages = {263--280}, } @article{DuanP-approxMWM, author = {R. Duan and S. Pettie}, title = {Linear Time Approximation for Maximum Weight Matching}, journal = {J. ACM}, volume = {61}, number = {1}, note = {Article 1}, year = {2014}, } @article{Pettie-MCM-to-MWM, author = {S. Pettie}, title = {A Simple Reduction from Maximum Weight Matching to Maximum Cardinality Matching}, journal = {Information Processing Letters}, year = {2012}, volume = {112}, issue = {23}, pages = {893-898}, } @article{Pettie-FH, author = {S. Pettie}, title = {Degrees on Nonlinearity in Forbidden 0-1 Matrix Problems}, journal = {Discrete Mathematics}, year = {2011}, volume = {311}, pages = {2396--2410}, } @article{Pettie-GenDS, author = {S. Pettie}, title = {Generalized Davenport-Schinzel Sequences and Their 0-1 Matrix Counterparts}, journal = {J. Comb. Theory Ser. A}, year = {2011}, volume = {118}, number = {6}, pages = {1863--1895}, } @article{Pettie-DS-nonlin, author = {S. Pettie}, title = {Origins of Nonlinearity in Davenport-Schinzel Sequences}, journal = {SIAM J. Discrete Mathematics}, year = {2011}, volume = {25}, number = {1}, pages = {211--233}, } @article{Pettie-Distr-Spanner, author = {S. Pettie}, title = {Distributed Algorithms for Ultrasparse Spanners and Linear Size Skeletons}, journal = {Distributed Computing}, volume = {22}, number = {3}, year = {2010}, pages = {147--166}, } @article{Pettie-Low-Dist-Span, author = {S. Pettie}, title = {Low Distortion Spanners}, journal = {ACM Transactions on Algorithms}, volume = {6}, number = {1}, year = {2009}, } @article{BaswanaKMP, author = {S. Baswana and T. Kavitha and K. Mehlhorn and S. Pettie}, title = {Additive Spanners and $(\alpha,\beta)$-Spanners}, journal = {ACM Transactions on Algorithms}, volume = {7}, number = {1}, year = {2010}, } @article{PetRam-RandMST, author = {S. Pettie and V. Ramachandran}, title = {Randomized Minimum Spanning Tree Algorithms Using Exponentially Fewer Random Bits}, journal = {ACM Transactions on Algorithms}, volume = {4}, number = {1}, year = {2008}, pages = {1--27}, } @article{PetUndirectedSP, author = {S. Pettie and V. Ramachandran}, title = {A Shortest Path Algorithm for Real-Weighted Undirected Graphs}, journal = SICOMP, volume = {34}, number = {6}, year = {2005}, pages = {1398--1431}, } @article{PetInvAck, author = {Seth Pettie}, title = {An Inverse-{A}ckermann Type Lower Bound for Online Minimum Spanning Tree Verification}, journal = {Combinatorica}, volume = {26}, number = {2}, pages = {207--230}, year = {2006}, } @article{PS04, author = {Seth Pettie and Peter Sanders}, title = {A simpler linear time $2/3 - \epsilon$ Approximation to Maximum Weight Matching}, journal = {Information Processing Letters}, volume = {91}, number = {6}, pages = {271--276}, year = {2004}, } @article{Pet03, author = {Seth Pettie}, title = {A New Approach to All-Pairs Shortest Paths on Real-Weighted Graphs}, journal = {Theoretical Computer Science}, volume = {312}, number = {1}, pages = {47--74}, year = {2003}, note = {special issue of selected papers from ICALP 2002}, } @article{PR02c, author = {Seth Pettie and Vijaya Ramachandran}, title= {An optimal minimum spanning tree algorithm}, journal = {J. {ACM}}, volume = {49}, number = {1}, year = {2002}, pages = {16--34}, } @article{PR02d, author = {Seth Pettie and Vijaya Ramachandran}, title = {A randomized time-work optimal parallel algorithm for finding a minimum spanning forest}, journal = {SIAM J. Comput.}, volume = {31}, number = {6}, year = {2002}, pages = {1879--1895}, }

Conference Papers

@inproceedings{ChangLP18, author = {Y.-J. Chang and W. Li and S. Pettie}, title = {An optimal distributed $(\Delta+1)$-coloring algorithm?}, booktitle = {Proceedings 50th ACM Symposium on Theory of Computing (STOC)}, pages = {?}, year = {2018}, } @inproceedings{ChangHLPU18, author = {Y.-J. Chang and Q. He and W. Li and S. Pettie and J. Uitto}, title = {The complexity of distributed edge coloring with small palettes}, booktitle = {Proceedings 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)}, pages = {2633--2652}, year = {2018}, } @inproceedings{ChangP17, author = {Y.-J. Chang and S. Pettie}, title = {A Time Hierarchy Theorem for the {LOCAL} Model}, booktitle = {Proceedings 58th IEEE Symposium on Foundations of Computer Science (FOCS)}, pages = {156-167}, year = {2017}, } @inproceedings{CKPWZ17, author = {Y.-J. Chang and T. Kopelowitz and S. Pettie and R. Wang and W. Zhan}, title = {Exponential Separations in the Energy Complexity of Leader Election}, booktitle = {Proceedings 49th ACM Symposium on Theory of Computing (STOC)}, pages = {771-783}, year = {2017}, } @inproceedings{BernsteinKPPS17, author = {A. Bernstein and T. Kopelowitz and S. Pettie and E. Porat and C. Stein}, title = {Simultaneously load balancing for every $p$-norm, with reassignments}, booktitle = {Proceedings of the 8th Conference on Innovations in Theoretical Computer Science ({ITCS})}, pages = {51:1-51:14}, year = {2017}, } @inproceedings{HuangHKP17, author = {S.-E. Huang and D. Huang and T. Kopelowitz and S. Pettie}, title = {Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time}, booktitle = {Proceedings 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)}, pages = {510--520}, year = {2017}, } @inproceedings{DuanP17, author = {R. Duan and S. Pettie}, title = {Connectivity Oracles for Graphs Subject to Vertex Failures}, booktitle = {Proceedings 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)}, pages = {490--509}, year = {2017}, } @inproceedings{DuanPS17, author = {R. Duan and S. Pettie and H.-H. Su}, title = {Scaling Algorithms for Weighted Matching in General Graphs}, booktitle = {Proceedings 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)}, pages = {781--800}, year = {2017}, } @inproceedings{AbboudBP17, author = {A. Abboud and G. Bodwin and S. Pettie}, title = {A Hierarchy of Lower Bounds for Sublinear Additive Spanners}, booktitle = {Proceedings 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)}, pages = {568--576}, year = {2017}, } @inproceedings{AmirKLPPS16, author = {A. Amir and T. Kopelowitz and A. Levy and S. Pettie \ and E. Porat and B. Riva Shalom}, title = {Mind the Gap: Essentially Optimal Algorithms for Online Dictionary Matching with One Gap}, booktitle = {Proceedings 27th International Symposium on Algorithms and Computation (ISAAC)}, pages = {12:1--12:12}, year = {2016}, doi = {10.4230/LIPIcs.ISAAC.2016.12}, } @inproceedings{CKP16, author = {Y.-J. Chang and T. Kopelowitz and S. Pettie}, title = {An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model}, booktitle = {Proceedings 57th IEEE Symposium on Foundations of Computer Science (FOCS)}, pages = {615--624}, year = {2016}, } @inproceedings{KKPT16, author = {C. Kejlberg-Rasmussen and T. Kopelowitz and S. Pettie and M. Thorup}, title = {Faster Worst Case Deterministic Dynamic Connectivity}, booktitle = {Proceedings 24th European Symposium on Algorithms (ESA)}, pages = {53:1--53:15}, year = {2016}, } @inproceedings{BKPY16, author = {M. Bender and T. Kopelowitz and S. Pettie and M. Young}, title = {Contention Resolution with Log-Logstar Channel Accesses}, booktitle = {Proceedings 48th ACM Symposium on Theory of Computing (STOC)}, pages = {499--508}, year = {2016}, } @inproceedings{KopelowitzPP16, author = {T. Kopelowitz and S. Pettie and E. Porat}, title = {Higher Lower Bounds from the 3SUM Conjecture}, booktitle = {Proceedings 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)}, year = {2016}, pages = {1272--1287}, } @inproceedings{KopelowitzPP15, author = {T. Kopelowitz and S. Pettie and E. Porat}, title = {Dynamic Set Intersection}, booktitle = {Proceedings 14th Int'l Symposium on Algorithms and Data Structures (WADS)}, year = {2015}, pages = {470--481}, } @inproceedings{ElkinP15, author = {M. Elkin and S. Pettie}, title = {A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs}, booktitle = {Proceedings 26th Annual {ACM-SIAM} Symposium on Discrete Algorithms ({SODA})}, pages = {805--821}, year = {2015}, } @inproceedings{Pettie15, author = {S. Pettie}, title = {Sharp Bounds on Formation-free Sequences}, booktitle = {Proceedings 26th Annual {ACM-SIAM} Symposium on Discrete Algorithms ({SODA})}, pages = {592--604}, year = {2015}, } @inproceedings{ElkinPS15, author = {M. Elkin and S. Pettie and H.-H. Su}, title = {$(2\Delta - l)$-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting}, booktitle = {Proceedings 26th Annual {ACM-SIAM} Symposium on Discrete Algorithms ({SODA})}, pages = {355--370}, year = {2015}, } @inproceedings{GronlundP14, author = {A. Gr\o nlund and S. Pettie}, title = {Threesomes, degenerates, and love triangles}, booktitle = {Proceedings 55th IEEE Symposium on Foundations of Computer Science (FOCS)}, pages = {621--630}, year = {2014}, } @inproceedings{ChungPS14, author = {K.-M. Chung and S. Pettie and H.-H. Su}, title = {Distributed Algorithms for the {L}ov\'{a}sz Local Lemma and Graph Coloring}, booktitle = {Proceedings 33rd ACM Symposium on Principles of Distributed Computing (PODC)}, year = {2014}, pages = {134--143}, } @inproceedings{GilbertKPPSY14, author = {S. Gilbert and V. King and S. Pettie and E. Porat and J. Saia and M. Young}, title = {(Near) Optimal Resource-Competitive Broadcast with Jamming}, booktitle = {Proceedings 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)}, year = {2014}, pages = {257--266}, } @inproceedings{Pettie-DS13, author = {S. Pettie}, title = {Sharp Bounds on {D}avenport-{S}chinzel Sequences of Every Order}, booktitle = {Proceedings 29th Annual Symposium on Computational Geometry (SOCG)}, year = {2013}, pages = {319--328}, note = {Full manuscript available at arXiv:1204.1086}, } @inproceedings{PettieSu13, author = {S. Pettie and H.-H. Su}, title = {Fast Distributed Coloring Algorithms for Triangle-Free Graphs}, booktitle = {Proceedings 40th Int'l Colloquium on Automata, Languages, and Programming (ICALP)}, year = {2013}, pages = {681--693}, } @inproceedings{BEPS12, author = {L. Barenboim and M. Elkin and S. Pettie and J. Schneider}, title = {The Locality of Distributed Symmetry Breaking}, booktitle = {Proceedings 53rd IEEE Symposium on Foundations of Computer Science (FOCS)}, year = {2012}, pages = {321-330}, note = {Full manuscript available at arXiv:1202.1983} } @inproceedings{BPW-N12, author = {G. Borradaile and S. Pettie and C. Wulff-Nilsen}, title = {Connectivity Oracles for Planar Graphs}, booktitle = {Proceedings 13th Scandinavian Workshop on Algorithm Theory (SWAT)}, year = {2012}, pages = {316--327}, note = {Full manuscript available at arXiv:1204.4159}, } @inproceedings{Pettie-Forbidden-Sequences-11, author = {S. Pettie}, title = {On the structure and composition of forbidden sequences, with geometric applications}, booktitle = {Proceedings 27th Annual Symposium on Computational Geometry (SOCG)}, year = {2011}, pages = {370--379}, } @inproceedings{DuanP10b, author = {R. Duan and S. Pettie}, title = {Approximating Maximum Weight Matching in Near-Linear Time}, booktitle = {Proceedings 51st IEEE Symposium on Foundations of Computer Science (FOCS)}, year = {2010}, pages = {673--682}, } @inproceedings{DuanP10, author = {R. Duan and S. Pettie}, title = {Connectivity Oracles for Failure Prone Graphs}, booktitle = {Proceedings 42nd ACM Symposium on Theory of Computing (STOC)}, year = {2010}, pages = {465--474}, } @inproceedings{Pettie-Forbidden-10, author = {S. Pettie}, title = {Applications of Forbidden 0-1 Matrices to Search Tree- and Path Compression-Based Data Structures}, booktitle = {Proceedings 21st ACM-SIAM Symposium on Discrete Algorithms (SODA)}, year = {2010}, pages = {1457--1467} } @inproceedings{Pettie-FH-10, author = {S. Pettie}, title = {On Nonlinear Forbidden 0-1 Matrices: A Refutation of a F\"{u}redi-Hajnal Conjecture}, booktitle = {Proceedings 21st ACM-SIAM Symposium on Discrete Algorithms (SODA)}, year = {2010}, pages = {875--885} } @inproceedings{DuanP09b, author = {R. Duan and S. Pettie}, title = {Fast algorithms for ($\max$, $\min$)-matrix multiplication and bottleneck shortest paths}, booktitle = {Proceedings 20th ACM-SIAM Symposium on Discrete Algorithms (SODA)}, year = {2009}, pages = {384--391}, } @inproceedings{DuanP09a, author = {R. Duan and S. Pettie}, title = {Dual-failure distance and connectivity oracles}, booktitle = {Proceedings 20th ACM-SIAM Symposium on Discrete Algorithms (SODA)}, year = {2009}, pages = {506--515}, } @inproceedings{Pettie-Spanner-08, author = {S. Pettie}, title = {Distributed Algorithms for Ultrasparse Spanners and Linear Size Skeletons}, booktitle = {Proc. 27th ACM Symposium on Principles of Distributed Computing (PODC)}, year = {2008}, pages = {253--262}, } @inproceedings{LotkerPP-08, author = {Z. Lotker and B. Patt-Shamir and S. Pettie}, title = {Improved Distributed Approximate Matching}, booktitle = {Proc. 20th ACM Symposium on Parallel Algorithms and Architectures (SPAA)}, year = {2008}, pages = {129--136}, } @inproceedings{DuanPettie08, author = {R. Duan and S. Pettie}, title = {Bounded-leg Distance and Reachability Oracles}, booktitle = {Proc. 19th {ACM}-{SIAM} Symposium on Discrete Algorithms (SODA)}, year = {2008}, pages = {436--445}, } @inproceedings{Pettie-Deque-08, author = {S. Pettie}, title = {Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture}, booktitle = {Proc. 19th {ACM}-{SIAM} Symposium on Discrete Algorithms (SODA)}, year = {2008}, pages = {1115--1124}, } @inproceedings{Pettie-Spanner-07, author = {S. Pettie}, title = {Low Distortion Spanners}, booktitle = {Proc. 34th Int'l Colloq. on Automata, Languages, and Programming ({ICALP})}, year = {2007}, pages = {78--87}, } @inproceedings{Pettie-Sensitivity-05, author = {S. Pettie}, title = {Sensitivity Analysis of Minimum Spanning Trees in Sub-Inverse-{A}ckermann Time}, pages = {964--973}, year = {2005}, booktitle = {Proceedings 16th Int'l Symposium on Algorithms and Computation ({ISAAC})}, } @inproceedings{Pettie05, author = {S. Pettie}, title = {Towards a Final Analysis of Pairing Heaps}, pages = {174--183}, year = {2005}, booktitle = {Proceedings 46th Annual Symposium on Foundations of Computer Science ({FOCS})}, } @inproceedings{MortensenPettie05, author = {C.~W. Mortensen and S. Pettie}, title = {The Complexity of Implicit and Space-Efficient Priority Queues}, pages = {49--60}, year = {2005}, booktitle = {Proceedings 9th Biennial Workshop on Algorithms and Data Structures ({WADS})}, } @inproceedings{BTMP05, author = {Surender Baswana and Telikepalli Kavitha and Kurt Mehlhorn and Seth Pettie}, title = {New constructions of $(\alpha,\beta)$-spanners and purely additive spanners}, year = {2005}, booktitle = {Proc.~16th Ann.~{ACM}-{SIAM} Symposium on Discrete Algorithms ({SODA})}, pages = {672--681}, } @inproceedings{Pet02b, author = "Seth Pettie", title = "On the Comparison-Addition Complexity of All-Pairs Shortest Paths", year = "2002", pages = "32--43", booktitle = "Proc. 13th Annual Int'l Symp. on Algorithms and Computation ({ISAAC})", } @inproceedings{Pet02a, author = "Seth Pettie", title = "An Inverse-{Ackermann} Style Lower Bound for the Online Minimum Spanning Tree Verification Problem", year = "2002", pages = "155--163", booktitle = "Proc. 43rd Annual Symposium on Foundations of Computer Science ({FOCS})", } @inproceedings{Pet02, author = "S. Pettie", title = "A Faster All-pairs Shortest Path Algorithm for Real-weighted Sparse Graphs", booktitle = "Proceedings of 29th International Colloquium on Automata, Languages, and Programming ({ICALP}), {LNCS} Vol. 2380", pages = "85--97", year = "2002", } @inproceedings{GP02, author = "H. Gabow and S. Pettie", title = "The Dynamic Vertex Minimum Problem and Its Application to Clustering-type Approximation Algorithms", booktitle = "Proceedings 8th Scandinavian Workshop on Algorithm Theory ({SWAT}), {LNCS} Vol. 2368", pages = "190--199", year = "2002", } @InProceedings{PR02b, author = "S. Pettie and V. Ramachandran", title = "Minimizing randomness in minimum spanning tree, parallel connectivity and set maxima algorithms", booktitle = "Proceedings of the 13th Annual {ACM}-{SIAM} Symposium on Discrete Algorithms ({SODA})", pages = "713--722", year = "2002", } @InProceedings{PR02a, author = "S. Pettie and V. Ramachandran", title = "Computing shortest paths with comparisons and additions", booktitle = "Proceedings of the 13th Annual {ACM}-{SIAM} Symposium on Discrete Algorithms ({SODA})", pages = "267--276", year = "2002", } @InProceedings{PRS02, author = "S. Pettie and V. Ramachandran and S. Sridhar", title = "Experimental evaluation of a new shortest path algorithm", booktitle = "Proc. 4th Workshop on Algorithm Engineering and Experiments ({ALENEX}), {LNCS} Vol. 2409", pages = "126--142", year = "2002", } @inproceedings{PR00, author = "S. Pettie and V. Ramachandran", title = "An optimal minimum spanning tree algorithm", booktitle = "Proceedings of {ICALP} 2000 ({LNCS} Vol. 1853)", pages = "49--60", year = "2000", } @inproceedings{PR99, author = "S. Pettie and V. Ramachandran", title = "A randomized time-work optimal parallel algorithm for finding a minimum spanning forest", booktitle = "Proceedings of {RANDOM}-{APPROX}'99 ({LNCS} Vol. 1671)", pages = "233--244", year = "1999", }

Technical Reports

@techreport{CU-CS-928-02, author = "H. Gabow and S. Pettie", title = "The Dynamic Vertex Minimum Problem and Its Application to Clustering-type Approximation Algorithms", institution = "University of Colorado, Boulder", type = "Technical Report", number = "CU-CS-928-02", bibdate = apr, year = "2002", } @TechReport{Pet-TR23, year = "1999", type = "Technical Report", number = "CS-TR-99-23", institution = "University of Texas, Austin", title = "Finding minimum spanning trees in {$O(m\alpha(m,n))$} time", bibdate = "October 21, 99", url = "ftp://ftp.cs.utexas.edu/pub/techreports/tr99-23.ps.Z", author = "S. Pettie", abstract = "We describe a deterministic minimum spanning tree algorithm running in time $O(m \alpha(m,n))$, where alpha is a natural inverse of Ackermann's function and m and n are the number of edges and vertices, respectively. This improves upon the $O(m \alpha(m,n) \log \alpha(m,n))$ bound established by Chazelle in 1997. A similar $O(m \alpha(m,n))$-time algorithm was discovered independently by Chazelle, predating the algorithm presented here by many months. This paper may still be of interest for its alternative exposition.", }