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 34th Int'l Symposium on Theoretical Aspects of Computer Science (STACS 2017) 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, Postdocs, and Visitors Shang-En Huang (Ph.D student) Yi-Jun Chang (Ph.D. student) Dawei Huang (Ph.D. student) 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 Veronika Loitzenbauer, University of Vienna. Visitor, June-August, 2016. Ruosong Wang, Tsinghua University. Visitor, February-June, 2016. Wei Zhan, Tsinghua University. Visitor, February-June, 2016. Manuscripts / In Submission Exponential Separations in the Energy Complexity of Leader Election Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie, Ruosong Wang, Wei Zhan arXiv:1609.08486v2 Lower Bounds on Davenport-Schinzel Sequences via Rectangular Zarankiewicz Matrices Julian Wellman and Seth Pettie arXiv:1610.09774 Journal Articles Distributed Algorithms for the Lovász Local Lemma and Graph Coloring Kai-Min Chung, Seth Pettie, and Hsin-Hao Su Distributed Computing, to appear. The Locality of Distributed Symmetry Breaking Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider J. ACM 63(3), Article 20, 2016. PDF, BibTex 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, BibTex 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 Conference Papers 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, BibTex A Hierarchy of Lower Bounds for Sublinear Additive Spanners Amir Abboud, Greg Bodwin, and Seth Pettie SODA 2017 arXiv:1607.07497, BibTex Connectivity Oracles for Graphs Subject to Vertex Failures Ran Duan and Seth Pettie SODA 2017 arXiv:1607.06865, BibTex Scaling Algorithms for Weighted Matching in General Graphs Ran Duan, Seth Pettie, and Hsin-Hao Su SODA 2017 arXiv:1411.1919v5, BibTex Simultaneously Load Balancing for Every p-norm, With Reassignments Aaron Bernstein, Tsvi Kopelowitz, Seth Pettie, Ely Porat, and Cliff Stein ITCS 2017 PDF, BibTex 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, BibTex 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, BibTex Faster Worst Case Deterministic Dynamic Connectivity Casper Kejlberg-Rasmussen, Tsvi Kopelowitz, Seth Pettie, and Mikkel Thorup ESA 2016 arXiv:1507.05944v2, BibTex 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 arXiv:1407.6756, BibTex 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 See journal version. BibTex Threesomes, Degenerates, and Love Triangles Allan Grønlund, Seth Pettie FOCS 2014 arXiv:1404.0799, BibTex 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, 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 See journal version. BibTex Conference presentation (extended) PPTX Fast Distributed Coloring Algorithms for Triangle-Free Graphs Seth Pettie and Hsin-Hao Su ICALP 2013 See journal version. BibTex The Locality of Distributed Symmetry Breaking Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider FOCS 2012 See journal version. 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 See journal version. Connectivity Oracles for Failure Prone Graphs Ran Duan and Seth Pettie STOC 2010 PDF, BibTex See arXiv report: Connectivity Oracles for Graphs Subject to Vertex Failures. 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. BibTex Applications of Forbidden 0-1 Matrices to Search Tree- and Path Compression-Based Data Structures Seth Pettie SODA 2010 PDF, BibTex Fast Algorithms for (Max,Min)-Matrix Multiplication and Bottleneck Shortest Paths Ran Duan and Seth Pettie SODA 2009 PDF, BibTex Dual-Failure Distance and Connectivity Oracles Ran Duan and Seth Pettie SODA 2009 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 See journal version. BibTex Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture Seth Pettie SODA 2008 PDF, BibTex Bounded-leg Distance and Reachability Oracles Ran Duan and Seth Pettie SODA 2008 PDF, BibTex Low Distortion Spanners Seth Pettie ICALP 2007 See journal version. BibTex 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, BibTex The Complexity of Implicit and Space-Efficient Priority Queues Christian Mortensen and Seth Pettie WADS 2005 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 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, 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 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, 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 |