Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Shuichi Hirahara and Dana Moshkovitz. Regularization of Low Error PCPs and an Application to MCSP. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 39:1-39:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{hirahara_et_al:LIPIcs.ISAAC.2023.39, author = {Hirahara, Shuichi and Moshkovitz, Dana}, title = {{Regularization of Low Error PCPs and an Application to MCSP}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {39:1--39:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.39}, URN = {urn:nbn:de:0030-drops-193411}, doi = {10.4230/LIPIcs.ISAAC.2023.39}, annote = {Keywords: PCP theorem, regularization, Minimum Circuit Size Problem} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Dean Doron and Roei Tell. Derandomization with Minimal Memory Footprint. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 11:1-11:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{doron_et_al:LIPIcs.CCC.2023.11, author = {Doron, Dean and Tell, Roei}, title = {{Derandomization with Minimal Memory Footprint}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {11:1--11:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-282-2}, ISSN = {1868-8969}, year = {2023}, volume = {264}, editor = {Ta-Shma, Amnon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.11}, URN = {urn:nbn:de:0030-drops-182816}, doi = {10.4230/LIPIcs.CCC.2023.11}, annote = {Keywords: derandomization, space-bounded computation, catalytic space} }
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.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 234, 37th Computational Complexity Conference (CCC 2022)
Louis Golowich and Salil Vadhan. Pseudorandomness of Expander Random Walks for Symmetric Functions and Permutation Branching Programs. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 27:1-27:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{golowich_et_al:LIPIcs.CCC.2022.27, author = {Golowich, Louis and Vadhan, Salil}, title = {{Pseudorandomness of Expander Random Walks for Symmetric Functions and Permutation Branching Programs}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {27:1--27:13}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.27}, URN = {urn:nbn:de:0030-drops-165893}, doi = {10.4230/LIPIcs.CCC.2022.27}, annote = {Keywords: Expander graph, Random walk, Pseudorandomness} }
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.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 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, and Salil Vadhan. Pseudorandom Generators for Read-Once Monotone Branching Programs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 58:1-58:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{doron_et_al:LIPIcs.APPROX/RANDOM.2021.58, author = {Doron, Dean and Meka, Raghu and Reingold, Omer and Tal, Avishay and Vadhan, Salil}, title = {{Pseudorandom Generators for Read-Once Monotone Branching Programs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {58:1--58:21}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.58}, URN = {urn:nbn:de:0030-drops-147513}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.58}, annote = {Keywords: Branching programs, pseudorandom generators, constant depth circuits} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, and Amnon Ta-Shma. Error Reduction for Weighted PRGs Against Read Once Branching Programs. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 22:1-22:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{cohen_et_al:LIPIcs.CCC.2021.22, author = {Cohen, Gil and Doron, Dean and Renard, Oren and Sberlo, Ori and Ta-Shma, Amnon}, title = {{Error Reduction for Weighted PRGs Against Read Once Branching Programs}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {22:1--22:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.22}, URN = {urn:nbn:de:0030-drops-142963}, doi = {10.4230/LIPIcs.CCC.2021.22}, annote = {Keywords: Pseudorandom generators, Read once branching programs, Space-bounded computation} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
William M. Hoza, Edward Pyne, and Salil Vadhan. Pseudorandom Generators for Unbounded-Width Permutation Branching Programs. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 7:1-7:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{hoza_et_al:LIPIcs.ITCS.2021.7, author = {Hoza, William M. and Pyne, Edward and Vadhan, Salil}, title = {{Pseudorandom Generators for Unbounded-Width Permutation Branching Programs}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {7:1--7: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.7}, URN = {urn:nbn:de:0030-drops-135464}, doi = {10.4230/LIPIcs.ITCS.2021.7}, annote = {Keywords: Pseudorandom generators, permutation branching programs} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Jay Mardia. Is the Space Complexity of Planted Clique Recovery the Same as That of Detection?. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 34:1-34:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{mardia:LIPIcs.ITCS.2021.34, author = {Mardia, Jay}, title = {{Is the Space Complexity of Planted Clique Recovery the Same as That of Detection?}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {34:1--34:17}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.34}, URN = {urn:nbn:de:0030-drops-135734}, doi = {10.4230/LIPIcs.ITCS.2021.34}, annote = {Keywords: Statistical computational gaps, Planted clique, Space complexity, Average case computational complexity} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Dean Doron, Amnon Ta-Shma, and Roei Tell. On Hitting-Set Generators for Polynomials That Vanish Rarely. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 7:1-7:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{doron_et_al:LIPIcs.APPROX/RANDOM.2020.7, author = {Doron, Dean and Ta-Shma, Amnon and Tell, Roei}, title = {{On Hitting-Set Generators for Polynomials That Vanish Rarely}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {7:1--7:23}, 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.7}, URN = {urn:nbn:de:0030-drops-126109}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.7}, annote = {Keywords: Hitting-set generators, Polynomials over finite fields, Quantified derandomization} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma. Near-Optimal Erasure List-Decodable Codes. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 1:1-1:27, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{benaroya_et_al:LIPIcs.CCC.2020.1, author = {Ben-Aroya, Avraham and Doron, Dean and Ta-Shma, Amnon}, title = {{Near-Optimal Erasure List-Decodable Codes}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {1:1--1:27}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.1}, URN = {urn:nbn:de:0030-drops-125531}, doi = {10.4230/LIPIcs.CCC.2020.1}, annote = {Keywords: Dispersers, Erasure codes, List decoding, Ramsey graphs, Two-source extractors} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Dean Doron, Pooya Hatami, and William M. Hoza. Log-Seed Pseudorandom Generators via Iterated Restrictions. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 6:1-6:36, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{doron_et_al:LIPIcs.CCC.2020.6, author = {Doron, Dean and Hatami, Pooya and Hoza, William M.}, title = {{Log-Seed Pseudorandom Generators via Iterated Restrictions}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {6:1--6:36}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.6}, URN = {urn:nbn:de:0030-drops-125586}, doi = {10.4230/LIPIcs.CCC.2020.6}, annote = {Keywords: Pseudorandom generators, Pseudorandom restrictions, Read-once depth-2 formulas, Parity gates} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Kuan Cheng and William M. Hoza. Hitting Sets Give Two-Sided Derandomization of Small Space. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 10:1-10:25, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{cheng_et_al:LIPIcs.CCC.2020.10, author = {Cheng, Kuan and Hoza, William M.}, title = {{Hitting Sets Give Two-Sided Derandomization of Small Space}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {10:1--10:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.10}, URN = {urn:nbn:de:0030-drops-125625}, doi = {10.4230/LIPIcs.CCC.2020.10}, annote = {Keywords: hitting sets, derandomization, read-once branching programs} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Dean Doron, Jack Murtagh, Salil Vadhan, and David Zuckerman. Spectral Sparsification via Bounded-Independence Sampling. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 39:1-39:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{doron_et_al:LIPIcs.ICALP.2020.39, author = {Doron, Dean and Murtagh, Jack and Vadhan, Salil and Zuckerman, David}, title = {{Spectral Sparsification via Bounded-Independence Sampling}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {39:1--39:21}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.39}, URN = {urn:nbn:de:0030-drops-124462}, doi = {10.4230/LIPIcs.ICALP.2020.39}, annote = {Keywords: Spectral sparsification, Derandomization, Space complexity} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Avraham Ben-Aroya, Gil Cohen, Dean Doron, and Amnon Ta-Shma. Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 43:1-43:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{benaroya_et_al:LIPIcs.APPROX-RANDOM.2019.43, author = {Ben-Aroya, Avraham and Cohen, Gil and Doron, Dean and Ta-Shma, Amnon}, title = {{Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {43:1--43:20}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.43}, URN = {urn:nbn:de:0030-drops-112587}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.43}, annote = {Keywords: Condensers, Extractors, Resilient functions, Explicit constructions} }
Feedback for Dagstuhl Publishing