Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Eshan Chattopadhyay and Jyun-Jie Liao. Recursive Error Reduction for Regular Branching Programs. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 29:1-29:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chattopadhyay_et_al:LIPIcs.ITCS.2024.29, author = {Chattopadhyay, Eshan and Liao, Jyun-Jie}, title = {{Recursive Error Reduction for Regular Branching Programs}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {29:1--29: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.29}, URN = {urn:nbn:de:0030-drops-195571}, doi = {10.4230/LIPIcs.ITCS.2024.29}, annote = {Keywords: read-once branching program, regular branching program, weighted pseudorandom generator, derandomization} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Aaron (Louie) Putterman and Edward Pyne. Pseudorandom Linear Codes Are List-Decodable to Capacity. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 90:1-90:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{putterman_et_al:LIPIcs.ITCS.2024.90, author = {Putterman, Aaron (Louie) and Pyne, Edward}, title = {{Pseudorandom Linear Codes Are List-Decodable to Capacity}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {90:1--90:21}, 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.90}, URN = {urn:nbn:de:0030-drops-196183}, doi = {10.4230/LIPIcs.ITCS.2024.90}, annote = {Keywords: Derandomization, error-correcting codes} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Chin Ho Lee, Edward Pyne, and Salil Vadhan. On the Power of Regular and Permutation Branching Programs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 44:1-44:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{lee_et_al:LIPIcs.APPROX/RANDOM.2023.44, author = {Lee, Chin Ho and Pyne, Edward and Vadhan, Salil}, title = {{On the Power of Regular and Permutation Branching Programs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {44:1--44:22}, 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.44}, URN = {urn:nbn:de:0030-drops-188698}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.44}, annote = {Keywords: Pseudorandomness, Branching Programs} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Chin Ho Lee, Edward Pyne, and Salil Vadhan. Fourier Growth of Regular Branching Programs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 2:1-2:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{lee_et_al:LIPIcs.APPROX/RANDOM.2022.2, author = {Lee, Chin Ho and Pyne, Edward and Vadhan, Salil}, title = {{Fourier Growth of Regular Branching Programs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {2:1--2:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, 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.2022.2}, URN = {urn:nbn:de:0030-drops-171247}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.2}, annote = {Keywords: pseudorandomness, fourier analysis} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Andrej Bogdanov, William M. Hoza, Gautam Prakriya, and Edward Pyne. Hitting Sets for Regular Branching Programs. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 3:1-3:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bogdanov_et_al:LIPIcs.CCC.2022.3, author = {Bogdanov, Andrej and Hoza, William M. and Prakriya, Gautam and Pyne, Edward}, title = {{Hitting Sets for Regular Branching Programs}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {3:1--3:22}, 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.3}, URN = {urn:nbn:de:0030-drops-165658}, doi = {10.4230/LIPIcs.CCC.2022.3}, annote = {Keywords: Pseudorandomness, hitting set generators, space-bounded computation} }
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-dev.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 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Eric Allender, John Gouwar, Shuichi Hirahara, and Caleb Robelle. Cryptographic Hardness Under Projections for Time-Bounded Kolmogorov Complexity. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 54:1-54:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{allender_et_al:LIPIcs.ISAAC.2021.54, author = {Allender, Eric and Gouwar, John and Hirahara, Shuichi and Robelle, Caleb}, title = {{Cryptographic Hardness Under Projections for Time-Bounded Kolmogorov Complexity}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {54:1--54:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-214-3}, ISSN = {1868-8969}, year = {2021}, volume = {212}, editor = {Ahn, Hee-Kap and Sadakane, Kunihiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.54}, URN = {urn:nbn:de:0030-drops-154875}, doi = {10.4230/LIPIcs.ISAAC.2021.54}, annote = {Keywords: Kolmogorov Complexity, Interactive Proofs, Minimum Circuit Size Problem, Worst-case to Average-case Reductions} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Louis Golowich. Improved Product-Based High-Dimensional Expanders. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 38:1-38:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{golowich:LIPIcs.APPROX/RANDOM.2021.38, author = {Golowich, Louis}, title = {{Improved Product-Based High-Dimensional Expanders}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {38:1--38:17}, 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.38}, URN = {urn:nbn:de:0030-drops-147319}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.38}, annote = {Keywords: High-Dimensional Expander, Expander Graph, Random Walk} }
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-dev.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)
Edward Pyne and Salil Vadhan. Pseudodistributions That Beat All Pseudorandom Generators (Extended Abstract). In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 33:1-33:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{pyne_et_al:LIPIcs.CCC.2021.33, author = {Pyne, Edward and Vadhan, Salil}, title = {{Pseudodistributions That Beat All Pseudorandom Generators (Extended Abstract)}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {33:1--33:15}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.33}, URN = {urn:nbn:de:0030-drops-143070}, doi = {10.4230/LIPIcs.CCC.2021.33}, annote = {Keywords: pseudorandomness, space-bounded computation, spectral graph theory} }
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-dev.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)
Venkatesan Guruswami and Vinayak M. Kumar. Pseudobinomiality of the Sticky Random Walk. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 48:1-48:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{guruswami_et_al:LIPIcs.ITCS.2021.48, author = {Guruswami, Venkatesan and Kumar, Vinayak M.}, title = {{Pseudobinomiality of the Sticky Random Walk}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {48:1--48:19}, 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.48}, URN = {urn:nbn:de:0030-drops-135870}, doi = {10.4230/LIPIcs.ITCS.2021.48}, annote = {Keywords: Expander Graphs, Fourier analysis, Markov Chains, Pseudorandomness, Random Walks} }
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-dev.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 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Marco Gaboardi, Kobbi Nissim, and David Purser. The Complexity of Verifying Loop-Free Programs as Differentially Private. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 129:1-129:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{gaboardi_et_al:LIPIcs.ICALP.2020.129, author = {Gaboardi, Marco and Nissim, Kobbi and Purser, David}, title = {{The Complexity of Verifying Loop-Free Programs as Differentially Private}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {129:1--129:17}, 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.129}, URN = {urn:nbn:de:0030-drops-125362}, doi = {10.4230/LIPIcs.ICALP.2020.129}, annote = {Keywords: differential privacy, program verification, probabilistic programs} }
Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)
Victor Balcer and Albert Cheu. Separating Local & Shuffled Differential Privacy via Histograms. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 1:1-1:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{balcer_et_al:LIPIcs.ITC.2020.1, author = {Balcer, Victor and Cheu, Albert}, title = {{Separating Local \& Shuffled Differential Privacy via Histograms}}, booktitle = {1st Conference on Information-Theoretic Cryptography (ITC 2020)}, pages = {1:1--1:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-151-1}, ISSN = {1868-8969}, year = {2020}, volume = {163}, editor = {Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.1}, URN = {urn:nbn:de:0030-drops-121068}, doi = {10.4230/LIPIcs.ITC.2020.1}, annote = {Keywords: Differential Privacy, Distributed Protocols, Histograms} }
Feedback for Dagstuhl Publishing