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

Teaching: Winter 2009: EECS 598 - Graph Optimization Algorithms Fall 2008: EECS 376 - Foundations of Computer Science Fall 2007: EECS 203 - Discrete Mathematics Winter 2007: EECS 477 - Introduction to Algorithms Fall 2006: EECS 598 - Advanced Data Structures See the Theory Seminar calendar for upcoming talks. If you'd like to be added to the mailing list just send me an email. Professional Service: Editorial Board, The Encyclopedia of Algorithms 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 Low Distortion Spanners ACM Transactions on Algorithms, to appear. PDF BibTex Additive Spanners and (&alpha,&beta)-Spanners (with S. Baswana, T. Kavitha, and K. Mehlhorn) ACM Transactions on Algorithms, to appear. PDF BibTex Randomized Minimum Spanning Tree Algorithms Using Exponentially Fewer Random Bits (with Vijaya Ramachandran) ACM Transactions on Algorithms 4(1):1--27, 2008.. PDF, BibTex A Shortest Path Algorithm for Real-Weighted Undirected Graphs (with Vijaya Ramachandran) SIAM J. Comput. 34(6):1398--1431, 2005. Journal Version: Link to article, PDF, BibTeX An Inverse-Ackermann Type Lower Bound for Online Minimum Spanning Tree Verification Combinatorica 26(2):207--230, 2006. Journal Submission: PostScript, PDF, BibTex A Simpler Linear Time 2/3 - &epsilon Approximation for Maximum Weight Matching (with Peter Sanders) Information Processing Letters 91(6):271--276. Journal Version: PostScript, PDF, BibTex A New Approach to All-Pairs Shortest Paths on Real-Weighted Graphs Theoretical Computer Science, special issue on papers from ICALP 2002, 312(1), pp. 47--74. Link to article, PostScript, PDF, BibTex An Optimal Minimum Spanning Tree Algorithm (with Vijaya Ramachandran) J. Assoc. Comput. Mach. 49(1), pp. 16--34 Link to article, PostScript, PDF, BibTex A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest. (with Vijaya Ramachandran) SIAM Journal on Computing 31(6), pp. 1879--1895. Link to article, PostScript, PDF, BibTex Manuscripts / In Submission Origins of Nonlinearity in Davenport-Schinzel Sequences Journal Submission: PDF Conference Papers Fast Algorithms for (Max,Min)-Matrix Multiplication and Bottleneck Shortest Paths (with Ran Duan) SODA 2009 Conference Version: PDF, BibTex Dual-Failure Distance and Connectivity Oracles (with Ran Duan) SODA 2009 Conference Version: PDF, BibTex Distributed Algorithms for Ultrasparse Spanners and Linear Size Skeletons PODC 2008 Journal Submission: PDF, BibTex Improved Distributed Approximate Matching (with Zvi Lotker and Boaz Patt-Shamir) SPAA 2008 Conference version: PDF, BibTex Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture SODA 2008 Preliminary Draft: PDF, BibTex Bounded-leg Distance and Reachability Oracles(with Ran Duan) SODA 2008 Preliminary Draft: PDF, BibTex Low Distortion Spanners ICALP 2007 Conference version: PDF BibTex Sensitivity Analysis of Minimum Spanning Trees in Sub-Inverse-Ackermann Time ISAAC 2005 Conference submission: Postscript, BibTex Towards a Final Analysis of Pairing Heaps FOCS 2005 Conference version: PDF, BibTex The Complexity of Implicit and Space-Efficient Priority Queues (with Christian Mortensen) WADS 2005 Conference Version: PostScript, BibTex New Constructions of (&alpha,&beta)-Spanners and Purely Additive Spanners (with S. Baswana, T. Kavitha, and K. Mehlhorn) Proceedings 16th Symposium on Discrete Algorithms (SODA 2005) [see journal submission] On the Comparison-Addition Complexity of All-pairs Shortest Paths 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 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 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 (with Harold Gabow) 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 (with 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 (with Vijaya Ramachandran) Proceedings 13th Symposium on Discrete Algorithms (SODA 2002) [see journal version] Computing Shortest Paths with Comparisons and Additions (with Vijaya Ramachandran) Proceedings 13th Symposium on Discrete Algorithms (SODA 2002) [see journal version] An Optimal Minimum Spanning Tree Algorithm (with 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. (with Vijaya Ramachandran) Proceedings 3rd Int'l Workshop on Randomization and Approximation in Computer Science RANDOM 1999 [see journal version] Ph.D. Thesis On the Shortest Path and Minimum Spanning Tree Problems PDF, BibTex Received The Outstanding Dissertation Award from The University of Texas Graduate School, 2004. Technical Reports The Dynamic Vertex Minimum Problem and its Application to Clustering-type Approximation Algorithms (with Harold Gabow) Technical Report: PostScript, PDF, BibTex Finding Minimum Spanning Trees in O(m &alpha(m,n)) Time Technical Report: PostScript, PDF, BibTex