% csauthors.net - beta - BibTeX bibliography of Seth Pettie
@inproceedings{conf/alenex/PettieRS02,
title = {Experimental Evaluation of a New Shortest Path Algorithm.},
year = {2002},
booktitle = {ALENEX},
author = {{Seth Pettie} and {Vijaya Ramachandran} and {Srinath Sridhar 001}},
publisher = {Springer},
booktitle = {Algorithm Engineering and Experiments, 4th International Workshop, ALENEX 2002, San Francisco, CA, USA, January 4-5, 2002, Revised Papers}
}
@inproceedings{conf/focs/Pettie02,
title = {An Inverse-Ackermann Style Lower Bound for the Online Minimum Spanning Tree.},
year = {2002},
booktitle = {FOCS},
author = {{Seth Pettie}},
publisher = {IEEE Computer Society},
booktitle = {43rd Symposium on Foundations of Computer Science (FOCS 2002), 16-19 November 2002, Vancouver, BC, Canada, Proceedings}
}
@inproceedings{conf/icalp/Pettie02,
title = {A Faster All-Pairs Shortest Path Algorithm for Real-Weighted Sparse Graphs.},
year = {2002},
booktitle = {ICALP},
author = {{Seth Pettie}},
publisher = {Springer},
booktitle = {Automata, Languages and Programming, 29th International Colloquium, ICALP 2002, Malaga, Spain, July 8-13, 2002, Proceedings}
}
@inproceedings{conf/isaac/Pettie02,
title = {On the Comparison-Addition Complexity of All-Pairs Shortest Paths.},
year = {2002},
booktitle = {ISAAC},
author = {{Seth Pettie}},
publisher = {Springer},
booktitle = {Algorithms and Computation, 13th International Symposium, ISAAC 2002 Vancouver, BC, Canada, November 21-23, 2002, Proceedings}
}
@inproceedings{conf/soda/PettieR02,
title = {Computing shortest paths with comparisons and additions.},
year = {2002},
booktitle = {SODA},
author = {{Seth Pettie} and {Vijaya Ramachandran}},
publisher = {ACM/SIAM},
booktitle = {Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6-8, 2002, San Francisco, CA, USA.}
}
@inproceedings{conf/soda/PettieR02a,
title = {Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms.},
year = {2002},
booktitle = {SODA},
author = {{Seth Pettie} and {Vijaya Ramachandran}},
publisher = {ACM/SIAM},
booktitle = {Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6-8, 2002, San Francisco, CA, USA.}
}
@inproceedings{conf/swat/GabowP02,
title = {The Dynamic Vertex Minimum Problem and Its Application to Clustering-Type Approximation Algorithms.},
year = {2002},
booktitle = {SWAT},
author = {{Harold N. Gabow} and {Seth Pettie}},
publisher = {Springer},
booktitle = {Algorithm Theory - SWAT 2002, 8th Scandinavian Workshop on Algorithm Theory, Turku, Finland, July 3-5, 2002 Proceedings}
}
@article{journals/jacm/PettieR02,
title = {An optimal minimum spanning tree algorithm.},
year = {2002},
journal = {J. ACM},
author = {{Seth Pettie} and {Vijaya Ramachandran}}
}
@article{journals/siamcomp/PettieR02,
title = {A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest.},
year = {2002},
journal = {SIAM J. Comput.},
author = {{Seth Pettie} and {Vijaya Ramachandran}}
}
@article{journals/ipl/PettieS04,
title = {A simpler linear time 2/3-epsilon approximation for maximum weight matching.},
year = {2004},
journal = {Inf. Process. Lett.},
author = {{Seth Pettie} and {Peter Sanders 001}}
}
@article{journals/tcs/Pettie04,
title = {A new approach to all-pairs shortest paths on real-weighted graphs.},
year = {2004},
journal = {Theor. Comput. Sci.},
author = {{Seth Pettie}}
}
@inproceedings{conf/soda/BaswanaKMP05,
title = {New constructions of (alpha, beta)-spanners and purely additive spanners.},
year = {2005},
booktitle = {SODA},
author = {{Surender Baswana} and {Telikepalli Kavitha} and {Kurt Mehlhorn} and {Seth Pettie}},
publisher = {SIAM},
booktitle = {Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005}
}
@inproceedings{conf/wads/MortensenP05,
title = {The Complexity of Implicit and Space Efficient Priority Queues.},
year = {2005},
booktitle = {WADS},
author = {{Christian Worm Mortensen} and {Seth Pettie}},
publisher = {Springer},
booktitle = {Algorithms and Data Structures, 9th International Workshop, WADS 2005, Waterloo, Canada, August 15-17, 2005, Proceedings}
}
@article{journals/siamcomp/PettieR05,
title = {A Shortest Path Algorithm for Real-Weighted Undirected Graphs.},
year = {2005},
journal = {SIAM J. Comput.},
author = {{Seth Pettie} and {Vijaya Ramachandran}}
}
@inproceedings{conf/dagstuhl/Pettie06,
title = {Towards a Final Analysis of Pairing Heaps.},
year = {2006},
booktitle = {Data Structures},
author = {{Seth Pettie}},
publisher = {Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany},
booktitle = {Data Structures, 26.02. - 03.03.2006}
}
@article{journals/combinatorica/Pettie06,
title = {An Inverse-Ackermann Type Lower Bound For Online Minimum Spanning Tree Verification.},
year = {2006},
journal = {Comb.},
author = {{Seth Pettie}}
}
@inproceedings{conf/dagstuhl/Pettie08,
title = {Sources of Superlinearity in Davenport-Schinzel Sequences.},
year = {2008},
booktitle = {Data Structures},
author = {{Seth Pettie}},
publisher = {Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany},
booktitle = {Data Structures, 17.02. - 22.02.2008}
}
@inproceedings{conf/micro/GreathouseWRBABP08,
title = {Testudo: Heavyweight security analysis via statistical sampling.},
year = {2008},
booktitle = {MICRO},
author = {{Joseph L. Greathouse} and {Ilya Wagner} and {David A. Ramos} and {Gautam Bhatnagar} and {Todd M. Austin} and {Valeria Bertacco} and {Seth Pettie}},
publisher = {IEEE Computer Society},
booktitle = {41st Annual IEEE/ACM International Symposium on Microarchitecture (MICRO-41 2008), November 8-12, 2008, Lake Como, Italy}
}
@inproceedings{conf/soda/DuanP08,
title = {Bounded-leg distance and reachability oracles.},
year = {2008},
booktitle = {SODA},
author = {{Ran Duan} and {Seth Pettie}},
publisher = {SIAM},
booktitle = {Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008}
}
@inproceedings{conf/soda/Pettie08,
title = {Splay trees, Davenport-Schinzel sequences, and the deque conjecture.},
year = {2008},
booktitle = {SODA},
author = {{Seth Pettie}},
publisher = {SIAM},
booktitle = {Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008}
}
@article{journals/talg/PettieR08,
title = {Randomized minimum spanning tree algorithms using exponentially fewer random bits.},
year = {2008},
journal = {ACM Trans. Algorithms},
author = {{Seth Pettie} and {Vijaya Ramachandran}}
}
@incollection{reference/algo/Pettie08,
title = {All Pairs Shortest Paths in Sparse Graphs.},
year = {2008},
booktitle = {Encyclopedia of Algorithms},
author = {{Seth Pettie}},
publisher = {Springer},
booktitle = {Encyclopedia of Algorithms - 2008 Edition}
}
@incollection{reference/algo/Pettie08a,
title = {Minimum Spanning Trees.},
year = {2008},
booktitle = {Encyclopedia of Algorithms},
author = {{Seth Pettie}},
publisher = {Springer},
booktitle = {Encyclopedia of Algorithms - 2008 Edition}
}
@incollection{reference/algo/Pettie08b,
title = {Single-Source Shortest Paths.},
year = {2008},
booktitle = {Encyclopedia of Algorithms},
author = {{Seth Pettie}},
publisher = {Springer},
booktitle = {Encyclopedia of Algorithms - 2008 Edition}
}
@inproceedings{conf/soda/DuanP09,
title = {Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths.},
year = {2009},
booktitle = {SODA},
author = {{Ran Duan} and {Seth Pettie}},
publisher = {SIAM},
booktitle = {Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009}
}
@inproceedings{conf/soda/DuanP09a,
title = {Dual-failure distance and connectivity oracles.},
year = {2009},
booktitle = {SODA},
author = {{Ran Duan} and {Seth Pettie}},
publisher = {SIAM},
booktitle = {Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009}
}
@article{journals/talg/Pettie09,
title = {Low distortion spanners.},
year = {2009},
journal = {ACM Trans. Algorithms},
author = {{Seth Pettie}}
}
@inproceedings{conf/focs/DuanP10,
title = {Approximating Maximum Weight Matching in Near-Linear Time.},
year = {2010},
booktitle = {FOCS},
author = {{Ran Duan} and {Seth Pettie}},
publisher = {IEEE Computer Society},
booktitle = {51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA}
}
@inproceedings{conf/soda/Pettie10,
title = {On Nonlinear Forbidden 0-1 Matrices: A Refutation of a Füredi-Hajnal Conjecture.},
year = {2010},
booktitle = {SODA},
author = {{Seth Pettie}},
publisher = {SIAM},
booktitle = {Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010}
}
@inproceedings{conf/soda/Pettie10a,
title = {Applications of Forbidden 0-1 Matrices to Search Tree and Path Compression-Based Data Structures.},
year = {2010},
booktitle = {SODA},
author = {{Seth Pettie}},
publisher = {SIAM},
booktitle = {Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010}
}
@inproceedings{conf/stoc/DuanP10,
title = {Connectivity oracles for failure prone graphs.},
year = {2010},
booktitle = {STOC},
author = {{Ran Duan} and {Seth Pettie}},
publisher = {ACM},
booktitle = {Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010}
}
@article{journals/dc/Pettie10,
title = {Distributed algorithms for ultrasparse spanners and linear size skeletons.},
year = {2010},
journal = {Distributed Comput.},
author = {{Seth Pettie}}
}
@article{journals/talg/BaswanaKMP10,
title = {Additive spanners and (alpha, beta)-spanners.},
year = {2010},
journal = {ACM Trans. Algorithms},
author = {{Surender Baswana} and {Telikepalli Kavitha} and {Kurt Mehlhorn} and {Seth Pettie}}
}
@inproceedings{conf/compgeom/Pettie11,
title = {On the structure and composition of forbidden sequences, with geometric applications.},
year = {2011},
booktitle = {SCG},
author = {{Seth Pettie}},
publisher = {ACM},
booktitle = {Proceedings of the 27th ACM Symposium on Computational Geometry, Paris, France, June 13-15, 2011}
}
@article{journals/corr/abs-1112-0790,
title = {Scaling algorithms for approximate and exact maximum weight matching},
year = {2011},
journal = {CoRR},
author = {{Ran Duan} and {Seth Pettie} and {Hsin-Hao Su}}
}
@article{journals/dm/Pettie11,
title = {Degrees of nonlinearity in forbidden 0-1 matrix problems.},
year = {2011},
journal = {Discret. Math.},
author = {{Seth Pettie}}
}
@article{journals/jct/Pettie11,
title = {Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts.},
year = {2011},
journal = {J. Comb. Theory, Ser. A},
author = {{Seth Pettie}}
}
@article{journals/siamdm/Pettie11,
title = {Origins of Nonlinearity in Davenport-Schinzel Sequences.},
year = {2011},
journal = {SIAM J. Discret. Math.},
author = {{Seth Pettie}}
}
@inproceedings{conf/swat/BorradailePW12,
title = {Connectivity Oracles for Planar Graphs.},
year = {2012},
booktitle = {SWAT},
author = {{Glencora Borradaile} and {Seth Pettie} and {Christian Wulff-Nilsen}},
publisher = {Springer},
booktitle = {Algorithm Theory - SWAT 2012 - 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012. Proceedings}
}
@article{journals/corr/abs-1202-1983,
title = {Fast Distributed Algorithms for Maximal Matching and Maximal Independent Set},
year = {2012},
journal = {CoRR},
author = {{Leonid Barenboim} and {Michael Elkin} and {Seth Pettie} and {Johannes Schneider 002}}
}
@article{journals/corr/abs-1204-1086,
title = {Tightish Bounds on Davenport-Schinzel Sequences},
year = {2012},
journal = {CoRR},
author = {{Seth Pettie}}
}
@article{journals/ipl/Pettie12,
title = {A simple reduction from maximum weight matching to maximum cardinality matching.},
year = {2012},
journal = {Inf. Process. Lett.},
author = {{Seth Pettie}}
}
@article{journals/siamcomp/EtessamiMPWV12,
title = {Special Section on the Forty-Third Annual ACM Symposium on Theory of Computing (STOC 2011).},
year = {2012},
journal = {SIAM J. Comput.},
author = {{Kousha Etessami} and {Dieter van Melkebeek} and {Seth Pettie} and {John Watrous} and {Salil P. Vadhan}}
}
@inproceedings{conf/icalp/PettieS13,
title = {Fast Distributed Coloring Algorithms for Triangle-Free Graphs.},
year = {2013},
booktitle = {ICALP (2)},
author = {{Seth Pettie} and {Hsin-Hao Su}},
publisher = {Springer},
booktitle = {Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part II}
}
@inproceedings{conf/spaa/GilbertKPPSY14,
title = {(Near) optimal resource-competitive broadcast with jamming.},
year = {2014},
booktitle = {SPAA},
author = {{Seth Gilbert} and {Valerie King} and {Seth Pettie} and {Ely Porat} and {Jared Saia} and {Maxwell Young}},
publisher = {ACM},
booktitle = {26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '14, Prague, Czech Republic - June 23 - 25, 2014}
}
@article{journals/corr/Kejlberg-RasmussenKPP14,
title = {Word-packing Algorithms for Dynamic Connectivity and Dynamic Sets.},
year = {2014},
journal = {CoRR},
author = {{Casper Kejlberg-Rasmussen} and {Tsvi Kopelowitz} and {Seth Pettie} and {Ely Porat}}
}
@article{journals/corr/KopelowitzPP14,
title = {3SUM Hardness in (Dynamic) Data Structures.},
year = {2014},
journal = {CoRR},
author = {{Tsvi Kopelowitz} and {Seth Pettie} and {Ely Porat}}
}
@article{journals/jacm/DuanP14,
title = {Linear-Time Approximation for Maximum Weight Matching.},
year = {2014},
journal = {J. ACM},
author = {{Ran Duan} and {Seth Pettie}}
}
@inproceedings{conf/soda/ElkinPS15,
title = {(2Δ - l)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting.},
year = {2015},
booktitle = {SODA},
author = {{Michael Elkin} and {Seth Pettie} and {Hsin-Hao Su}},
publisher = {SIAM},
booktitle = {Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015}
}
@inproceedings{conf/soda/Pettie15,
title = {Sharp Bounds on Formation-free Sequences.},
year = {2015},
booktitle = {SODA},
author = {{Seth Pettie}},
publisher = {SIAM},
booktitle = {Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015}
}
@inproceedings{conf/wads/KopelowitzPP15,
title = {Dynamic Set Intersection.},
year = {2015},
booktitle = {WADS},
author = {{Tsvi Kopelowitz} and {Seth Pettie} and {Ely Porat}},
publisher = {Springer},
booktitle = {Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings}
}
@article{journals/corr/AmirKLPPS15,
title = {Online Dictionary Matching with One Gap.},
year = {2015},
journal = {CoRR},
author = {{Amihood Amir} and {Tsvi Kopelowitz} and {Avivit Levy} and {Seth Pettie} and {Ely Porat} and {B. Riva Shalom}}
}
@article{journals/corr/Kejlberg-Rasmussen15,
title = {Deterministic Worst Case Dynamic Connectivity: Simpler and Faster.},
year = {2015},
journal = {CoRR},
author = {{Casper Kejlberg-Rasmussen} and {Tsvi Kopelowitz} and {Seth Pettie} and {Mikkel Thorup}}
}
@article{journals/iandc/PettieS15,
title = {Distributed coloring algorithms for triangle-free graphs.},
year = {2015},
journal = {Inf. Comput.},
author = {{Seth Pettie} and {Hsin-Hao Su}}
}
@article{journals/jacm/LotkerPP15,
title = {Improved Distributed Approximate Matching.},
year = {2015},
journal = {J. ACM},
author = {{Zvi Lotker} and {Boaz Patt-Shamir} and {Seth Pettie}}
}
@article{journals/jacm/Pettie15,
title = {Sharp Bounds on Davenport-Schinzel Sequences of Every Order.},
year = {2015},
journal = {J. ACM},
author = {{Seth Pettie}}
}
@article{journals/jgaa/Pettie15,
title = {Sensitivity Analysis of Minimum Spanning Trees in Sub-Inverse-Ackermann Time.},
year = {2015},
journal = {J. Graph Algorithms Appl.},
author = {{Seth Pettie}}
}
@article{journals/siamdm/Pettie15,
title = {Three Generalizations of Davenport-Schinzel Sequences.},
year = {2015},
journal = {SIAM J. Discret. Math.},
author = {{Seth Pettie}}
}
@article{journals/sigact/BenderFMSDGPY15,
title = {Resource-Competitive Algorithms.},
year = {2015},
journal = {SIGACT News},
author = {{Michael A. Bender} and {Jeremy T. Fineman} and {Mahnush Movahedi} and {Jared Saia} and {Varsha Dani} and {Seth Gilbert} and {Seth Pettie} and {Maxwell Young}}
}
@inproceedings{conf/esa/Kejlberg-Rasmussen16,
title = {Faster Worst Case Deterministic Dynamic Connectivity.},
year = {2016},
booktitle = {ESA},
author = {{Casper Kejlberg-Rasmussen} and {Tsvi Kopelowitz} and {Seth Pettie} and {Mikkel Thorup}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark}
}
@inproceedings{conf/isaac/AmirKLPPS16,
title = {Mind the Gap: Essentially Optimal Algorithms for Online Dictionary Matching with One Gap.},
year = {2016},
booktitle = {ISAAC},
author = {{Amihood Amir} and {Tsvi Kopelowitz} and {Avivit Levy} and {Seth Pettie} and {Ely Porat} and {B. Riva Shalom}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {27th International Symposium on Algorithms and Computation, ISAAC 2016, December 12-14, 2016, Sydney, Australia}
}
@inproceedings{conf/podc/ChangKP16,
title = {Brief Announcement: An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model.},
year = {2016},
booktitle = {PODC},
author = {{Yi-Jun Chang} and {Tsvi Kopelowitz} and {Seth Pettie}},
publisher = {ACM},
booktitle = {Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, July 25-28, 2016}
}
@inproceedings{conf/soda/KopelowitzPP16,
title = {Higher Lower Bounds from the 3SUM Conjecture.},
year = {2016},
booktitle = {SODA},
author = {{Tsvi Kopelowitz} and {Seth Pettie} and {Ely Porat}},
publisher = {SIAM},
booktitle = {Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016}
}
@inproceedings{conf/stoc/BenderKPY16,
title = {Contention resolution with log-logstar channel accesses.},
year = {2016},
booktitle = {STOC},
author = {{Michael A. Bender} and {Tsvi Kopelowitz} and {Seth Pettie} and {Maxwell Young}},
publisher = {ACM},
booktitle = {Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016}
}
@article{journals/corr/ChangKPWZ16,
title = {How to Elect a Low-energy Leader.},
year = {2016},
journal = {CoRR},
author = {{Yi-Jun Chang} and {Tsvi Kopelowitz} and {Seth Pettie} and {Ruosong Wang} and {Wei Zhan}}
}
@article{journals/corr/HuangHKP16,
title = {Fully Dynamic Connectivity in O(log n(log log n)2) Amortized Expected Time.},
year = {2016},
journal = {CoRR},
author = {{Shang-En Huang} and {Dawei Huang} and {Tsvi Kopelowitz} and {Seth Pettie}}
}
@article{journals/dagstuhl-reports/LewensteinPW16,
title = {Structure and Hardness in P (Dagstuhl Seminar 16451).},
year = {2016},
journal = {Dagstuhl Reports},
author = {{Moshe Lewenstein} and {Seth Pettie} and {Virginia Vassilevska Williams}}
}
@article{journals/jacm/BarenboimEPS16,
title = {The Locality of Distributed Symmetry Breaking.},
year = {2016},
journal = {J. ACM},
author = {{Leonid Barenboim} and {Michael Elkin} and {Seth Pettie} and {Johannes Schneider 002}}
}
@article{journals/talg/ElkinP16,
title = {A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs.},
year = {2016},
journal = {ACM Trans. Algorithms},
author = {{Michael Elkin} and {Seth Pettie}}
}
@incollection{reference/algo/Pettie16,
title = {All Pairs Shortest Paths in Sparse Graphs.},
year = {2016},
booktitle = {Encyclopedia of Algorithms},
author = {{Seth Pettie}}
}
@incollection{reference/algo/Pettie16a,
title = {Minimum Spanning Trees.},
year = {2016},
booktitle = {Encyclopedia of Algorithms},
author = {{Seth Pettie}}
}
@incollection{reference/algo/Pettie16b,
title = {Single-Source Shortest Paths.},
year = {2016},
booktitle = {Encyclopedia of Algorithms},
author = {{Seth Pettie}}
}
@inproceedings{conf/innovations/BernsteinKPPS17,
title = {Simultaneously Load Balancing for Every p-norm, With Reassignments.},
year = {2017},
booktitle = {ITCS},
author = {{Aaron Bernstein} and {Tsvi Kopelowitz} and {Seth Pettie} and {Ely Porat} and {Clifford Stein 001}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA}
}
@inproceedings{conf/soda/HuangHKP17,
title = {Fully Dynamic Connectivity in O(log n(log log n)2) Amortized Expected Time.},
year = {2017},
booktitle = {SODA},
author = {{Shang-En Huang} and {Dawei Huang} and {Tsvi Kopelowitz} and {Seth Pettie}},
publisher = {SIAM},
booktitle = {Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19}
}
@article{journals/corr/HuangP17b,
title = {Approximate Generalized Matching: \$f\$-Factors and \$f\$-Edge Covers.},
year = {2017},
journal = {CoRR},
author = {{Dawei Huang} and {Seth Pettie}}
}
@article{journals/dc/ChungPS17,
title = {Distributed algorithms for the Lovász local lemma and graph coloring.},
year = {2017},
journal = {Distributed Comput.},
author = {{Kai-Min Chung} and {Seth Pettie} and {Hsin-Hao Su}}
}
@inproceedings{conf/esa/BrandtPU18,
title = {Fine-grained Lower Bounds on Cops and Robbers.},
year = {2018},
booktitle = {ESA},
author = {{Sebastian Brandt 002} and {Seth Pettie} and {Jara Uitto}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland}
}
@inproceedings{conf/esa/DorfmanK0PZ18,
title = {Improved Bounds for Multipass Pairing Heaps and Path-Balanced Binary Search Trees.},
year = {2018},
booktitle = {ESA},
author = {{Dani Dorfman} and {Haim Kaplan} and {László Kozma 002} and {Seth Pettie} and {Uri Zwick}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland}
}
@inproceedings{conf/podc/ChangDHHLP18,
title = {The Energy Complexity of Broadcast.},
year = {2018},
booktitle = {PODC},
author = {{Yi-Jun Chang} and {Varsha Dani} and {Thomas P. Hayes} and {Qizheng He} and {Wenzheng Li} and {Seth Pettie}},
publisher = {ACM},
booktitle = {Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27, 2018}
}
@inproceedings{conf/soda/ChangHLPU18,
title = {The Complexity of Distributed Edge Coloring with Small Palettes.},
year = {2018},
booktitle = {SODA},
author = {{Yi-Jun Chang} and {Qizheng He} and {Wenzheng Li} and {Seth Pettie} and {Jara Uitto}},
publisher = {SIAM},
booktitle = {Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018}
}
@inproceedings{conf/stoc/ChangLP18,
title = {An optimal distributed (Δ+1)-coloring algorithm?},
year = {2018},
booktitle = {STOC},
author = {{Yi-Jun Chang} and {Wenzheng Li} and {Seth Pettie}},
publisher = {ACM},
booktitle = {Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018}
}
@article{journals/dc/KingPSY18,
title = {A resource-competitive jamming defense.},
year = {2018},
journal = {Distributed Comput.},
author = {{Valerie King} and {Seth Pettie} and {Jared Saia} and {Maxwell Young}}
}
@article{journals/dm/WellmanP18,
title = {Lower bounds on Davenport-Schinzel sequences via rectangular Zarankiewicz matrices.},
year = {2018},
journal = {Discret. Math.},
author = {{Julian Wellman} and {Seth Pettie}}
}
@article{journals/jacm/GronlundP18,
title = {Threesomes, Degenerates, and Love Triangles.},
year = {2018},
journal = {J. ACM},
author = {{Allan Grønlund} and {Seth Pettie}}
}
@article{journals/siamcomp/AbboudBP18,
title = {A Hierarchy of Lower Bounds for Sublinear Additive Spanners.},
year = {2018},
journal = {SIAM J. Comput.},
author = {{Amir Abboud} and {Greg Bodwin} and {Seth Pettie}}
}
@article{journals/siamcomp/BenderKPY18,
title = {Contention Resolution with Constant Throughput and Log-Logstar Channel Accesses.},
year = {2018},
journal = {SIAM J. Comput.},
author = {{Michael A. Bender} and {Tsvi Kopelowitz} and {Seth Pettie} and {Maxwell Young}}
}
@article{journals/talg/DuanPS18,
title = {Scaling Algorithms for Weighted Matching in General Graphs.},
year = {2018},
journal = {ACM Trans. Algorithms},
author = {{Ran Duan} and {Seth Pettie} and {Hsin-Hao Su}}
}
@inproceedings{conf/soda/ChangJP19,
title = {Simple Contention Resolution via Multiplicative Weight Updates.},
year = {2019},
booktitle = {SOSA},
author = {{Yi-Jun Chang} and {Wenyu Jin 001} and {Seth Pettie}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {2nd Symposium on Simplicity in Algorithms, SOSA 2019, January 8-9, 2019, San Diego, CA, USA}
}
@inproceedings{conf/soda/ChangPZ19,
title = {Distributed Triangle Detection via Expander Decomposition.},
year = {2019},
booktitle = {SODA},
author = {{Yi-Jun Chang} and {Seth Pettie} and {Hengjie Zhang}},
publisher = {SIAM},
booktitle = {Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019}
}
@article{journals/algorithmica/AmirKLPPS19,
title = {Mind the Gap! - Online Dictionary Matching with One Gap.},
year = {2019},
journal = {Algorithmica},
author = {{Amihood Amir} and {Tsvi Kopelowitz} and {Avivit Levy} and {Seth Pettie} and {Ely Porat} and {B. Riva Shalom}}
}
@article{journals/corr/abs-1912-03443,
title = {Joins on Samples: A Theoretical Guide for Practitioners.},
year = {2019},
journal = {CoRR},
author = {{Dawei Huang} and {Dong Young Yoon} and {Seth Pettie} and {Barzan Mozafari}}
}
@article{journals/ipl/HuangP19,
title = {Thorup-Zwick emulators are universally optimal hopsets.},
year = {2019},
journal = {Inf. Process. Lett.},
author = {{Shang-En Huang} and {Seth Pettie}}
}
@article{journals/pvldb/HuangYPM19,
title = {Join on Samples: A Theoretical Guide for Practitioners.},
year = {2019},
journal = {Proc. VLDB Endow.},
author = {{Dawei Huang} and {Dong Young Yoon} and {Seth Pettie} and {Barzan Mozafari}}
}
@article{journals/siamcomp/ChangKP19,
title = {An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model.},
year = {2019},
journal = {SIAM J. Comput.},
author = {{Yi-Jun Chang} and {Tsvi Kopelowitz} and {Seth Pettie}}
}
@article{journals/siamcomp/ChangP19,
title = {A Time Hierarchy Theorem for the LOCAL Model.},
year = {2019},
journal = {SIAM J. Comput.},
author = {{Yi-Jun Chang} and {Seth Pettie}}
}
@article{journals/talg/ChangKPWZ19,
title = {Exponential Separations in the Energy Complexity of Leader Election.},
year = {2019},
journal = {ACM Trans. Algorithms},
author = {{Yi-Jun Chang} and {Tsvi Kopelowitz} and {Seth Pettie} and {Ruosong Wang} and {Wei Zhan}}
}
@inproceedings{conf/podc/ChangDHP20,
title = {The Energy Complexity of BFS in Radio Networks.},
year = {2020},
booktitle = {PODC},
author = {{Yi-Jun Chang} and {Varsha Dani} and {Thomas P. Hayes} and {Seth Pettie}},
publisher = {ACM},
booktitle = {PODC '20: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, August 3-7, 2020}
}
@inproceedings{conf/stoc/BenderKKP20,
title = {Contention resolution without collision detection.},
year = {2020},
booktitle = {STOC},
author = {{Michael A. Bender} and {Tsvi Kopelowitz} and {William Kuszmaul} and {Seth Pettie}},
publisher = {ACM},
booktitle = {Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020}
}
@article{journals/corr/abs-2008-08739,
title = {Simple and Efficient Cardinality Estimation in Data Streams.},
year = {2020},
journal = {CoRR},
author = {{Seth Pettie} and {Dingyu Wang} and {Longhui Yin}}
}
@article{journals/siamcomp/ChangLP20,
title = {Distributed (Δ+1)-Coloring via Ultrafast Graph Shattering.},
year = {2020},
journal = {SIAM J. Comput.},
author = {{Yi-Jun Chang} and {Wenzheng Li} and {Seth Pettie}}
}
@article{journals/siamcomp/DuanP20,
title = {Connectivity Oracles for Graphs Subject to Vertex Failures.},
year = {2020},
journal = {SIAM J. Comput.},
author = {{Ran Duan} and {Seth Pettie}}
}
@article{journals/talg/ChangHLPU20,
title = {Distributed Edge Coloring and a Special Case of the Constructive Lovász Local Lemma.},
year = {2020},
journal = {ACM Trans. Algorithms},
author = {{Yi-Jun Chang} and {Qizheng He} and {Wenzheng Li} and {Seth Pettie} and {Jara Uitto}}
}
@inproceedings{conf/esa/BernsteinDP21,
title = {Incremental SCC Maintenance in Sparse Graphs.},
year = {2021},
booktitle = {ESA},
author = {{Aaron Bernstein} and {Aditi Dudeja} and {Seth Pettie}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference).}
}
@inproceedings{conf/icalp/PettieWY21,
title = {Non-Mergeable Sketching for Cardinality Estimation.},
year = {2021},
booktitle = {ICALP},
author = {{Seth Pettie} and {Dingyu Wang} and {Longhui Yin}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference).}
}
@inproceedings{conf/icalp/PettieY21,
title = {The Structure of Minimum Vertex Cuts.},
year = {2021},
booktitle = {ICALP},
author = {{Seth Pettie} and {Longhui Yin}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference).}
}
@inproceedings{conf/podc/DaniGHP21,
title = {Brief Announcement: Wake Up and Join Me! An Energy Efficient Algorithm for Maximal Matching in Radio Networks.},
year = {2021},
booktitle = {PODC},
author = {{Varsha Dani} and {Aayush Gupta} and {Thomas P. Hayes} and {Seth Pettie}},
publisher = {ACM},
booktitle = {PODC '21: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, July 26-30, 2021}
}
@inproceedings{conf/soda/LongP21,
title = {Planar Distance Oracles with Better Time-Space Tradeoffs.},
year = {2021},
booktitle = {SODA},
author = {{Yaowei Long} and {Seth Pettie}},
publisher = {SIAM},
booktitle = {Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021}
}
@inproceedings{conf/stoc/PettieW21,
title = {Information theoretic limits of cardinality estimation: Fisher meets Shannon.},
year = {2021},
booktitle = {STOC},
author = {{Seth Pettie} and {Dingyu Wang}},
publisher = {ACM},
booktitle = {STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021.}
}
@article{journals/jacm/ChangPSZ21,
title = {Near-optimal Distributed Triangle Enumeration via Expander Decompositions.},
year = {2021},
journal = {J. ACM},
author = {{Yi-Jun Chang} and {Seth Pettie} and {Thatchaphol Saranurak} and {Hengjie Zhang}}
}
@article{journals/siamcomp/HuangPZZ21,
title = {The Communication Complexity of Set Intersection and Multiple Equality Testing.},
year = {2021},
journal = {SIAM J. Comput.},
author = {{Dawei Huang} and {Seth Pettie} and {Yixiang Zhang} and {Zhijun Zhang 007}}
}
@article{journals/siamdm/HuangP21,
title = {Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing Shortcuts.},
year = {2021},
journal = {SIAM J. Discret. Math.},
author = {{Shang-En Huang} and {Seth Pettie}}
}
@inproceedings{conf/stoc/HuangPZ22,
title = {Byzantine agreement in polynomial time with near-optimal resilience.},
year = {2022},
booktitle = {STOC},
author = {{Shang-En Huang} and {Seth Pettie} and {Leqi Zhu}},
publisher = {ACM},
booktitle = {STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022}
}
@inproceedings{conf/stoc/PettieSY22,
title = {Optimal vertex connectivity oracles.},
year = {2022},
booktitle = {STOC},
author = {{Seth Pettie} and {Thatchaphol Saranurak} and {Longhui Yin}},
publisher = {ACM},
booktitle = {STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022}
}
@article{journals/algorithmica/HuangP22,
title = {Approximate Generalized Matching: f-Matchings and f-Edge Covers.},
year = {2022},
journal = {Algorithmica},
author = {{Dawei Huang} and {Seth Pettie}}
}
@article{journals/corr/abs-2208-10578,
title = {Simpler and Better Cardinality Estimators for HyperLogLog and PCSA.},
year = {2022},
journal = {CoRR},
author = {{Seth Pettie} and {Dingyu Wang}}
}
@inproceedings{conf/pods/WangP23,
title = {Better Cardinality Estimators for HyperLogLog, PCSA, and Beyond.},
year = {2023},
booktitle = {PODS},
author = {{Dingyu Wang} and {Seth Pettie}},
publisher = {ACM},
booktitle = {Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2023, Seattle, WA, USA, June 18-23, 2023}
}
@inproceedings{conf/soda/HuangPZ23,
title = {Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection.},
year = {2023},
booktitle = {SODA},
author = {{Shang-En Huang} and {Seth Pettie} and {Leqi Zhu}},
publisher = {SIAM},
booktitle = {Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023}
}
@article{journals/corr/abs-2306-16365,
title = {On the Extremal Functions of Acyclic Forbidden 0-1 Matrices.},
year = {2023},
journal = {CoRR},
author = {{Seth Pettie} and {Gábor Tardos}}
}
@article{journals/corr/abs-2307-02294,
title = {Sorting Pattern-Avoiding Permutations via 0-1 Matrices Forbidding Product Patterns.},
year = {2023},
journal = {CoRR},
author = {{Parinya Chalermsook} and {Seth Pettie} and {Sorrachai Yingchareonthawornchai}}
}
@article{journals/corr/abs-2307-06276,
title = {Connectivity Labeling for Multiple Vertex Failures.},
year = {2023},
journal = {CoRR},
author = {{Merav Parter} and {Asaf Petruschka} and {Seth Pettie}}
}
@article{journals/theoretics/HuangHKPT23,
title = {Fully Dynamic Connectivity in O(log n(loglog n)2) Amortized Expected Time.},
year = {2023},
journal = {TheoretiCS},
author = {{Shang-En Huang} and {Dawei Huang} and {Tsvi Kopelowitz} and {Seth Pettie} and {Mikkel Thorup}}
}
@article{journals/jacm/CharalampopoulosGLMPWW23,
title = {Almost Optimal Exact Distance Oracles for Planar Graphs.},
year = {2023},
month = {April},
journal = {J. ACM},
author = {{Panagiotis Charalampopoulos} and {Pawel Gawrychowski} and {Yaowei Long} and {Shay Mozes} and {Seth Pettie} and {Oren Weimann} and {Christian Wulff-Nilsen}}
}
@article{journals/dc/DaniGHP23,
title = {Wake up and join me! An energy-efficient algorithm for maximal matching in radio networks.},
year = {2023},
month = {September},
journal = {Distributed Comput.},
author = {{Varsha Dani} and {Aayush Gupta} and {Thomas P. Hayes} and {Seth Pettie}}
}
@inproceedings{conf/innovations/DaniHPS24,
title = {Fraud Detection for Random Walks.},
year = {2024},
booktitle = {ITCS},
author = {{Varsha Dani} and {Thomas P. Hayes} and {Seth Pettie} and {Jared Saia}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {15th Innovations in Theoretical Computer Science Conference, ITCS 2024, January 30 to February 2, 2024, Berkeley, CA, USA}
}