Seth Pettie - RankMe

194 papers A* 58A 9B 7Journal 104Unranked 9

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Contention Resolution, With and Without a Global Clock. CoRR Zixi Cai, Kuowen Chen, Shengquan Du, Tsvi Kopelowitz, Seth Pettie, Ben Plosk
2026	A*	`conf`	On a Clique Game and the Erdős-Hajnal Problem on High-Chromatic High-Girth Subgraphs. SODA Seth Pettie, Gábor Tardos, Bartosz Walczak
2026	J	`jnl`	Space Complexity of Vertex Connectivity Oracles. SIAM J. Comput. Seth Pettie, Thatchaphol Saranurak, Longhui Yin
2025	A*	`conf`	A Refutation of the Pach-Tardos Conjecture for 0-1 Matrices. SODA Seth Pettie, Gábor Tardos
2025	J	`jnl`	A Refutation of the Pach-Tardos Conjecture for 0-1 Matrices. Comb. Seth Pettie, Gábor Tardos
2025	A*	`conf`	Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies. SODA Yaowei Long, Seth Pettie, Thatchaphol Saranurak
2025	J	`jnl`	Reviving Thorup's Shortcut Conjecture. CoRR Aaron Bernstein, Henry L. Fleischmann, Maximilian Probst Gutenberg, Bernhard Haeupler, Gary Hoppenworth, Yonggang Jiang, George Z. Li, Seth Pettie, Thatchaphol Saranurak, Leon Schiller
2025	A	`conf`	Sketching, Moment Estimation, and the Lévy-Khintchine Representation Theorem. ITCS Seth Pettie, Dingyu Wang
2025	J	`jnl`	The Squishy Grid Problem. CoRR Zixi Cai, Kuowen Chen, Shengquan Du, Arnold Filtser, Seth Pettie, Daniel Skora
2025	A*	`conf`	Universal Perfect Samplers for Incremental Streams. SODA Seth Pettie, Dingyu Wang
2024	—	`ed.`	2024 Symposium on Simplicity in Algorithms, SOSA 2024, Alexandria, VA, USA, January 8-10, 2024 SOSA Merav Parter, Seth Pettie
2024	J	`jnl`	A Refutation of the Pach-Tardos Conjecture for 0-1 Matrices. CoRR Seth Pettie, Gábor Tardos
2024	J	`jnl`	Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection. J. ACM Shang-En Huang, Seth Pettie, Leqi Zhu
2024	J	`jnl`	Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies. CoRR Yaowei Long, Seth Pettie, Thatchaphol Saranurak
2024	A*	`conf`	Connectivity Labeling and Routing with Multiple Vertex Failures. STOC Merav Parter, Asaf Petruschka, Seth Pettie
2024	J	`jnl`	Fourier Transform-based Estimators for Data Sketches. CoRR Seth Pettie, Dingyu Wang
2024	A	`conf`	Fraud Detection for Random Walks. ITCS Varsha Dani, Thomas P. Hayes, Seth Pettie, Jared Saia
2024	A*	`conf`	On the Extremal Functions of Acyclic Forbidden 0-1 Matrices. SODA Seth Pettie, Gábor Tardos
2024	J	`jnl`	Sketching, Moment Estimation, and the Lévy-Khintchine Representation Theorem. CoRR Seth Pettie, Dingyu Wang
2024	A*	`conf`	Sorting Pattern-Avoiding Permutations via 0-1 Matrices Forbidding Product Patterns. SODA Parinya Chalermsook, Seth Pettie, Sorrachai Yingchareonthawornchai
2024	J	`jnl`	Universal Perfect Samplers for Incremental Streams. CoRR Seth Pettie, Dingyu Wang
2023	J	`jnl`	Almost Optimal Exact Distance Oracles for Planar Graphs. J. ACM Panagiotis Charalampopoulos, Pawel Gawrychowski, Yaowei Long, Shay Mozes, Seth Pettie, Oren Weimann, Christian Wulff-Nilsen
2023	A*	`conf`	Better Cardinality Estimators for HyperLogLog, PCSA, and Beyond. PODS Dingyu Wang, Seth Pettie
2023	A*	`conf`	Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection. SODA Shang-En Huang, Seth Pettie, Leqi Zhu
2023	J	`jnl`	Connectivity Labeling for Multiple Vertex Failures. CoRR Merav Parter, Asaf Petruschka, Seth Pettie
2023	J	`jnl`	Fully Dynamic Connectivity in O(log n(loglog n) TheoretiCS Shang-En Huang, Dawei Huang, Tsvi Kopelowitz, Seth Pettie, Mikkel Thorup
2023	J	`jnl`	On the Extremal Functions of Acyclic Forbidden 0-1 Matrices. CoRR Seth Pettie, Gábor Tardos
2023	J	`jnl`	Sorting Pattern-Avoiding Permutations via 0-1 Matrices Forbidding Product Patterns. CoRR Parinya Chalermsook, Seth Pettie, Sorrachai Yingchareonthawornchai
2023	J	`jnl`	Wake up and join me! An energy-efficient algorithm for maximal matching in radio networks. Distributed Comput. Varsha Dani, Aayush Gupta, Thomas P. Hayes, Seth Pettie
2022	J	`jnl`	Approximate Generalized Matching: f-Matchings and f-Edge Covers. Algorithmica Dawei Huang, Seth Pettie
2022	J	`jnl`	Byzantine Agreement in Polynomial Time with Near-Optimal Resilience. CoRR Shang-En Huang, Seth Pettie, Leqi Zhu
2022	J	`jnl`	Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection. CoRR Shang-En Huang, Seth Pettie, Leqi Zhu
2022	A*	`conf`	Byzantine agreement in polynomial time with near-optimal resilience. STOC Shang-En Huang, Seth Pettie, Leqi Zhu
2022	J	`jnl`	Optimal Vertex Connectivity Oracles. CoRR Seth Pettie, Thatchaphol Saranurak, Longhui Yin
2022	A*	`conf`	Optimal vertex connectivity oracles. STOC Seth Pettie, Thatchaphol Saranurak, Longhui Yin
2022	J	`jnl`	Simpler and Better Cardinality Estimators for HyperLogLog and PCSA. CoRR Seth Pettie, Dingyu Wang
2021	A*	`conf`	Brief Announcement: Wake Up and Join Me! An Energy Efficient Algorithm for Maximal Matching in Radio Networks. PODC Varsha Dani, Aayush Gupta, Thomas P. Hayes, Seth Pettie
2021	A	`conf`	Incremental SCC Maintenance in Sparse Graphs. ESA Aaron Bernstein, Aditi Dudeja, Seth Pettie
2021	A*	`conf`	Information theoretic limits of cardinality estimation: Fisher meets Shannon. STOC Seth Pettie, Dingyu Wang
2021	J	`jnl`	Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing Shortcuts. SIAM J. Discret. Math. Shang-En Huang, Seth Pettie
2021	J	`jnl`	Near-optimal Distributed Triangle Enumeration via Expander Decompositions. J. ACM Yi-Jun Chang, Seth Pettie, Thatchaphol Saranurak, Hengjie Zhang
2021	A*	`conf`	Non-Mergeable Sketching for Cardinality Estimation. ICALP Seth Pettie, Dingyu Wang, Longhui Yin
2021	A*	`conf`	Planar Distance Oracles with Better Time-Space Tradeoffs. SODA Yaowei Long, Seth Pettie
2021	J	`jnl`	The Communication Complexity of Set Intersection and Multiple Equality Testing. SIAM J. Comput. Dawei Huang, Seth Pettie, Yixiang Zhang, Zhijun Zhang
2021	A*	`conf`	The Structure of Minimum Vertex Cuts. ICALP Seth Pettie, Longhui Yin
2021	J	`jnl`	The Structure of Minimum Vertex Cuts. CoRR Seth Pettie, Longhui Yin
2021	J	`jnl`	Wake Up and Join Me! An Energy-Efficient Algorithm for Maximal Matching in Radio Networks. CoRR Varsha Dani, Aayush Gupta, Thomas P. Hayes, Seth Pettie
2021	A	`conf`	Wake up and Join Me! an Energy-Efficient Algorithm for Maximal Matching in Radio Networks. DISC Varsha Dani, Aayush Gupta, Thomas P. Hayes, Seth Pettie
2020	J	`jnl`	Connectivity Oracles for Graphs Subject to Vertex Failures. SIAM J. Comput. Ran Duan, Seth Pettie
2020	J	`jnl`	Contention Resolution Without Collision Detection. CoRR Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul, Seth Pettie
2020	A*	`conf`	Contention resolution without collision detection. STOC Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul, Seth Pettie
2020	J	`jnl`	Distributed (Δ+1)-Coloring via Ultrafast Graph Shattering. SIAM J. Comput. Yi-Jun Chang, Wenzheng Li, Seth Pettie
2020	J	`jnl`	Distributed Edge Coloring and a Special Case of the Constructive Lovász Local Lemma. ACM Trans. Algorithms Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, Jara Uitto
2020	J	`jnl`	Information Theoretic Limits of Cardinality Estimation: Fisher Meets Shannon. CoRR Seth Pettie, Dingyu Wang
2020	J	`jnl`	Planar Distance Oracles with Better Time-Space Tradeoffs. CoRR Yaowei Long, Seth Pettie
2020	J	`jnl`	Simple and Efficient Cardinality Estimation in Data Streams. CoRR Seth Pettie, Dingyu Wang, Longhui Yin
2020	A*	`conf`	The Communication Complexity of Set Intersection and Multiple Equality Testing. SODA Dawei Huang, Seth Pettie, Yixiang Zhang, Zhijun Zhang
2020	A*	`conf`	The Energy Complexity of BFS in Radio Networks. PODC Yi-Jun Chang, Varsha Dani, Thomas P. Hayes, Seth Pettie
2020	J	`jnl`	The Energy Complexity of BFS in Radio Networks. CoRR Yi-Jun Chang, Varsha Dani, Thomas P. Hayes, Seth Pettie
2019	J	`jnl`	A Time Hierarchy Theorem for the LOCAL Model. SIAM J. Comput. Yi-Jun Chang, Seth Pettie
2019	J	`jnl`	An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model. SIAM J. Comput. Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie
2019	A*	`conf`	Distributed Triangle Detection via Expander Decomposition. SODA Yi-Jun Chang, Seth Pettie, Hengjie Zhang
2019	J	`jnl`	Exponential Separations in the Energy Complexity of Leader Election. ACM Trans. Algorithms Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie, Ruosong Wang, Wei Zhan
2019	J	`jnl`	Join on Samples: A Theoretical Guide for Practitioners. Proc. VLDB Endow. Dawei Huang, Dong Young Yoon, Seth Pettie, Barzan Mozafari
2019	J	`jnl`	Joins on Samples: A Theoretical Guide for Practitioners. CoRR Dawei Huang, Dong Young Yoon, Seth Pettie, Barzan Mozafari
2019	J	`jnl`	Mind the Gap! - Online Dictionary Matching with One Gap. Algorithmica Amihood Amir, Tsvi Kopelowitz, Avivit Levy, Seth Pettie, Ely Porat, B. Riva Shalom
2019	—	`conf`	Simple Contention Resolution via Multiplicative Weight Updates. SOSA Yi-Jun Chang, Wenyu Jin, Seth Pettie
2019	J	`jnl`	The Communication Complexity of Set Intersection and Multiple Equality Testing. CoRR Dawei Huang, Seth Pettie, Yixiang Zhang, Zhijun Zhang
2019	J	`jnl`	Thorup-Zwick emulators are universally optimal hopsets. Inf. Process. Lett. Shang-En Huang, Seth Pettie
2018	J	`jnl`	A Hierarchy of Lower Bounds for Sublinear Additive Spanners. SIAM J. Comput. Amir Abboud, Greg Bodwin, Seth Pettie
2018	J	`jnl`	A resource-competitive jamming defense. Distributed Comput. Valerie King, Seth Pettie, Jared Saia, Maxwell Young
2018	A*	`conf`	An optimal distributed (Δ+1)-coloring algorithm? STOC Yi-Jun Chang, Wenzheng Li, Seth Pettie
2018	J	`jnl`	Contention Resolution with Constant Throughput and Log-Logstar Channel Accesses. SIAM J. Comput. Michael A. Bender, Tsvi Kopelowitz, Seth Pettie, Maxwell Young
2018	J	`jnl`	Distributed Triangle Detection via Expander Decomposition. CoRR Yi-Jun Chang, Seth Pettie, Hengjie Zhang
2018	A	`conf`	Fine-grained Lower Bounds on Cops and Robbers. ESA Sebastian Brandt, Seth Pettie, Jara Uitto
2018	A	`conf`	Improved Bounds for Multipass Pairing Heaps and Path-Balanced Binary Search Trees. ESA Dani Dorfman, Haim Kaplan, László Kozma, Seth Pettie, Uri Zwick
2018	J	`jnl`	Improved bounds for multipass pairing heaps and path-balanced binary search trees. CoRR Dani Dorfman, Haim Kaplan, László Kozma, Seth Pettie, Uri Zwick
2018	—	`conf`	Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing shortcuts. SWAT Shang-En Huang, Seth Pettie
2018	J	`jnl`	Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing shortcuts. CoRR Shang-En Huang, Seth Pettie
2018	J	`jnl`	Lower bounds on Davenport-Schinzel sequences via rectangular Zarankiewicz matrices. Discret. Math. Julian Wellman, Seth Pettie
2018	J	`jnl`	Scaling Algorithms for Weighted Matching in General Graphs. ACM Trans. Algorithms Ran Duan, Seth Pettie, Hsin-Hao Su
2018	A*	`conf`	The Complexity of Distributed Edge Coloring with Small Palettes. SODA Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, Jara Uitto
2018	A*	`conf`	The Energy Complexity of Broadcast. PODC Yi-Jun Chang, Varsha Dani, Thomas P. Hayes, Qizheng He, Wenzheng Li, Seth Pettie
2018	J	`jnl`	Threesomes, Degenerates, and Love Triangles. J. ACM Allan Grønlund, Seth Pettie
2017	A*	`conf`	A Hierarchy of Lower Bounds for Sublinear Additive Spanners. SODA Amir Abboud, Greg Bodwin, Seth Pettie
2017	A*	`conf`	A Time Hierarchy Theorem for the LOCAL Model. FOCS Yi-Jun Chang, Seth Pettie
2017	J	`jnl`	A Time Hierarchy Theorem for the LOCAL Model. CoRR Yi-Jun Chang, Seth Pettie
2017	J	`jnl`	An Optimal Distributed (Δ+1)-Coloring Algorithm? CoRR Yi-Jun Chang, Wenzheng Li, Seth Pettie
2017	J	`jnl`	Approximate Generalized Matching: $f$-Factors and $f$-Edge Covers. CoRR Dawei Huang, Seth Pettie
2017	A*	`conf`	Connectivity Oracles for Graphs Subject to Vertex Failures. SODA Ran Duan, Seth Pettie
2017	J	`jnl`	Distributed algorithms for the Lovász local lemma and graph coloring. Distributed Comput. Kai-Min Chung, Seth Pettie, Hsin-Hao Su
2017	A*	`conf`	Exponential separations in the energy complexity of leader election. STOC Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie, Ruosong Wang, Wei Zhan
2017	A*	`conf`	Fully Dynamic Connectivity in SODA Shang-En Huang, Dawei Huang, Tsvi Kopelowitz, Seth Pettie
2017	A*	`conf`	Scaling Algorithms for Weighted Matching in General Graphs. SODA Ran Duan, Seth Pettie, Hsin-Hao Su
2017	A	`conf`	Simultaneously Load Balancing for Every p-norm, With Reassignments. ITCS Aaron Bernstein, Tsvi Kopelowitz, Seth Pettie, Ely Porat, Clifford Stein
2017	J	`jnl`	The Complexity of Distributed Edge Coloring with Small Palettes. CoRR Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, Jara Uitto
2017	J	`jnl`	The Energy Complexity of Broadcast. CoRR Yi-Jun Chang, Varsha Dani, Thomas P. Hayes, Qizheng He, Wenzheng Li, Seth Pettie
2017	J	`jnl`	Thorup-Zwick Emulators are Universally Optimal Hopsets. CoRR Shang-En Huang, Seth Pettie
2016	J	`jnl`	A Hierarchy of Lower Bounds for Sublinear Additive Spanners. CoRR Amir Abboud, Greg Bodwin, Seth Pettie
2016	J	`jnl`	A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs. ACM Trans. Algorithms Michael Elkin, Seth Pettie
2016	—	`ch.`	All Pairs Shortest Paths in Sparse Graphs. Encyclopedia of Algorithms Seth Pettie
2016	J	`jnl`	An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model. CoRR Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie
2016	A*	`conf`	An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model. FOCS Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie
2016	A*	`conf`	Brief Announcement: An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model. PODC Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie
2016	J	`jnl`	Connectivity Oracles for Graphs Subject to Vertex Failures. CoRR Ran Duan, Seth Pettie
2016	A*	`conf`	Contention resolution with log-logstar channel accesses. STOC Michael A. Bender, Tsvi Kopelowitz, Seth Pettie, Maxwell Young
2016	A	`conf`	Faster Worst Case Deterministic Dynamic Connectivity. ESA Casper Kejlberg-Rasmussen, Tsvi Kopelowitz, Seth Pettie, Mikkel Thorup
2016	J	`jnl`	Fully Dynamic Connectivity in O(log n(log log n) CoRR Shang-En Huang, Dawei Huang, Tsvi Kopelowitz, Seth Pettie
2016	A*	`conf`	Higher Lower Bounds from the 3SUM Conjecture. SODA Tsvi Kopelowitz, Seth Pettie, Ely Porat
2016	J	`jnl`	How to Elect a Low-energy Leader. CoRR Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie, Ruosong Wang, Wei Zhan
2016	J	`jnl`	Lower Bounds on Davenport-Schinzel Sequences via Rectangular Zarankiewicz Matrices. CoRR Julian Wellman, Seth Pettie
2016	B	`conf`	Mind the Gap: Essentially Optimal Algorithms for Online Dictionary Matching with One Gap. ISAAC Amihood Amir, Tsvi Kopelowitz, Avivit Levy, Seth Pettie, Ely Porat, B. Riva Shalom
2016	—	`ch.`	Minimum Spanning Trees. Encyclopedia of Algorithms Seth Pettie
2016	—	`ch.`	Single-Source Shortest Paths. Encyclopedia of Algorithms Seth Pettie
2016	J	`jnl`	Structure and Hardness in P (Dagstuhl Seminar 16451). Dagstuhl Reports Moshe Lewenstein, Seth Pettie, Virginia Vassilevska Williams
2016	J	`jnl`	The Locality of Distributed Symmetry Breaking. J. ACM Leonid Barenboim, Michael Elkin, Seth Pettie, Johannes Schneider
2015	A*	`conf`	(2Δ - l)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting. SODA Michael Elkin, Seth Pettie, Hsin-Hao Su
2015	A*	`conf`	A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs. SODA Michael Elkin, Seth Pettie
2015	J	`jnl`	A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs. CoRR Michael Elkin, Seth Pettie
2015	J	`jnl`	Deterministic Worst Case Dynamic Connectivity: Simpler and Faster. CoRR Casper Kejlberg-Rasmussen, Tsvi Kopelowitz, Seth Pettie, Mikkel Thorup
2015	J	`jnl`	Distributed coloring algorithms for triangle-free graphs. Inf. Comput. Seth Pettie, Hsin-Hao Su
2015	B	`conf`	Dynamic Set Intersection. WADS Tsvi Kopelowitz, Seth Pettie, Ely Porat
2015	J	`jnl`	Improved Distributed Approximate Matching. J. ACM Zvi Lotker, Boaz Patt-Shamir, Seth Pettie
2015	J	`jnl`	Online Dictionary Matching with One Gap. CoRR Amihood Amir, Tsvi Kopelowitz, Avivit Levy, Seth Pettie, Ely Porat, B. Riva Shalom
2015	J	`jnl`	Resource-Competitive Algorithms. SIGACT News Michael A. Bender, Jeremy T. Fineman, Mahnush Movahedi, Jared Saia, Varsha Dani, Seth Gilbert, Seth Pettie, Maxwell Young
2015	J	`jnl`	Sensitivity Analysis of Minimum Spanning Trees in Sub-Inverse-Ackermann Time. J. Graph Algorithms Appl. Seth Pettie
2015	J	`jnl`	Sharp Bounds on Davenport-Schinzel Sequences of Every Order. J. ACM Seth Pettie
2015	A*	`conf`	Sharp Bounds on Formation-free Sequences. SODA Seth Pettie
2015	J	`jnl`	Three Generalizations of Davenport-Schinzel Sequences. SIAM J. Discret. Math. Seth Pettie
2014	B	`conf`	(Near) optimal resource-competitive broadcast with jamming. SPAA Seth Gilbert, Valerie King, Seth Pettie, Ely Porat, Jared Saia, Maxwell Young
2014	J	`jnl`	3SUM Hardness in (Dynamic) Data Structures. CoRR Tsvi Kopelowitz, Seth Pettie, Ely Porat
2014	A*	`conf`	Distributed algorithms for the Lovász local lemma and graph coloring. PODC Kai-Min Chung, Seth Pettie, Hsin-Hao Su
2014	J	`jnl`	Linear-Time Approximation for Maximum Weight Matching. J. ACM Ran Duan, Seth Pettie
2014	J	`jnl`	Sensitivity Analysis of Minimum Spanning Trees in Sub-Inverse-Ackermann Time. CoRR Seth Pettie
2014	J	`jnl`	Three Generalizations of Davenport-Schinzel Sequences. CoRR Seth Pettie
2014	A*	`conf`	Threesomes, Degenerates, and Love Triangles. FOCS Allan Grønlund Jørgensen, Seth Pettie
2014	J	`jnl`	Threesomes, Degenerates, and Love Triangles. CoRR Allan Grønlund Jørgensen, Seth Pettie
2014	J	`jnl`	Word-packing Algorithms for Dynamic Connectivity and Dynamic Sets. CoRR Casper Kejlberg-Rasmussen, Tsvi Kopelowitz, Seth Pettie, Ely Porat
2013	—	`conf`	Fast Distributed Coloring Algorithms for Triangle-Free Graphs. ICALP (2) Seth Pettie, Hsin-Hao Su
2013	A*	`conf`	Sharp bounds on Davenport-Schinzel sequences of every order. SoCG Seth Pettie
2012	J	`jnl`	A simple reduction from maximum weight matching to maximum cardinality matching. Inf. Process. Lett. Seth Pettie
2012	J	`jnl`	Connectivity Oracles for Planar Graphs CoRR Glencora Borradaile, Seth Pettie, Christian Wulff-Nilsen
2012	—	`conf`	Connectivity Oracles for Planar Graphs. SWAT Glencora Borradaile, Seth Pettie, Christian Wulff-Nilsen
2012	J	`jnl`	Fast Distributed Algorithms for Maximal Matching and Maximal Independent Set CoRR Leonid Barenboim, Michael Elkin, Seth Pettie, Johannes Schneider
2012	J	`jnl`	Special Section on the Forty-Third Annual ACM Symposium on Theory of Computing (STOC 2011). SIAM J. Comput. Kousha Etessami, Dieter van Melkebeek, Seth Pettie, John Watrous, Salil P. Vadhan
2012	A*	`conf`	The Locality of Distributed Symmetry Breaking. FOCS Leonid Barenboim, Michael Elkin, Seth Pettie, Johannes Schneider
2012	J	`jnl`	Tightish Bounds on Davenport-Schinzel Sequences CoRR Seth Pettie
2011	J	`jnl`	Degrees of nonlinearity in forbidden 0-1 matrix problems. Discret. Math. Seth Pettie
2011	J	`jnl`	Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts. J. Comb. Theory A Seth Pettie
2011	—	`conf`	On the structure and composition of forbidden sequences, with geometric applications. SCG Seth Pettie
2011	J	`jnl`	Origins of Nonlinearity in Davenport-Schinzel Sequences. SIAM J. Discret. Math. Seth Pettie
2011	J	`jnl`	Scaling algorithms for approximate and exact maximum weight matching CoRR Ran Duan, Seth Pettie, Hsin-Hao Su
2010	J	`jnl`	Additive spanners and (alpha, beta)-spanners. ACM Trans. Algorithms Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, Seth Pettie
2010	A*	`conf`	Applications of Forbidden 0-1 Matrices to Search Tree and Path Compression-Based Data Structures. SODA Seth Pettie
2010	A*	`conf`	Approximating Maximum Weight Matching in Near-Linear Time. FOCS Ran Duan, Seth Pettie
2010	A*	`conf`	Connectivity oracles for failure prone graphs. STOC Ran Duan, Seth Pettie
2010	J	`jnl`	Distributed algorithms for ultrasparse spanners and linear size skeletons. Distributed Comput. Seth Pettie
2010	A*	`conf`	On Nonlinear Forbidden 0-1 Matrices: A Refutation of a Füredi-Hajnal Conjecture. SODA Seth Pettie
2009	A*	`conf`	Dual-failure distance and connectivity oracles. SODA Ran Duan, Seth Pettie
2009	A*	`conf`	Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths. SODA Ran Duan, Seth Pettie
2009	J	`jnl`	Low distortion spanners. ACM Trans. Algorithms Seth Pettie
2008	—	`ch.`	All Pairs Shortest Paths in Sparse Graphs. Encyclopedia of Algorithms Seth Pettie
2008	A*	`conf`	Bounded-leg distance and reachability oracles. SODA Ran Duan, Seth Pettie
2008	A*	`conf`	Distributed algorithms for ultrasparse spanners and linear size skeletons. PODC Seth Pettie
2008	B	`conf`	Improved distributed approximate matching. SPAA Zvi Lotker, Boaz Patt-Shamir, Seth Pettie
2008	—	`ch.`	Minimum Spanning Trees. Encyclopedia of Algorithms Seth Pettie
2008	J	`jnl`	Randomized minimum spanning tree algorithms using exponentially fewer random bits. ACM Trans. Algorithms Seth Pettie, Vijaya Ramachandran
2008	—	`ch.`	Single-Source Shortest Paths. Encyclopedia of Algorithms Seth Pettie
2008	—	`conf`	Sources of Superlinearity in Davenport-Schinzel Sequences. Data Structures Seth Pettie
2008	A*	`conf`	Splay trees, Davenport-Schinzel sequences, and the deque conjecture. SODA Seth Pettie
2008	A*	`conf`	Testudo: Heavyweight security analysis via statistical sampling. MICRO Joseph L. Greathouse, Ilya Wagner, David A. Ramos, Gautam Bhatnagar, Todd M. Austin, Valeria Bertacco, Seth Pettie
2007	A*	`conf`	Low Distortion Spanners. ICALP Seth Pettie
2007	J	`jnl`	Sources of Superlinearity in Davenport-Schinzel Sequences CoRR Seth Pettie
2007	J	`jnl`	Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture CoRR Seth Pettie
2006	J	`jnl`	An Inverse-Ackermann Type Lower Bound For Online Minimum Spanning Tree Verification. Comb. Seth Pettie
2006	—	`conf`	Towards a Final Analysis of Pairing Heaps. Data Structures Seth Pettie
2005	J	`jnl`	A Shortest Path Algorithm for Real-Weighted Undirected Graphs. SIAM J. Comput. Seth Pettie, Vijaya Ramachandran
2005	A*	`conf`	New constructions of (alpha, beta)-spanners and purely additive spanners. SODA Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, Seth Pettie
2005	B	`conf`	Sensitivity Analysis of Minimum Spanning Trees in Sub-inverse-Ackermann Time. ISAAC Seth Pettie
2005	B	`conf`	The Complexity of Implicit and Space Efficient Priority Queues. WADS Christian Worm Mortensen, Seth Pettie
2005	A*	`conf`	Towards a Final Analysis of Pairing Heaps. FOCS Seth Pettie
2004	J	`jnl`	A new approach to all-pairs shortest paths on real-weighted graphs. Theor. Comput. Sci. Seth Pettie
2004	J	`jnl`	A simpler linear time 2/3-epsilon approximation for maximum weight matching. Inf. Process. Lett. Seth Pettie, Peter Sanders
2002	A*	`conf`	A Faster All-Pairs Shortest Path Algorithm for Real-Weighted Sparse Graphs. ICALP Seth Pettie
2002	J	`jnl`	A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest. SIAM J. Comput. Seth Pettie, Vijaya Ramachandran
2002	A*	`conf`	An Inverse-Ackermann Style Lower Bound for the Online Minimum Spanning Tree. FOCS Seth Pettie
2002	J	`jnl`	An optimal minimum spanning tree algorithm. J. ACM Seth Pettie, Vijaya Ramachandran
2002	A*	`conf`	Computing shortest paths with comparisons and additions. SODA Seth Pettie, Vijaya Ramachandran
2002	A	`conf`	Experimental Evaluation of a New Shortest Path Algorithm. ALENEX Seth Pettie, Vijaya Ramachandran, Srinath Sridhar
2002	A*	`conf`	Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms. SODA Seth Pettie, Vijaya Ramachandran
2002	B	`conf`	On the Comparison-Addition Complexity of All-Pairs Shortest Paths. ISAAC Seth Pettie
2002	—	`conf`	The Dynamic Vertex Minimum Problem and Its Application to Clustering-Type Approximation Algorithms. SWAT Harold N. Gabow, Seth Pettie
2000	A*	`conf`	An Optimal Minimum Spanning Tree Algorithm. ICALP Seth Pettie, Vijaya Ramachandran
1999	—	`conf`	A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest. RANDOM-APPROX Seth Pettie, Vijaya Ramachandran