Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Shuichi Hirahara, Zhenjian Lu, and Hanlin Ren. Bounded Relativization. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 6:1-6:45, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{hirahara_et_al:LIPIcs.CCC.2023.6, author = {Hirahara, Shuichi and Lu, Zhenjian and Ren, Hanlin}, title = {{Bounded Relativization}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {6:1--6:45}, 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.6}, URN = {urn:nbn:de:0030-drops-182764}, doi = {10.4230/LIPIcs.CCC.2023.6}, annote = {Keywords: relativization, circuit lower bound, derandomization, explicit construction, pseudodeterministic algorithms, interactive proofs} }
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)
James Cook and Ian Mertz. Trading Time and Space in Catalytic Branching Programs. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 8:1-8:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{cook_et_al:LIPIcs.CCC.2022.8, author = {Cook, James and Mertz, Ian}, title = {{Trading Time and Space in Catalytic Branching Programs}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {8:1--8:21}, 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.8}, URN = {urn:nbn:de:0030-drops-165708}, doi = {10.4230/LIPIcs.CCC.2022.8}, annote = {Keywords: complexity theory, branching programs, amortized, space complexity, catalytic computation} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Shachar Lovett, Raghu Meka, Ian Mertz, Toniann Pitassi, and Jiapeng Zhang. Lifting with Sunflowers. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 104:1-104:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{lovett_et_al:LIPIcs.ITCS.2022.104, author = {Lovett, Shachar and Meka, Raghu and Mertz, Ian and Pitassi, Toniann and Zhang, Jiapeng}, title = {{Lifting with Sunflowers}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {104:1--104:24}, 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.104}, URN = {urn:nbn:de:0030-drops-157004}, doi = {10.4230/LIPIcs.ITCS.2022.104}, annote = {Keywords: Lifting theorems, communication complexity, combinatorics, sunflowers} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Gregory Rosenthal. Bounds on the QAC^0 Complexity of Approximating Parity. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 32:1-32:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{rosenthal:LIPIcs.ITCS.2021.32, author = {Rosenthal, Gregory}, title = {{Bounds on the QAC^0 Complexity of Approximating Parity}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {32:1--32: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.32}, URN = {urn:nbn:de:0030-drops-135713}, doi = {10.4230/LIPIcs.ITCS.2021.32}, annote = {Keywords: quantum circuit complexity, QAC^0, fanout, parity, nekomata} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Ian Mertz, Toniann Pitassi, and Yuanhao Wei. Short Proofs Are Hard to Find. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 84:1-84:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{mertz_et_al:LIPIcs.ICALP.2019.84, author = {Mertz, Ian and Pitassi, Toniann and Wei, Yuanhao}, title = {{Short Proofs Are Hard to Find}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {84:1--84:16}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.84}, URN = {urn:nbn:de:0030-drops-106605}, doi = {10.4230/LIPIcs.ICALP.2019.84}, annote = {Keywords: automatizability, Resolution, SAT solvers, proof complexity} }
Feedback for Dagstuhl Publishing