Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Ittai Rubinstein. Average-Case to (Shifted) Worst-Case Reduction for the Trace Reconstruction Problem. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 102:1-102:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{rubinstein:LIPIcs.ICALP.2023.102, author = {Rubinstein, Ittai}, title = {{Average-Case to (Shifted) Worst-Case Reduction for the Trace Reconstruction Problem}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {102:1--102:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.102}, URN = {urn:nbn:de:0030-drops-181542}, doi = {10.4230/LIPIcs.ICALP.2023.102}, annote = {Keywords: Trace Reconstruction, Synchronization Channels, Computational Learning Theory, Computational Biology} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Dan Alistarh, Giorgi Nadiradze, and Amirmojtaba Sabour. Dynamic Averaging Load Balancing on Cycles. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{alistarh_et_al:LIPIcs.ICALP.2020.7, author = {Alistarh, Dan and Nadiradze, Giorgi and Sabour, Amirmojtaba}, title = {{Dynamic Averaging Load Balancing on Cycles}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {7:1--7:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.7}, URN = {urn:nbn:de:0030-drops-124142}, doi = {10.4230/LIPIcs.ICALP.2020.7}, annote = {Keywords: Algorithms, Load Balancing} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Frank Ban, Xi Chen, Rocco A. Servedio, and Sandip Sinha. Efficient Average-Case Population Recovery in the Presence of Insertions and Deletions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 44:1-44:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{ban_et_al:LIPIcs.APPROX-RANDOM.2019.44, author = {Ban, Frank and Chen, Xi and Servedio, Rocco A. and Sinha, Sandip}, title = {{Efficient Average-Case Population Recovery in the Presence of Insertions and Deletions}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {44:1--44:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.44}, URN = {urn:nbn:de:0030-drops-112592}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.44}, annote = {Keywords: population recovery, deletion channel, trace reconstruction} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Yuval Peres, Mohit Singh, and Nisheeth K. Vishnoi. Random Walks in Polytopes and Negative Dependence. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 50:1-50:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{peres_et_al:LIPIcs.ITCS.2017.50, author = {Peres, Yuval and Singh, Mohit and Vishnoi, Nisheeth K.}, title = {{Random Walks in Polytopes and Negative Dependence}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {50:1--50:10}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.50}, URN = {urn:nbn:de:0030-drops-81464}, doi = {10.4230/LIPIcs.ITCS.2017.50}, annote = {Keywords: Random walks, Matroid, Polytope, Brownian motion, Negative dependence} }
Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Omer Angel, Abbas Mehrabian, and Yuval Peres. The String of Diamonds Is Tight for Rumor Spreading. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 26:1-26:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{angel_et_al:LIPIcs.APPROX-RANDOM.2017.26, author = {Angel, Omer and Mehrabian, Abbas and Peres, Yuval}, title = {{The String of Diamonds Is Tight for Rumor Spreading}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)}, pages = {26:1--26:9}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-044-6}, ISSN = {1868-8969}, year = {2017}, volume = {81}, editor = {Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.26}, URN = {urn:nbn:de:0030-drops-75754}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.26}, annote = {Keywords: randomized rumor spreading, push\&pull protocol, asynchronous time model, string of diamonds} }
Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Anna Ben-Hamou and Yuval Peres. Cutoff for a Stratified Random Walk on the Hypercube. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 29:1-29:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{benhamou_et_al:LIPIcs.APPROX-RANDOM.2017.29, author = {Ben-Hamou, Anna and Peres, Yuval}, title = {{Cutoff for a Stratified Random Walk on the Hypercube}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)}, pages = {29:1--29:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-044-6}, ISSN = {1868-8969}, year = {2017}, volume = {81}, editor = {Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.29}, URN = {urn:nbn:de:0030-drops-75787}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.29}, annote = {Keywords: Mixing times, cutoff, hypercube} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Nick Gravin, Yuval Peres, and Balasubramanian Sivan. Tight Lower Bounds for Multiplicative Weights Algorithmic Families. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 48:1-48:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{gravin_et_al:LIPIcs.ICALP.2017.48, author = {Gravin, Nick and Peres, Yuval and Sivan, Balasubramanian}, title = {{Tight Lower Bounds for Multiplicative Weights Algorithmic Families}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {48:1--48:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.48}, URN = {urn:nbn:de:0030-drops-74997}, doi = {10.4230/LIPIcs.ICALP.2017.48}, annote = {Keywords: Multiplicative Weights, Lower Bounds, Adversarial Primitives} }
Feedback for Dagstuhl Publishing