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.