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