LIPIcs, Volume 33
CCC 2015, June 17-19, 2015, Portland, Oregon, USA
Editors: David Zuckerman
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Scott Aaronson, Harry Buhrman, and William Kretschmer. A Qubit, a Coin, and an Advice String Walk into a Relational Problem. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 1:1-1:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{aaronson_et_al:LIPIcs.ITCS.2024.1, author = {Aaronson, Scott and Buhrman, Harry and Kretschmer, William}, title = {{A Qubit, a Coin, and an Advice String Walk into a Relational Problem}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {1:1--1:24}, 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.1}, URN = {urn:nbn:de:0030-drops-195290}, doi = {10.4230/LIPIcs.ITCS.2024.1}, annote = {Keywords: Relational problems, quantum advice, randomized advice, FBQP, FBPP} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Vinayak M. Kumar. Tight Correlation Bounds for Circuits Between AC0 and TC0. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 18:1-18:40, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{kumar:LIPIcs.CCC.2023.18, author = {Kumar, Vinayak M.}, title = {{Tight Correlation Bounds for Circuits Between AC0 and TC0}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {18:1--18:40}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.18}, URN = {urn:nbn:de:0030-drops-182885}, doi = {10.4230/LIPIcs.CCC.2023.18}, annote = {Keywords: AC⁰, TC⁰, Switching Lemma, Lower Bounds, Correlation Bounds, Circuit Complexity} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Eshan Chattopadhyay, Jesse Goodman, and David Zuckerman. The Space Complexity of Sampling. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 40:1-40:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{chattopadhyay_et_al:LIPIcs.ITCS.2022.40, author = {Chattopadhyay, Eshan and Goodman, Jesse and Zuckerman, David}, title = {{The Space Complexity of Sampling}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {40:1--40:23}, 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.40}, URN = {urn:nbn:de:0030-drops-156366}, doi = {10.4230/LIPIcs.ITCS.2022.40}, annote = {Keywords: Complexity of distributions, complexity of sampling, extractors, list decodable codes, lower bounds, read-once branching programs, small-space computation} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
William M. Hoza. Better Pseudodistributions and Derandomization for Space-Bounded Computation. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 28:1-28:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{hoza:LIPIcs.APPROX/RANDOM.2021.28, author = {Hoza, William M.}, title = {{Better Pseudodistributions and Derandomization for Space-Bounded Computation}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {28:1--28: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.28}, URN = {urn:nbn:de:0030-drops-147217}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.28}, annote = {Keywords: Weighted pseudorandom generator, pseudorandom pseudodistribution, read-once branching program, derandomization, space complexity} }
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 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Dana Moshkovitz, Justin Oh, and David Zuckerman. Randomness Efficient Noise Stability and Generalized Small Bias Sets. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{moshkovitz_et_al:LIPIcs.FSTTCS.2020.31, author = {Moshkovitz, Dana and Oh, Justin and Zuckerman, David}, title = {{Randomness Efficient Noise Stability and Generalized Small Bias Sets}}, booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)}, pages = {31:1--31:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-174-0}, ISSN = {1868-8969}, year = {2020}, volume = {182}, editor = {Saxena, Nitin and Simon, Sunil}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.31}, URN = {urn:nbn:de:0030-drops-132721}, doi = {10.4230/LIPIcs.FSTTCS.2020.31}, annote = {Keywords: pseudorandomness, derandomization, epsilon biased sets, noise stability} }
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-dev.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-dev.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-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 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
Giordano Da Lozzo, David Eppstein, Michael T. Goodrich, and Siddharth Gupta. C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{dalozzo_et_al:LIPIcs.IPEC.2019.9, author = {Da Lozzo, Giordano and Eppstein, David and Goodrich, Michael T. and Gupta, Siddharth}, title = {{C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width}}, booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)}, pages = {9:1--9:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-129-0}, ISSN = {1868-8969}, year = {2019}, volume = {148}, editor = {Jansen, Bart M. P. and Telle, Jan Arne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.9}, URN = {urn:nbn:de:0030-drops-114705}, doi = {10.4230/LIPIcs.IPEC.2019.9}, annote = {Keywords: Clustered planarity, carving-width, non-crossing partitions, FPT} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Fu Li and David Zuckerman. Improved Extractors for Recognizable and Algebraic Sources. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 72:1-72:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{li_et_al:LIPIcs.APPROX-RANDOM.2019.72, author = {Li, Fu and Zuckerman, David}, title = {{Improved Extractors for Recognizable and Algebraic Sources}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {72:1--72:22}, 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.72}, URN = {urn:nbn:de:0030-drops-112873}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.72}, annote = {Keywords: Extractor, Pseudorandomness} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
William M. Hoza. Typically-Correct Derandomization for Small Time and Space. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 9:1-9:39, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{hoza:LIPIcs.CCC.2019.9, author = {Hoza, William M.}, title = {{Typically-Correct Derandomization for Small Time and Space}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {9:1--9:39}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.9}, URN = {urn:nbn:de:0030-drops-108317}, doi = {10.4230/LIPIcs.CCC.2019.9}, annote = {Keywords: Derandomization, pseudorandomness, space complexity} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Dean Doron, Pooya Hatami, and William M. Hoza. Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 16:1-16:34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{doron_et_al:LIPIcs.CCC.2019.16, author = {Doron, Dean and Hatami, Pooya and Hoza, William M.}, title = {{Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {16:1--16:34}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.16}, URN = {urn:nbn:de:0030-drops-108382}, doi = {10.4230/LIPIcs.CCC.2019.16}, annote = {Keywords: Pseudorandom generators, Constant-depth formulas, Explicit constructions} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Xue Chen and Eric Price. Estimating the Frequency of a Clustered Signal. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 36:1-36:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chen_et_al:LIPIcs.ICALP.2019.36, author = {Chen, Xue and Price, Eric}, title = {{Estimating the Frequency of a Clustered Signal}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {36:1--36:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.36}, URN = {urn:nbn:de:0030-drops-106128}, doi = {10.4230/LIPIcs.ICALP.2019.36}, annote = {Keywords: sublinear algorithms, Fourier transform} }
Feedback for Dagstuhl Publishing