Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Varsha Dani, Thomas P. Hayes, Seth Pettie, and Jared Saia. Fraud Detection for Random Walks. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 36:1-36:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dani_et_al:LIPIcs.ITCS.2024.36, author = {Dani, Varsha and Hayes, Thomas P. and Pettie, Seth and Saia, Jared}, title = {{Fraud Detection for Random Walks}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {36:1--36:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.36}, URN = {urn:nbn:de:0030-drops-195645}, doi = {10.4230/LIPIcs.ITCS.2024.36}, annote = {Keywords: Fraud detection, random processes, Markov chains} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Aleksander Łukasiewicz and Przemysław Uznański. Cardinality Estimation Using Gumbel Distribution. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 76:1-76:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{lukasiewicz_et_al:LIPIcs.ESA.2022.76, author = {{\L}ukasiewicz, Aleksander and Uzna\'{n}ski, Przemys{\l}aw}, title = {{Cardinality Estimation Using Gumbel Distribution}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {76:1--76:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.76}, URN = {urn:nbn:de:0030-drops-170140}, doi = {10.4230/LIPIcs.ESA.2022.76}, annote = {Keywords: Streaming algorithms, Cardinality estimation, Sketching, Gumbel distribution} }
Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)
Varsha Dani, Aayush Gupta, Thomas P. Hayes, and Seth Pettie. Wake up and Join Me! an Energy-Efficient Algorithm for Maximal Matching in Radio Networks. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{dani_et_al:LIPIcs.DISC.2021.19, author = {Dani, Varsha and Gupta, Aayush and Hayes, Thomas P. and Pettie, Seth}, title = {{Wake up and Join Me! an Energy-Efficient Algorithm for Maximal Matching in Radio Networks}}, booktitle = {35th International Symposium on Distributed Computing (DISC 2021)}, pages = {19:1--19:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-210-5}, ISSN = {1868-8969}, year = {2021}, volume = {209}, editor = {Gilbert, Seth}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.19}, URN = {urn:nbn:de:0030-drops-148219}, doi = {10.4230/LIPIcs.DISC.2021.19}, annote = {Keywords: Distributed Algorithms, Energy-Aware Computation, Radio Networks, Maximal Matching, Sensor Networks} }
Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)
Sebastian Brandt, Rustam Latypov, and Jara Uitto. Brief Announcement: Memory Efficient Massively Parallel Algorithms for LCL Problems on Trees. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 50:1-50:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{brandt_et_al:LIPIcs.DISC.2021.50, author = {Brandt, Sebastian and Latypov, Rustam and Uitto, Jara}, title = {{Brief Announcement: Memory Efficient Massively Parallel Algorithms for LCL Problems on Trees}}, booktitle = {35th International Symposium on Distributed Computing (DISC 2021)}, pages = {50:1--50:4}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-210-5}, ISSN = {1868-8969}, year = {2021}, volume = {209}, editor = {Gilbert, Seth}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.50}, URN = {urn:nbn:de:0030-drops-148521}, doi = {10.4230/LIPIcs.DISC.2021.50}, annote = {Keywords: Distributed computing, Locally checkable labeling problems, Trees, Massively Parallel Computation, Sublinear memory, 3-coloring} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Aaron Bernstein, Aditi Dudeja, and Seth Pettie. Incremental SCC Maintenance in Sparse Graphs. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bernstein_et_al:LIPIcs.ESA.2021.14, author = {Bernstein, Aaron and Dudeja, Aditi and Pettie, Seth}, title = {{Incremental SCC Maintenance in Sparse Graphs}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {14:1--14:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.14}, URN = {urn:nbn:de:0030-drops-145950}, doi = {10.4230/LIPIcs.ESA.2021.14}, annote = {Keywords: Directed Graphs, Strongly Connected Components, Dynamic Graph Algorithms} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Seth Pettie, Dingyu Wang, and Longhui Yin. Non-Mergeable Sketching for Cardinality Estimation. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 104:1-104:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{pettie_et_al:LIPIcs.ICALP.2021.104, author = {Pettie, Seth and Wang, Dingyu and Yin, Longhui}, title = {{Non-Mergeable Sketching for Cardinality Estimation}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {104:1--104:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.104}, URN = {urn:nbn:de:0030-drops-141731}, doi = {10.4230/LIPIcs.ICALP.2021.104}, annote = {Keywords: Cardinality Estimation, Sketching} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Seth Pettie and Longhui Yin. The Structure of Minimum Vertex Cuts. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 105:1-105:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{pettie_et_al:LIPIcs.ICALP.2021.105, author = {Pettie, Seth and Yin, Longhui}, title = {{The Structure of Minimum Vertex Cuts}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {105:1--105:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.105}, URN = {urn:nbn:de:0030-drops-141746}, doi = {10.4230/LIPIcs.ICALP.2021.105}, annote = {Keywords: Graph theory, vertex connectivity, data structures} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Martin Dietzfelbinger and Stefan Walzer. Efficient Gauss Elimination for Near-Quadratic Matrices with One Short Random Block per Row, with Applications. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 39:1-39:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{dietzfelbinger_et_al:LIPIcs.ESA.2019.39, author = {Dietzfelbinger, Martin and Walzer, Stefan}, title = {{Efficient Gauss Elimination for Near-Quadratic Matrices with One Short Random Block per Row, with Applications}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {39:1--39:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.39}, URN = {urn:nbn:de:0030-drops-111602}, doi = {10.4230/LIPIcs.ESA.2019.39}, annote = {Keywords: Random Band Matrix, Gauss Elimination, Retrieval, Hashing, Succinct Data Structure, Randomised Data Structure, Robin Hood Hashing, Bloom Filter} }
Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)
Yi-Jun Chang, Wenyu Jin, and Seth Pettie. Simple Contention Resolution via Multiplicative Weight Updates. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chang_et_al:OASIcs.SOSA.2019.16, author = {Chang, Yi-Jun and Jin, Wenyu and Pettie, Seth}, title = {{Simple Contention Resolution via Multiplicative Weight Updates}}, booktitle = {2nd Symposium on Simplicity in Algorithms (SOSA 2019)}, pages = {16:1--16:16}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-099-6}, ISSN = {2190-6807}, year = {2019}, volume = {69}, editor = {Fineman, Jeremy T. and Mitzenmacher, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.16}, URN = {urn:nbn:de:0030-drops-100426}, doi = {10.4230/OASIcs.SOSA.2019.16}, annote = {Keywords: Contention resolution, multiplicative weight update method} }
Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)
Merav Parter and Hsin-Hao Su. Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 39:1-39:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{parter_et_al:LIPIcs.DISC.2018.39, author = {Parter, Merav and Su, Hsin-Hao}, title = {{Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds}}, booktitle = {32nd International Symposium on Distributed Computing (DISC 2018)}, pages = {39:1--39:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-092-7}, ISSN = {1868-8969}, year = {2018}, volume = {121}, editor = {Schmid, Ulrich and Widder, Josef}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.39}, URN = {urn:nbn:de:0030-drops-98286}, doi = {10.4230/LIPIcs.DISC.2018.39}, annote = {Keywords: Distributed Graph Algorithms, Coloring, congested clique} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Sebastian Brandt, Seth Pettie, and Jara Uitto. Fine-grained Lower Bounds on Cops and Robbers. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{brandt_et_al:LIPIcs.ESA.2018.9, author = {Brandt, Sebastian and Pettie, Seth and Uitto, Jara}, title = {{Fine-grained Lower Bounds on Cops and Robbers}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {9:1--9:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-081-1}, ISSN = {1868-8969}, year = {2018}, volume = {112}, editor = {Azar, Yossi and Bast, Hannah and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.9}, URN = {urn:nbn:de:0030-drops-94725}, doi = {10.4230/LIPIcs.ESA.2018.9}, annote = {Keywords: Cops and Robbers} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Dani Dorfman, Haim Kaplan, László Kozma, Seth Pettie, and Uri Zwick. Improved Bounds for Multipass Pairing Heaps and Path-Balanced Binary Search Trees. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{dorfman_et_al:LIPIcs.ESA.2018.24, author = {Dorfman, Dani and Kaplan, Haim and Kozma, L\'{a}szl\'{o} and Pettie, Seth and Zwick, Uri}, title = {{Improved Bounds for Multipass Pairing Heaps and Path-Balanced Binary Search Trees}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {24:1--24:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-081-1}, ISSN = {1868-8969}, year = {2018}, volume = {112}, editor = {Azar, Yossi and Bast, Hannah and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.24}, URN = {urn:nbn:de:0030-drops-94879}, doi = {10.4230/LIPIcs.ESA.2018.24}, annote = {Keywords: data structure, priority queue, pairing heap, binary search tree} }
Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Shang-En Huang and Seth Pettie. Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing shortcuts. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 26:1-26:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{huang_et_al:LIPIcs.SWAT.2018.26, author = {Huang, Shang-En and Pettie, Seth}, title = {{Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing shortcuts}}, booktitle = {16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)}, pages = {26:1--26:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-068-2}, ISSN = {1868-8969}, year = {2018}, volume = {101}, editor = {Eppstein, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.26}, URN = {urn:nbn:de:0030-drops-88521}, doi = {10.4230/LIPIcs.SWAT.2018.26}, annote = {Keywords: additive spanners, emulators, shortcutting directed graphs} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Aaron Bernstein, Tsvi Kopelowitz, Seth Pettie, Ely Porat, and Clifford Stein. Simultaneously Load Balancing for Every p-norm, With Reassignments. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{bernstein_et_al:LIPIcs.ITCS.2017.51, author = {Bernstein, Aaron and Kopelowitz, Tsvi and Pettie, Seth and Porat, Ely and Stein, Clifford}, title = {{Simultaneously Load Balancing for Every p-norm, With Reassignments}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {51:1--51:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-029-3}, ISSN = {1868-8969}, year = {2017}, volume = {67}, editor = {Papadimitriou, Christos H.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.51}, URN = {urn:nbn:de:0030-drops-82009}, doi = {10.4230/LIPIcs.ITCS.2017.51}, annote = {Keywords: Online Matching, Graph Orientation, Minmizing the p-norm} }
Published in: Dagstuhl Reports, Volume 6, Issue 11 (2017)
Moshe Lewenstein, Seth Pettie, and Virginia Vassilevska Williams. Structure and Hardness in P (Dagstuhl Seminar 16451). In Dagstuhl Reports, Volume 6, Issue 11, pp. 1-34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@Article{lewenstein_et_al:DagRep.6.11.1, author = {Lewenstein, Moshe and Pettie, Seth and Vassilevska Williams, Virginia}, title = {{Structure and Hardness in P (Dagstuhl Seminar 16451)}}, pages = {1--34}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2017}, volume = {6}, number = {11}, editor = {Lewenstein, Moshe and Pettie, Seth and Vassilevska Williams, Virginia}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.6.11.1}, URN = {urn:nbn:de:0030-drops-70373}, doi = {10.4230/DagRep.6.11.1}, annote = {Keywords: Algorithmic equivalences, Classifying P, Hardness assumptions, Lower bounds} }
Feedback for Dagstuhl Publishing