Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Rubi Arviv, Lily Chung, Reut Levi, and Edward Pyne. Improved Local Computation Algorithms for Constructing Spanners. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 42:1-42:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{arviv_et_al:LIPIcs.APPROX/RANDOM.2023.42, author = {Arviv, Rubi and Chung, Lily and Levi, Reut and Pyne, Edward}, title = {{Improved Local Computation Algorithms for Constructing Spanners}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {42:1--42:23}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.42}, URN = {urn:nbn:de:0030-drops-188671}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.42}, annote = {Keywords: Local Computation Algorithms, Spanners} }
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.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.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.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 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Amartya Shankha Biswas, Edward Pyne, and Ronitt Rubinfeld. Local Access to Random Walks. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 24:1-24:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{biswas_et_al:LIPIcs.ITCS.2022.24, author = {Biswas, Amartya Shankha and Pyne, Edward and Rubinfeld, Ronitt}, title = {{Local Access to Random Walks}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {24:1--24: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.24}, URN = {urn:nbn:de:0030-drops-156209}, doi = {10.4230/LIPIcs.ITCS.2022.24}, annote = {Keywords: sublinear time algorithms, random generation, local computation} }
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.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.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} }
Feedback for Dagstuhl Publishing