LIPIcs, Volume 207
APPROX/RANDOM 2021, August 16-18, 2021, University of Washington, Seattle, Washington, US (Virtual Conference)
Editors: Mary Wootters and Laura Sanità
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Keller Blackwell and Mary Wootters. A Characterization of Optimal-Rate Linear Homomorphic Secret Sharing Schemes, and Applications. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 16:1-16:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{blackwell_et_al:LIPIcs.ITCS.2024.16, author = {Blackwell, Keller and Wootters, Mary}, title = {{A Characterization of Optimal-Rate Linear Homomorphic Secret Sharing Schemes, and Applications}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {16:1--16:20}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.16}, URN = {urn:nbn:de:0030-drops-195447}, doi = {10.4230/LIPIcs.ITCS.2024.16}, annote = {Keywords: Error Correcting Codes, Homomorphic Secret Sharing} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Guy Blanc and Dean Doron. New Near-Linear Time Decodable Codes Closer to the GV Bound. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 10:1-10:40, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{blanc_et_al:LIPIcs.CCC.2022.10, author = {Blanc, Guy and Doron, Dean}, title = {{New Near-Linear Time Decodable Codes Closer to the GV Bound}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {10:1--10:40}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.10}, URN = {urn:nbn:de:0030-drops-165726}, doi = {10.4230/LIPIcs.CCC.2022.10}, annote = {Keywords: Unique decoding, list decoding, the Gilbert-Varshamov bound, small-bias sample spaces, hypergraphs, expander walks} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Dean Doron and Mary Wootters. High-Probability List-Recovery, and Applications to Heavy Hitters. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 55:1-55:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{doron_et_al:LIPIcs.ICALP.2022.55, author = {Doron, Dean and Wootters, Mary}, title = {{High-Probability List-Recovery, and Applications to Heavy Hitters}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {55:1--55:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.55}, URN = {urn:nbn:de:0030-drops-163961}, doi = {10.4230/LIPIcs.ICALP.2022.55}, annote = {Keywords: List recoverable codes, Heavy Hitters, high-dimensional expanders} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Ingerid Fosli, Yuval Ishai, Victor I. Kolobov, and Mary Wootters. On the Download Rate of Homomorphic Secret Sharing. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 71:1-71:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{fosli_et_al:LIPIcs.ITCS.2022.71, author = {Fosli, Ingerid and Ishai, Yuval and Kolobov, Victor I. and Wootters, Mary}, title = {{On the Download Rate of Homomorphic Secret Sharing}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {71:1--71:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.71}, URN = {urn:nbn:de:0030-drops-156675}, doi = {10.4230/LIPIcs.ITCS.2022.71}, annote = {Keywords: Information-theoretic cryptography, homomorphic secret sharing, private information retrieval, secure multiparty computation, regenerating codes} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Noah Shutty and Mary Wootters. Low-Bandwidth Recovery of Linear Functions of Reed-Solomon-Encoded Data. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 117:1-117:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{shutty_et_al:LIPIcs.ITCS.2022.117, author = {Shutty, Noah and Wootters, Mary}, title = {{Low-Bandwidth Recovery of Linear Functions of Reed-Solomon-Encoded Data}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {117:1--117:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.117}, URN = {urn:nbn:de:0030-drops-157130}, doi = {10.4230/LIPIcs.ITCS.2022.117}, annote = {Keywords: Reed-Solomon Codes, Regenerating Codes, Coded Computation} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 1-1240, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@Proceedings{wootters_et_al:LIPIcs.APPROX/RANDOM.2021, title = {{LIPIcs, Volume 207, APPROX/RANDOM 2021, Complete Volume}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {1--1240}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, 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.2021}, URN = {urn:nbn:de:0030-drops-146929}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021}, annote = {Keywords: LIPIcs, Volume 207, APPROX/RANDOM 2021, Complete Volume} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 0:i-0:x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{wootters_et_al:LIPIcs.APPROX/RANDOM.2021.0, author = {Wootters, Mary and Sanit\`{a}, Laura}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {0:i--0:x}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, 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.2021.0}, URN = {urn:nbn:de:0030-drops-146933}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Umang Bhaskar, A. R. Sricharan, and Rohit Vaish. On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 1:1-1:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bhaskar_et_al:LIPIcs.APPROX/RANDOM.2021.1, author = {Bhaskar, Umang and Sricharan, A. R. and Vaish, Rohit}, title = {{On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {1:1--1:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, 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.2021.1}, URN = {urn:nbn:de:0030-drops-146944}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.1}, annote = {Keywords: Fair Division, Indivisible Chores, Approximate Envy-Freeness} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Susanne Albers and Sebastian Schubert. Optimal Algorithms for Online b-Matching with Variable Vertex Capacities. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 2:1-2:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{albers_et_al:LIPIcs.APPROX/RANDOM.2021.2, author = {Albers, Susanne and Schubert, Sebastian}, title = {{Optimal Algorithms for Online b-Matching with Variable Vertex Capacities}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {2:1--2:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, 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.2021.2}, URN = {urn:nbn:de:0030-drops-146957}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.2}, annote = {Keywords: Online algorithms, primal-dual analysis, configuration LP, b-matching, variable vertex capacities, unweighted matching, vertex-weighted matching} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Anupam Gupta, Amit Kumar, and Sahil Singla. Bag-Of-Tasks Scheduling on Related Machines. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{gupta_et_al:LIPIcs.APPROX/RANDOM.2021.3, author = {Gupta, Anupam and Kumar, Amit and Singla, Sahil}, title = {{Bag-Of-Tasks Scheduling on Related Machines}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {3:1--3:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, 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.2021.3}, URN = {urn:nbn:de:0030-drops-146967}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.3}, annote = {Keywords: approximation algorithms, scheduling, bag-of-tasks, related machines} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Anup Bhattacharya, Dishant Goyal, and Ragesh Jaiswal. Hardness of Approximation for Euclidean k-Median. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 4:1-4:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bhattacharya_et_al:LIPIcs.APPROX/RANDOM.2021.4, author = {Bhattacharya, Anup and Goyal, Dishant and Jaiswal, Ragesh}, title = {{Hardness of Approximation for Euclidean k-Median}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {4:1--4:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, 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.2021.4}, URN = {urn:nbn:de:0030-drops-146979}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.4}, annote = {Keywords: Hardness of approximation, bicriteria approximation, approximation algorithms, k-median, k-means} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Elena Grigorescu, Young-San Lin, and Kent Quanrud. Online Directed Spanners and Steiner Forests. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 5:1-5:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{grigorescu_et_al:LIPIcs.APPROX/RANDOM.2021.5, author = {Grigorescu, Elena and Lin, Young-San and Quanrud, Kent}, title = {{Online Directed Spanners and Steiner Forests}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {5:1--5:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, 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.2021.5}, URN = {urn:nbn:de:0030-drops-146987}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.5}, annote = {Keywords: online directed pairwise spanners, online directed Steiner forests, online covering/packing linear programming, primal-dual approach} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, and Manaswi Paraashar. Query Complexity of Global Minimum Cut. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bishnu_et_al:LIPIcs.APPROX/RANDOM.2021.6, author = {Bishnu, Arijit and Ghosh, Arijit and Mishra, Gopinath and Paraashar, Manaswi}, title = {{Query Complexity of Global Minimum Cut}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {6:1--6:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, 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.2021.6}, URN = {urn:nbn:de:0030-drops-146992}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.6}, annote = {Keywords: Query complexity, Global mincut} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Eun Jung Kim, Euiwoong Lee, and Dimitrios M. Thilikos. A Constant-Factor Approximation for Weighted Bond Cover. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{kim_et_al:LIPIcs.APPROX/RANDOM.2021.7, author = {Kim, Eun Jung and Lee, Euiwoong and Thilikos, Dimitrios M.}, title = {{A Constant-Factor Approximation for Weighted Bond Cover}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {7:1--7:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, 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.2021.7}, URN = {urn:nbn:de:0030-drops-147002}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.7}, annote = {Keywords: Constant-factor approximation algorithms, Primal-dual method, Bonds in graphs, Graph minors, Graph modification problems} }
Feedback for Dagstuhl Publishing