Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Shuchi Chawla, Evangelia Gergatsouli, Jeremy McMahan, and Christos Tzamos. Approximating Pandora’s Box with Correlations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 26:1-26:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{chawla_et_al:LIPIcs.APPROX/RANDOM.2023.26, author = {Chawla, Shuchi and Gergatsouli, Evangelia and McMahan, Jeremy and Tzamos, Christos}, title = {{Approximating Pandora’s Box with Correlations}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {26:1--26:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, 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.2023.26}, URN = {urn:nbn:de:0030-drops-188519}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.26}, annote = {Keywords: Pandora’s Box, Min Sum Set Cover, stochastic optimization, approximation preserving reduction} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Amir Abboud, Mina Dalirrooyfard, Ray Li, and Virginia Vassilevska Williams. On Diameter Approximation in Directed Graphs. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 2:1-2:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{abboud_et_al:LIPIcs.ESA.2023.2, author = {Abboud, Amir and Dalirrooyfard, Mina and Li, Ray and Vassilevska Williams, Virginia}, title = {{On Diameter Approximation in Directed Graphs}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {2:1--2:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.2}, URN = {urn:nbn:de:0030-drops-186552}, doi = {10.4230/LIPIcs.ESA.2023.2}, annote = {Keywords: Diameter, Directed Graphs, Approximation Algorithms, Fine-grained complexity} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Venkatesan Guruswami, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, and Mary Wootters. Sharp Threshold Rates for Random Codes. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{guruswami_et_al:LIPIcs.ITCS.2021.5, author = {Guruswami, Venkatesan and Mosheiff, Jonathan and Resch, Nicolas and Silas, Shashwat and Wootters, Mary}, title = {{Sharp Threshold Rates for Random Codes}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {5:1--5:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.5}, URN = {urn:nbn:de:0030-drops-135446}, doi = {10.4230/LIPIcs.ITCS.2021.5}, annote = {Keywords: Coding theory, Random codes, Sharp thresholds} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Joshua Lau and Angus Ritossa. Algorithms and Hardness for Multidimensional Range Updates and Queries. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{lau_et_al:LIPIcs.ITCS.2021.35, author = {Lau, Joshua and Ritossa, Angus}, title = {{Algorithms and Hardness for Multidimensional Range Updates and Queries}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {35:1--35:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.35}, URN = {urn:nbn:de:0030-drops-135742}, doi = {10.4230/LIPIcs.ITCS.2021.35}, annote = {Keywords: Orthogonal range, Range updates, Online and Dynamic Data Structures, Fine-grained complexity, Cycle counting} }
Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Mary Wootters. List-Decodability of Structured Ensembles of Codes (Invited Talk). In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 3:1-3:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{wootters:LIPIcs.MFCS.2020.3, author = {Wootters, Mary}, title = {{List-Decodability of Structured Ensembles of Codes}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {3:1--3:5}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-159-7}, ISSN = {1868-8969}, year = {2020}, volume = {170}, editor = {Esparza, Javier and Kr\'{a}l', Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.3}, URN = {urn:nbn:de:0030-drops-126742}, doi = {10.4230/LIPIcs.MFCS.2020.3}, annote = {Keywords: Error Correcting Codes, List-Decoding} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Venkatesan Guruswami, Ray Li, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, and Mary Wootters. Bounds for List-Decoding and List-Recovery of Random Linear Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{guruswami_et_al:LIPIcs.APPROX/RANDOM.2020.9, author = {Guruswami, Venkatesan and Li, Ray and Mosheiff, Jonathan and Resch, Nicolas and Silas, Shashwat and Wootters, Mary}, title = {{Bounds for List-Decoding and List-Recovery of Random Linear Codes}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {9:1--9:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-164-1}, ISSN = {1868-8969}, year = {2020}, volume = {176}, editor = {Byrka, Jaros{\l}aw and Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.9}, URN = {urn:nbn:de:0030-drops-126126}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.9}, annote = {Keywords: list-decoding, list-recovery, random linear codes, coding theory} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Serge Gaspers and Joshua Lau. Minimizing and Computing the Inverse Geodesic Length on Trees. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 59:1-59:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{gaspers_et_al:LIPIcs.ISAAC.2019.59, author = {Gaspers, Serge and Lau, Joshua}, title = {{Minimizing and Computing the Inverse Geodesic Length on Trees}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {59:1--59:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.59}, URN = {urn:nbn:de:0030-drops-115555}, doi = {10.4230/LIPIcs.ISAAC.2019.59}, annote = {Keywords: Trees, Treewidth, Fixed-Parameter Tractability, Inverse Geodesic Length, Vertex deletion, Polynomial multiplication, Distance distribution} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Ray Li and Mary Wootters. Lifted Multiplicity Codes and the Disjoint Repair Group Property. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 38:1-38:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{li_et_al:LIPIcs.APPROX-RANDOM.2019.38, author = {Li, Ray and Wootters, Mary}, title = {{Lifted Multiplicity Codes and the Disjoint Repair Group Property}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {38:1--38: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.38}, URN = {urn:nbn:de:0030-drops-112539}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.38}, annote = {Keywords: Lifted codes, Multiplicity codes, Disjoint repair group property, PIR code, Coding theory} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Serge Gaspers and Ray Li. Enumeration of Preferred Extensions in Almost Oriented Digraphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 74:1-74:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{gaspers_et_al:LIPIcs.MFCS.2019.74, author = {Gaspers, Serge and Li, Ray}, title = {{Enumeration of Preferred Extensions in Almost Oriented Digraphs}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {74:1--74:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.74}, URN = {urn:nbn:de:0030-drops-110188}, doi = {10.4230/LIPIcs.MFCS.2019.74}, annote = {Keywords: abstract argumentation, exact algorithms, exponential time algorithms, parameterized algorithms, enumeration algorithms, semikernels in digraphs} }
Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Ray Li and Mary Wootters. Improved List-Decodability of Random Linear Binary Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 50:1-50:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{li_et_al:LIPIcs.APPROX-RANDOM.2018.50, author = {Li, Ray and Wootters, Mary}, title = {{Improved List-Decodability of Random Linear Binary Codes}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)}, pages = {50:1--50:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-085-9}, ISSN = {1868-8969}, year = {2018}, volume = {116}, editor = {Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David}, 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.2018.50}, URN = {urn:nbn:de:0030-drops-94547}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.50}, annote = {Keywords: List-decoding, Random linear codes, Rank-metric codes} }
Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Venkatesan Guruswami and Ray Li. Efficiently Decodable Codes for the Binary Deletion Channel. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 47:1-47:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{guruswami_et_al:LIPIcs.APPROX-RANDOM.2017.47, author = {Guruswami, Venkatesan and Li, Ray}, title = {{Efficiently Decodable Codes for the Binary Deletion Channel}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)}, pages = {47:1--47:13}, 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.47}, URN = {urn:nbn:de:0030-drops-75964}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.47}, annote = {Keywords: Coding theory, Combinatorics, Synchronization errors, Channel capacity} }
Feedback for Dagstuhl Publishing