default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDSeth Pettie
Person information
- affiliation: University of Michigan, Department of Electrical Engineering and Computer Science, Ann Arbor, MI, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[j48]Shang-En Huang
, Seth Pettie, Leqi Zhu:
Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection. J. ACM 71(2): 12:1-12:37 (2024)- [c76]Varsha Dani, Thomas P. Hayes, Seth Pettie, Jared Saia:
Fraud Detection for Random Walks. ITCS 2024: 36:1-36:22 - [c75]Parinya Chalermsook, Seth Pettie, Sorrachai Yingchareonthawornchai:
Sorting Pattern-Avoiding Permutations via 0-1 Matrices Forbidding Product Patterns. SODA 2024: 133-149 - [c74]Seth Pettie, Gábor Tardos:
On the Extremal Functions of Acyclic Forbidden 0-1 Matrices. SODA 2024: 1166-1176 - [c73]Merav Parter, Asaf Petruschka, Seth Pettie:
Connectivity Labeling and Routing with Multiple Vertex Failures. STOC 2024: 823-834 - [e1]Merav Parter, Seth Pettie:
2024 Symposium on Simplicity in Algorithms, SOSA 2024, Alexandria, VA, USA, January 8-10, 2024. SIAM 2024, ISBN 978-1-61197-793-6 [contents] - [i53]Seth Pettie, Dingyu Wang:
Fourier Transform-based Estimators for Data Sketches. CoRR abs/2403.15366 (2024) - [i52]Seth Pettie, Gábor Tardos:
A Refutation of the Pach-Tardos Conjecture for 0-1 Matrices. CoRR abs/2407.02638 (2024) - [i51]Seth Pettie, Dingyu Wang:
Universal Perfect Samplers for Incremental Streams. CoRR abs/2407.04931 (2024) - [i50]Seth Pettie, Dingyu Wang:
Sketching, Moment Estimation, and the Lévy-Khintchine Representation Theorem. CoRR abs/2410.17426 (2024) - [i49]Yaowei Long, Seth Pettie, Thatchaphol Saranurak:
Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies. CoRR abs/2410.18885 (2024) - 2023
- [j47]Varsha Dani, Aayush Gupta, Thomas P. Hayes, Seth Pettie:
Wake up and join me! An energy-efficient algorithm for maximal matching in radio networks. Distributed Comput. 36(3): 373-384 (2023) - [j46]Panagiotis Charalampopoulos, Pawel Gawrychowski, Yaowei Long, Shay Mozes, Seth Pettie, Oren Weimann, Christian Wulff-Nilsen:
Almost Optimal Exact Distance Oracles for Planar Graphs. J. ACM 70(2): 12:1-12:50 (2023) - [j45]Shang-En Huang, Dawei Huang, Tsvi Kopelowitz, Seth Pettie, Mikkel Thorup:
Fully Dynamic Connectivity in O(log n(loglog n)2) Amortized Expected Time. TheoretiCS 2 (2023) - [c72]Dingyu Wang, Seth Pettie:
Better Cardinality Estimators for HyperLogLog, PCSA, and Beyond. PODS 2023: 317-327 - [c71]Shang-En Huang, Seth Pettie, Leqi Zhu:
Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection. SODA 2023: 4335-4353 - [i48]Seth Pettie, Gábor Tardos:
On the Extremal Functions of Acyclic Forbidden 0-1 Matrices. CoRR abs/2306.16365 (2023) - [i47]Parinya Chalermsook, Seth Pettie, Sorrachai Yingchareonthawornchai:
Sorting Pattern-Avoiding Permutations via 0-1 Matrices Forbidding Product Patterns. CoRR abs/2307.02294 (2023) - [i46]Merav Parter, Asaf Petruschka, Seth Pettie:
Connectivity Labeling for Multiple Vertex Failures. CoRR abs/2307.06276 (2023) - 2022
- [j44]Dawei Huang, Seth Pettie:
Approximate Generalized Matching: f-Matchings and f-Edge Covers. Algorithmica 84(7): 1952-1992 (2022) - [c70]Seth Pettie, Thatchaphol Saranurak, Longhui Yin:
Optimal vertex connectivity oracles. STOC 2022: 151-161 - [c69]Shang-En Huang, Seth Pettie, Leqi Zhu:
Byzantine agreement in polynomial time with near-optimal resilience. STOC 2022: 502-514 - [i45]Seth Pettie, Thatchaphol Saranurak, Longhui Yin:
Optimal Vertex Connectivity Oracles. CoRR abs/2201.00408 (2022) - [i44]Shang-En Huang, Seth Pettie, Leqi Zhu:
Byzantine Agreement in Polynomial Time with Near-Optimal Resilience. CoRR abs/2202.13452 (2022) - [i43]Shang-En Huang, Seth Pettie, Leqi Zhu:
Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection. CoRR abs/2206.15335 (2022) - [i42]Seth Pettie, Dingyu Wang:
Simpler and Better Cardinality Estimators for HyperLogLog and PCSA. CoRR abs/2208.10578 (2022) - 2021
- [j43]Yi-Jun Chang, Seth Pettie, Thatchaphol Saranurak, Hengjie Zhang:
Near-optimal Distributed Triangle Enumeration via Expander Decompositions. J. ACM 68(3): 21:1-21:36 (2021) - [j42]Dawei Huang, Seth Pettie, Yixiang Zhang, Zhijun Zhang:
The Communication Complexity of Set Intersection and Multiple Equality Testing. SIAM J. Comput. 50(2): 674-717 (2021) - [j41]Shang-En Huang, Seth Pettie:
Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing Shortcuts. SIAM J. Discret. Math. 35(3): 2129-2144 (2021) - [c68]Aaron Bernstein, Aditi Dudeja, Seth Pettie:
Incremental SCC Maintenance in Sparse Graphs. ESA 2021: 14:1-14:16 - [c67]Seth Pettie, Dingyu Wang, Longhui Yin:
Non-Mergeable Sketching for Cardinality Estimation. ICALP 2021: 104:1-104:20 - [c66]Seth Pettie, Longhui Yin:
The Structure of Minimum Vertex Cuts. ICALP 2021: 105:1-105:20 - [c65]Varsha Dani, Aayush Gupta, Thomas P. Hayes, Seth Pettie:
Brief Announcement: Wake Up and Join Me! An Energy Efficient Algorithm for Maximal Matching in Radio Networks. PODC 2021: 151-153 - [c64]Yaowei Long, Seth Pettie:
Planar Distance Oracles with Better Time-Space Tradeoffs. SODA 2021: 2517-2537 - [c63]Seth Pettie, Dingyu Wang:
Information theoretic limits of cardinality estimation: Fisher meets Shannon. STOC 2021: 556-569 - [c62]Varsha Dani, Aayush Gupta, Thomas P. Hayes, Seth Pettie:
Wake up and Join Me! an Energy-Efficient Algorithm for Maximal Matching in Radio Networks. DISC 2021: 19:1-19:14 - [i41]Seth Pettie, Longhui Yin:
The Structure of Minimum Vertex Cuts. CoRR abs/2102.06805 (2021) - [i40]Varsha Dani, Aayush Gupta, Thomas P. Hayes, Seth Pettie:
Wake Up and Join Me! An Energy-Efficient Algorithm for Maximal Matching in Radio Networks. CoRR abs/2104.09096 (2021) - 2020
- [j40]Yi-Jun Chang, Wenzheng Li, Seth Pettie:
Distributed (Δ+1)-Coloring via Ultrafast Graph Shattering. SIAM J. Comput. 49(3): 497-539 (2020) - [j39]Ran Duan, Seth Pettie:
Connectivity Oracles for Graphs Subject to Vertex Failures. SIAM J. Comput. 49(6): 1363-1396 (2020) - [j38]Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, Jara Uitto:
Distributed Edge Coloring and a Special Case of the Constructive Lovász Local Lemma. ACM Trans. Algorithms 16(1): 8:1-8:51 (2020) - [c61]Yi-Jun Chang, Varsha Dani, Thomas P. Hayes, Seth Pettie:
The Energy Complexity of BFS in Radio Networks. PODC 2020: 273-282 - [c60]Dawei Huang, Seth Pettie, Yixiang Zhang, Zhijun Zhang:
The Communication Complexity of Set Intersection and Multiple Equality Testing. SODA 2020: 1715-1732 - [c59]Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul, Seth Pettie:
Contention resolution without collision detection. STOC 2020: 105-118 - [i39]Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul, Seth Pettie:
Contention Resolution Without Collision Detection. CoRR abs/2004.08039 (2020) - [i38]Seth Pettie, Dingyu Wang:
Information Theoretic Limits of Cardinality Estimation: Fisher Meets Shannon. CoRR abs/2007.08051 (2020) - [i37]Yaowei Long, Seth Pettie:
Planar Distance Oracles with Better Time-Space Tradeoffs. CoRR abs/2007.08585 (2020) - [i36]Yi-Jun Chang, Varsha Dani, Thomas P. Hayes, Seth Pettie:
The Energy Complexity of BFS in Radio Networks. CoRR abs/2007.09816 (2020) - [i35]Seth Pettie, Dingyu Wang, Longhui Yin:
Simple and Efficient Cardinality Estimation in Data Streams. CoRR abs/2008.08739 (2020)
2010 – 2019
- 2019
- [j37]Amihood Amir, Tsvi Kopelowitz, Avivit Levy, Seth Pettie, Ely Porat, B. Riva Shalom:
Mind the Gap! - Online Dictionary Matching with One Gap. Algorithmica 81(6): 2123-2157 (2019) - [j36]Shang-En Huang, Seth Pettie:
Thorup-Zwick emulators are universally optimal hopsets. Inf. Process. Lett. 142: 9-13 (2019) - [j35]Dawei Huang, Dong Young Yoon, Seth Pettie, Barzan Mozafari:
Join on Samples: A Theoretical Guide for Practitioners. Proc. VLDB Endow. 13(4): 547-560 (2019) - [j34]Yi-Jun Chang, Seth Pettie:
A Time Hierarchy Theorem for the LOCAL Model. SIAM J. Comput. 48(1): 33-69 (2019) - [j33]Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie:
An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model. SIAM J. Comput. 48(1): 122-143 (2019) - [j32]Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie, Ruosong Wang, Wei Zhan:
Exponential Separations in the Energy Complexity of Leader Election. ACM Trans. Algorithms 15(4): 49:1-49:31 (2019) - [c58]Yi-Jun Chang, Wenyu Jin, Seth Pettie:
Simple Contention Resolution via Multiplicative Weight Updates. SOSA 2019: 16:1-16:16 - [c57]Yi-Jun Chang, Seth Pettie, Hengjie Zhang:
Distributed Triangle Detection via Expander Decomposition. SODA 2019: 821-840 - [i34]Dawei Huang, Seth Pettie, Yixiang Zhang, Zhijun Zhang:
The Communication Complexity of Set Intersection and Multiple Equality Testing. CoRR abs/1908.11825 (2019) - [i33]Dawei Huang, Dong Young Yoon, Seth Pettie, Barzan Mozafari:
Joins on Samples: A Theoretical Guide for Practitioners. CoRR abs/1912.03443 (2019) - 2018
- [j31]Valerie King, Seth Pettie, Jared Saia, Maxwell Young:
A resource-competitive jamming defense. Distributed Comput. 31(6): 419-439 (2018) - [j30]Julian Wellman, Seth Pettie:
Lower bounds on Davenport-Schinzel sequences via rectangular Zarankiewicz matrices. Discret. Math. 341(7): 1987-1993 (2018) - [j29]Allan Grønlund, Seth Pettie:
Threesomes, Degenerates, and Love Triangles. J. ACM 65(4): 22:1-22:25 (2018) - [j28]Michael A. Bender, Tsvi Kopelowitz, Seth Pettie, Maxwell Young:
Contention Resolution with Constant Throughput and Log-Logstar Channel Accesses. SIAM J. Comput. 47(5): 1735-1754 (2018) - [j27]Amir Abboud, Greg Bodwin, Seth Pettie:
A Hierarchy of Lower Bounds for Sublinear Additive Spanners. SIAM J. Comput. 47(6): 2203-2236 (2018) - [j26]Ran Duan, Seth Pettie, Hsin-Hao Su:
Scaling Algorithms for Weighted Matching in General Graphs. ACM Trans. Algorithms 14(1): 8:1-8:35 (2018) - [c56]Sebastian Brandt, Seth Pettie, Jara Uitto:
Fine-grained Lower Bounds on Cops and Robbers. ESA 2018: 9:1-9:12 - [c55]Dani Dorfman, Haim Kaplan, László Kozma, Seth Pettie, Uri Zwick:
Improved Bounds for Multipass Pairing Heaps and Path-Balanced Binary Search Trees. ESA 2018: 24:1-24:13 - [c54]Yi-Jun Chang, Varsha Dani, Thomas P. Hayes, Qizheng He, Wenzheng Li, Seth Pettie:
The Energy Complexity of Broadcast. PODC 2018: 95-104 - [c53]Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, Jara Uitto:
The Complexity of Distributed Edge Coloring with Small Palettes. SODA 2018: 2633-2652 - [c52]Yi-Jun Chang, Wenzheng Li, Seth Pettie:
An optimal distributed (Δ+1)-coloring algorithm? STOC 2018: 445-456 - [c51]Shang-En Huang, Seth Pettie:
Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing shortcuts. SWAT 2018: 26:1-26:12 - [i32]Shang-En Huang, Seth Pettie:
Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing shortcuts. CoRR abs/1802.06271 (2018) - [i31]Dani Dorfman, Haim Kaplan, László Kozma, Seth Pettie, Uri Zwick:
Improved bounds for multipass pairing heaps and path-balanced binary search trees. CoRR abs/1806.08692 (2018) - [i30]Yi-Jun Chang, Seth Pettie, Hengjie Zhang:
Distributed Triangle Detection via Expander Decomposition. CoRR abs/1807.06624 (2018) - 2017
- [j25]Kai-Min Chung, Seth Pettie, Hsin-Hao Su:
Distributed algorithms for the Lovász local lemma and graph coloring. Distributed Comput. 30(4): 261-280 (2017) - [c50]Yi-Jun Chang, Seth Pettie:
A Time Hierarchy Theorem for the LOCAL Model. FOCS 2017: 156-167 - [c49]Aaron Bernstein, Tsvi Kopelowitz, Seth Pettie, Ely Porat, Clifford Stein:
Simultaneously Load Balancing for Every p-norm, With Reassignments. ITCS 2017: 51:1-51:14 - [c48]Ran Duan, Seth Pettie:
Connectivity Oracles for Graphs Subject to Vertex Failures. SODA 2017: 490-509 - [c47]Shang-En Huang, Dawei Huang, Tsvi Kopelowitz, Seth Pettie:
Fully Dynamic Connectivity in O(log n(log log n)2) Amortized Expected Time. SODA 2017: 510-520 - [c46]Amir Abboud, Greg Bodwin, Seth Pettie:
A Hierarchy of Lower Bounds for Sublinear Additive Spanners. SODA 2017: 568-576 - [c45]Ran Duan, Seth Pettie, Hsin-Hao Su:
Scaling Algorithms for Weighted Matching in General Graphs. SODA 2017: 781-800 - [c44]Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie, Ruosong Wang, Wei Zhan:
Exponential separations in the energy complexity of leader election. STOC 2017: 771-783 - [i29]Yi-Jun Chang, Seth Pettie:
A Time Hierarchy Theorem for the LOCAL Model. CoRR abs/1704.06297 (2017) - [i28]Shang-En Huang, Seth Pettie:
Thorup-Zwick Emulators are Universally Optimal Hopsets. CoRR abs/1705.00327 (2017) - [i27]Dawei Huang, Seth Pettie:
Approximate Generalized Matching: $f$-Factors and $f$-Edge Covers. CoRR abs/1706.05761 (2017) - [i26]Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, Jara Uitto:
The Complexity of Distributed Edge Coloring with Small Palettes. CoRR abs/1708.04290 (2017) - [i25]Yi-Jun Chang, Varsha Dani, Thomas P. Hayes, Qizheng He, Wenzheng Li, Seth Pettie:
The Energy Complexity of Broadcast. CoRR abs/1710.01800 (2017) - [i24]Yi-Jun Chang, Wenzheng Li, Seth Pettie:
An Optimal Distributed (Δ+1)-Coloring Algorithm? CoRR abs/1711.01361 (2017) - 2016
- [j24]Leonid Barenboim, Michael Elkin, Seth Pettie, Johannes Schneider:
The Locality of Distributed Symmetry Breaking. J. ACM 63(3): 20:1-20:45 (2016) - [j23]Michael Elkin, Seth Pettie:
A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs. ACM Trans. Algorithms 12(4): 50:1-50:31 (2016) - [c43]Casper Kejlberg-Rasmussen, Tsvi Kopelowitz, Seth Pettie, Mikkel Thorup:
Faster Worst Case Deterministic Dynamic Connectivity. ESA 2016: 53:1-53:15 - [c42]Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie:
An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model. FOCS 2016: 615-624 - [c41]Amihood Amir, Tsvi Kopelowitz, Avivit Levy, Seth Pettie, Ely Porat, B. Riva Shalom:
Mind the Gap: Essentially Optimal Algorithms for Online Dictionary Matching with One Gap. ISAAC 2016: 12:1-12:12 - [c40]Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie:
Brief Announcement: An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model. PODC 2016: 195-197 - [c39]Tsvi Kopelowitz, Seth Pettie, Ely Porat:
Higher Lower Bounds from the 3SUM Conjecture. SODA 2016: 1272-1287 - [c38]Michael A. Bender, Tsvi Kopelowitz, Seth Pettie, Maxwell Young:
Contention resolution with log-logstar channel accesses. STOC 2016: 499-508 - [r6]Seth Pettie:
All Pairs Shortest Paths in Sparse Graphs. Encyclopedia of Algorithms 2016: 52-55 - [r5]Seth Pettie:
Minimum Spanning Trees. Encyclopedia of Algorithms 2016: 1322-1325 - [r4]Seth Pettie:
Single-Source Shortest Paths. Encyclopedia of Algorithms 2016: 1996-1999 - [i23]Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie:
An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model. CoRR abs/1602.08166 (2016) - [i22]Ran Duan, Seth Pettie:
Connectivity Oracles for Graphs Subject to Vertex Failures. CoRR abs/1607.06865 (2016) - [i21]Amir Abboud, Greg Bodwin, Seth Pettie:
A Hierarchy of Lower Bounds for Sublinear Additive Spanners. CoRR abs/1607.07497 (2016) - [i20]Shang-En Huang, Dawei Huang, Tsvi Kopelowitz, Seth Pettie:
Fully Dynamic Connectivity in O(log n(log log n)2) Amortized Expected Time. CoRR abs/1609.05867 (2016) - [i19]Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie, Ruosong Wang, Wei Zhan:
How to Elect a Low-energy Leader. CoRR abs/1609.08486 (2016) - [i18]Julian Wellman, Seth Pettie:
Lower Bounds on Davenport-Schinzel Sequences via Rectangular Zarankiewicz Matrices. CoRR abs/1610.09774 (2016) - [i17]Moshe Lewenstein, Seth Pettie, Virginia Vassilevska Williams:
Structure and Hardness in P (Dagstuhl Seminar 16451). Dagstuhl Reports 6(11): 1-34 (2016) - 2015
- [j22]Seth Pettie, Hsin-Hao Su:
Distributed coloring algorithms for triangle-free graphs. Inf. Comput. 243: 263-280 (2015) - [j21]Seth Pettie:
Sharp Bounds on Davenport-Schinzel Sequences of Every Order. J. ACM 62(5): 36:1-36:40 (2015) - [j20]Zvi Lotker, Boaz Patt-Shamir, Seth Pettie:
Improved Distributed Approximate Matching. J. ACM 62(5): 38:1-38:17 (2015) - [j19]Seth Pettie:
Sensitivity Analysis of Minimum Spanning Trees in Sub-Inverse-Ackermann Time. J. Graph Algorithms Appl. 19(1): 375-391 (2015) - [j18]Seth Pettie:
Three Generalizations of Davenport-Schinzel Sequences. SIAM J. Discret. Math. 29(4): 2189-2238 (2015) - [j17]Michael A. Bender, Jeremy T. Fineman, Mahnush Movahedi, Jared Saia, Varsha Dani, Seth Gilbert, Seth Pettie, Maxwell Young:
Resource-Competitive Algorithms. SIGACT News 46(3): 57-71 (2015) - [c37]Michael Elkin, Seth Pettie, Hsin-Hao Su:
(2Δ - l)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting. SODA 2015: 355-370 - [c36]Seth Pettie:
Sharp Bounds on Formation-free Sequences. SODA 2015: 592-604 - [c35]Michael Elkin, Seth Pettie:
A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs. SODA 2015: 805-821 - [c34]Tsvi Kopelowitz, Seth Pettie, Ely Porat:
Dynamic Set Intersection. WADS 2015: 470-481 - [i16]Amihood Amir, Tsvi Kopelowitz, Avivit Levy, Seth Pettie, Ely Porat, B. Riva Shalom:
Online Dictionary Matching with One Gap. CoRR abs/1503.07563 (2015) - [i15]Michael Elkin, Seth Pettie:
A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs. CoRR abs/1506.08392 (2015) - [i14]Casper Kejlberg-Rasmussen, Tsvi Kopelowitz, Seth Pettie, Mikkel Thorup:
Deterministic Worst Case Dynamic Connectivity: Simpler and Faster. CoRR abs/1507.05944 (2015) - 2014
- [j16]Ran Duan, Seth Pettie:
Linear-Time Approximation for Maximum Weight Matching. J. ACM 61(1): 1:1-1:23 (2014) - [c33]Allan Grønlund Jørgensen, Seth Pettie:
Threesomes, Degenerates, and Love Triangles. FOCS 2014: 621-630 - [c32]