| 2026 | SODA | On a Clique Game and the Erdős-Hajnal Problem on High-Chromatic High-Girth Subgraphs. | Seth Pettie, Gbor Tardos, Bartosz Walczak |
| 2026 | STOC | Reviving Thorup's Shortcut Conjecture. | Aaron Bernstein, Henry L. Fleischmann, Maximilian Probst Gutenberg, Bernhard Haeupler, Gary Hoppenworth, Yonggang Jiang, George Z. Li, Seth Pettie, Thatchaphol Saranurak, Leon Schiller |
| 2026 | STOC | Contention Resolution, with and without a Global Clock. | Zixi Cai, Kuowen Chen, Shengquan Du, Tsvi Kopelowitz, Seth Pettie, Ben Plosk |
| 2025 | SODA | Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies. | Yaowei Long, Seth Pettie, Thatchaphol Saranurak |
| 2025 | SODA | A Refutation of the Pach-Tardos Conjecture for 0-1 Matrices. | Seth Pettie, Gbor Tardos |
| 2025 | SODA | Universal Perfect Samplers for Incremental Streams. | Seth Pettie, Dingyu Wang |
| 2024 | SODA | Sorting Pattern-Avoiding Permutations via 0-1 Matrices Forbidding Product Patterns. | Parinya Chalermsook, Seth Pettie, Sorrachai Yingchareonthawornchai |
| 2024 | SODA | On the Extremal Functions of Acyclic Forbidden 0-1 Matrices. | Seth Pettie, Gbor Tardos |
| 2024 | STOC | Connectivity Labeling and Routing with Multiple Vertex Failures. | Merav Parter, Asaf Petruschka, Seth Pettie |
| 2023 | PODS | Better Cardinality Estimators for HyperLogLog, PCSA, and Beyond. | Dingyu Wang, Seth Pettie |
| 2023 | SODA | Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection. | Shang-En Huang, Seth Pettie, Leqi Zhu |
| 2022 | STOC | Byzantine agreement in polynomial time with near-optimal resilience. | Shang-En Huang, Seth Pettie, Leqi Zhu |
| 2022 | STOC | Optimal vertex connectivity oracles. | Seth Pettie, Thatchaphol Saranurak, Longhui Yin |
| 2021 | ESA | Incremental SCC Maintenance in Sparse Graphs. | Aaron Bernstein, Aditi Dudeja, Seth Pettie |
| 2021 | ICALP | Non-Mergeable Sketching for Cardinality Estimation. | Seth Pettie, Dingyu Wang, Longhui Yin |
| 2021 | ICALP | The Structure of Minimum Vertex Cuts. | Seth Pettie, Longhui Yin |
| 2021 | PODC | Brief Announcement: Wake Up and Join Me! An Energy Efficient Algorithm for Maximal Matching in Radio Networks. | Varsha Dani, Aayush Gupta, Thomas P. Hayes, Seth Pettie |
| 2021 | SODA | Planar Distance Oracles with Better Time-Space Tradeoffs. | Yaowei Long, Seth Pettie |
| 2021 | STOC | Information theoretic limits of cardinality estimation: Fisher meets Shannon. | Seth Pettie, Dingyu Wang |
| 2020 | PODC | The Energy Complexity of BFS in Radio Networks. | Yi-Jun Chang, Varsha Dani, Thomas P. Hayes, Seth Pettie |
| 2020 | SODA | The Communication Complexity of Set Intersection and Multiple Equality Testing. | Dawei Huang, Seth Pettie, Yixiang Zhang, Zhijun Zhang |
| 2020 | STOC | Contention resolution without collision detection. | Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul, Seth Pettie |
| 2019 | SODA | Simple Contention Resolution via Multiplicative Weight Updates. | Yi-Jun Chang, Wenyu Jin, Seth Pettie |
| 2019 | SODA | Distributed Triangle Detection via Expander Decomposition. | Yi-Jun Chang, Seth Pettie, Hengjie Zhang |
| 2018 | ESA | Fine-grained Lower Bounds on Cops and Robbers. | Sebastian Brandt, Seth Pettie, Jara Uitto |
| 2018 | ESA | Improved Bounds for Multipass Pairing Heaps and Path-Balanced Binary Search Trees. | Dani Dorfman, Haim Kaplan, Lszl Kozma, Seth Pettie, Uri Zwick |
| 2018 | PODC | The Energy Complexity of Broadcast. | Yi-Jun Chang, Varsha Dani, Thomas P. Hayes, Qizheng He, Wenzheng Li, Seth Pettie |
| 2018 | SODA | The Complexity of Distributed Edge Coloring with Small Palettes. | Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, Jara Uitto |
| 2018 | STOC | An optimal distributed (Δ+1)-coloring algorithm? | Yi-Jun Chang, Wenzheng Li, Seth Pettie |
| 2017 | FOCS | A Time Hierarchy Theorem for the LOCAL Model. | Yi-Jun Chang, Seth Pettie |
| 2017 | SODA | A Hierarchy of Lower Bounds for Sublinear Additive Spanners. | Amir Abboud, Greg Bodwin, Seth Pettie |
| 2017 | SODA | Connectivity Oracles for Graphs Subject to Vertex Failures. | Ran Duan, Seth Pettie |
| 2017 | SODA | Scaling Algorithms for Weighted Matching in General Graphs. | Ran Duan, Seth Pettie, Hsin-Hao Su |
| 2017 | SODA | Fully Dynamic Connectivity in | Shang-En Huang, Dawei Huang, Tsvi Kopelowitz, Seth Pettie |
| 2017 | STOC | Exponential separations in the energy complexity of leader election. | Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie, Ruosong Wang, Wei Zhan |
| 2016 | ESA | Faster Worst Case Deterministic Dynamic Connectivity. | Casper Kejlberg-Rasmussen, Tsvi Kopelowitz, Seth Pettie, Mikkel Thorup |
| 2016 | FOCS | An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model. | Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie |
| 2016 | ISAAC | Mind the Gap: Essentially Optimal Algorithms for Online Dictionary Matching with One Gap. | Amihood Amir, Tsvi Kopelowitz, Avivit Levy, Seth Pettie, Ely Porat, B. Riva Shalom |
| 2016 | PODC | Brief Announcement: An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model. | Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie |
| 2016 | SODA | Higher Lower Bounds from the 3SUM Conjecture. | Tsvi Kopelowitz, Seth Pettie, Ely Porat |
| 2016 | STOC | Contention resolution with log-logstar channel accesses. | Michael A. Bender, Tsvi Kopelowitz, Seth Pettie, Maxwell Young |
| 2015 | SODA | A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs. | Michael Elkin, Seth Pettie |
| 2015 | SODA | (2Δ - l)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting. | Michael Elkin, Seth Pettie, Hsin-Hao Su |
| 2015 | SODA | Sharp Bounds on Formation-free Sequences. | Seth Pettie |
| 2015 | WADS | Dynamic Set Intersection. | Tsvi Kopelowitz, Seth Pettie, Ely Porat |
| 2014 | FOCS | Threesomes, Degenerates, and Love Triangles. | Allan Grnlund Jrgensen, Seth Pettie |
| 2014 | PODC | Distributed algorithms for the Lovsz local lemma and graph coloring. | Kai-Min Chung, Seth Pettie, Hsin-Hao Su |
| 2014 | SPAA | (Near) optimal resource-competitive broadcast with jamming. | Seth Gilbert, Valerie King, Seth Pettie, Ely Porat, Jared Saia, Maxwell Young |
| 2013 | ICALP | Fast Distributed Coloring Algorithms for Triangle-Free Graphs. | Seth Pettie, Hsin-Hao Su |
| 2012 | FOCS | The Locality of Distributed Symmetry Breaking. | Leonid Barenboim, Michael Elkin, Seth Pettie, Johannes Schneider |
| 2010 | FOCS | Approximating Maximum Weight Matching in Near-Linear Time. | Ran Duan, Seth Pettie |
| 2010 | SODA | On Nonlinear Forbidden 0-1 Matrices: A Refutation of a Fredi-Hajnal Conjecture. | Seth Pettie |
| 2010 | SODA | Applications of Forbidden 0-1 Matrices to Search Tree and Path Compression-Based Data Structures. | Seth Pettie |
| 2010 | STOC | Connectivity oracles for failure prone graphs. | Ran Duan, Seth Pettie |
| 2009 | SODA | Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths. | Ran Duan, Seth Pettie |
| 2009 | SODA | Dual-failure distance and connectivity oracles. | Ran Duan, Seth Pettie |
| 2008 | MICRO | Testudo: Heavyweight security analysis via statistical sampling. | Joseph L. Greathouse, Ilya Wagner, David A. Ramos, Gautam Bhatnagar, Todd M. Austin, Valeria Bertacco, Seth Pettie |
| 2008 | PODC | Distributed algorithms for ultrasparse spanners and linear size skeletons. | Seth Pettie |
| 2008 | SODA | Bounded-leg distance and reachability oracles. | Ran Duan, Seth Pettie |
| 2008 | SODA | Splay trees, Davenport-Schinzel sequences, and the deque conjecture. | Seth Pettie |
| 2008 | SPAA | Improved distributed approximate matching. | Zvi Lotker, Boaz Patt-Shamir, Seth Pettie |
| 2007 | ICALP | Low Distortion Spanners. | Seth Pettie |
| 2005 | FOCS | Towards a Final Analysis of Pairing Heaps. | Seth Pettie |
| 2005 | ISAAC | Sensitivity Analysis of Minimum Spanning Trees in Sub-inverse-Ackermann Time. | Seth Pettie |
| 2005 | SODA | New constructions of (alpha, beta)-spanners and purely additive spanners. | Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, Seth Pettie |
| 2005 | WADS | The Complexity of Implicit and Space Efficient Priority Queues. | Christian Worm Mortensen, Seth Pettie |
| 2002 | ALENEX | Experimental Evaluation of a New Shortest Path Algorithm. | Seth Pettie, Vijaya Ramachandran, Srinath Sridhar |
| 2002 | FOCS | An Inverse-Ackermann Style Lower Bound for the Online Minimum Spanning Tree. | Seth Pettie |
| 2002 | ICALP | A Faster All-Pairs Shortest Path Algorithm for Real-Weighted Sparse Graphs. | Seth Pettie |
| 2002 | ISAAC | On the Comparison-Addition Complexity of All-Pairs Shortest Paths. | Seth Pettie |
| 2002 | SODA | Computing shortest paths with comparisons and additions. | Seth Pettie, Vijaya Ramachandran |
| 2002 | SODA | Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms. | Seth Pettie, Vijaya Ramachandran |
| 2000 | ICALP | An Optimal Minimum Spanning Tree Algorithm. | Seth Pettie, Vijaya Ramachandran |