Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Jiawei Li. Total NP Search Problems with Abundant Solutions. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 75:1-75:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{li:LIPIcs.ITCS.2024.75, author = {Li, Jiawei}, title = {{Total NP Search Problems with Abundant Solutions}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {75:1--75:23}, 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.75}, URN = {urn:nbn:de:0030-drops-196031}, doi = {10.4230/LIPIcs.ITCS.2024.75}, annote = {Keywords: TFNP, Pigeonhole Principle} }
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-dev.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)
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-dev.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)
Halley Goldberg and Valentine Kabanets. Improved Learning from Kolmogorov Complexity. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 12:1-12:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{goldberg_et_al:LIPIcs.CCC.2023.12, author = {Goldberg, Halley and Kabanets, Valentine}, title = {{Improved Learning from Kolmogorov Complexity}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {12:1--12:29}, 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.12}, URN = {urn:nbn:de:0030-drops-182825}, doi = {10.4230/LIPIcs.CCC.2023.12}, annote = {Keywords: learning, Kolmogorov complexity, meta-complexity, average-case complexity} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Eric Allender, Shuichi Hirahara, and Harsha Tirumala. Kolmogorov Complexity Characterizes Statistical Zero Knowledge. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{allender_et_al:LIPIcs.ITCS.2023.3, author = {Allender, Eric and Hirahara, Shuichi and Tirumala, Harsha}, title = {{Kolmogorov Complexity Characterizes Statistical Zero Knowledge}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {3:1--3:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.3}, URN = {urn:nbn:de:0030-drops-175063}, doi = {10.4230/LIPIcs.ITCS.2023.3}, annote = {Keywords: Kolmogorov Complexity, Interactive Proofs} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Shuichi Hirahara and Mikito Nanashima. Learning Versus Pseudorandom Generators in Constant Parallel Time. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 70:1-70:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{hirahara_et_al:LIPIcs.ITCS.2023.70, author = {Hirahara, Shuichi and Nanashima, Mikito}, title = {{Learning Versus Pseudorandom Generators in Constant Parallel Time}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {70:1--70:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.70}, URN = {urn:nbn:de:0030-drops-175736}, doi = {10.4230/LIPIcs.ITCS.2023.70}, annote = {Keywords: Parallel cryptography, polynomial-stretch pseudorandom generators in NC⁰, PAC learning, average-case complexity, fixed-parameter tractability} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Halley Goldberg, Valentine Kabanets, Zhenjian Lu, and Igor C. Oliveira. Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 16:1-16:60, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{goldberg_et_al:LIPIcs.CCC.2022.16, author = {Goldberg, Halley and Kabanets, Valentine and Lu, Zhenjian and Oliveira, Igor C.}, title = {{Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {16:1--16:60}, 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.16}, URN = {urn:nbn:de:0030-drops-165785}, doi = {10.4230/LIPIcs.CCC.2022.16}, annote = {Keywords: average-case complexity, Kolmogorov complexity, meta-complexity, worst-case to average-case reductions, learning} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Shuichi Hirahara and Mikito Nanashima. Finding Errorless Pessiland in Error-Prone Heuristica. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 25:1-25:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{hirahara_et_al:LIPIcs.CCC.2022.25, author = {Hirahara, Shuichi and Nanashima, Mikito}, title = {{Finding Errorless Pessiland in Error-Prone Heuristica}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {25:1--25:28}, 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.25}, URN = {urn:nbn:de:0030-drops-165875}, doi = {10.4230/LIPIcs.CCC.2022.25}, annote = {Keywords: average-case complexity, oracle separation, relativization barrier, meta-complexity, learning, auxiliary-input cryptography} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Shuichi Hirahara. Symmetry of Information from Meta-Complexity. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 26:1-26:41, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{hirahara:LIPIcs.CCC.2022.26, author = {Hirahara, Shuichi}, title = {{Symmetry of Information from Meta-Complexity}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {26:1--26:41}, 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.26}, URN = {urn:nbn:de:0030-drops-165880}, doi = {10.4230/LIPIcs.CCC.2022.26}, annote = {Keywords: resource-bounded Kolmogorov complexity, average-case complexity, pseudorandomness, hardness of approximation, unconditional lower bound} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Michael Saks and Rahul Santhanam. On Randomized Reductions to the Random Strings. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 29:1-29:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{saks_et_al:LIPIcs.CCC.2022.29, author = {Saks, Michael and Santhanam, Rahul}, title = {{On Randomized Reductions to the Random Strings}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {29:1--29:30}, 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.29}, URN = {urn:nbn:de:0030-drops-165912}, doi = {10.4230/LIPIcs.CCC.2022.29}, annote = {Keywords: Kolmogorov complexity, randomized reductions} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Lijie Chen, Shuichi Hirahara, and Neekon Vafa. Average-Case Hardness of NP and PH from Worst-Case Fine-Grained Assumptions. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 45:1-45:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{chen_et_al:LIPIcs.ITCS.2022.45, author = {Chen, Lijie and Hirahara, Shuichi and Vafa, Neekon}, title = {{Average-Case Hardness of NP and PH from Worst-Case Fine-Grained Assumptions}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {45:1--45:16}, 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.45}, URN = {urn:nbn:de:0030-drops-156411}, doi = {10.4230/LIPIcs.ITCS.2022.45}, annote = {Keywords: Average-case complexity, worst-case to average-case reduction} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Shuichi Hirahara and Rahul Santhanam. Errorless Versus Error-Prone Average-Case Complexity. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 84:1-84:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{hirahara_et_al:LIPIcs.ITCS.2022.84, author = {Hirahara, Shuichi and Santhanam, Rahul}, title = {{Errorless Versus Error-Prone Average-Case Complexity}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {84:1--84: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.84}, URN = {urn:nbn:de:0030-drops-156803}, doi = {10.4230/LIPIcs.ITCS.2022.84}, annote = {Keywords: average-case complexity, instance checker, pseudorandomness} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Shuichi Hirahara and Rahul Santhanam. Excluding PH Pessiland. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 85:1-85:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{hirahara_et_al:LIPIcs.ITCS.2022.85, author = {Hirahara, Shuichi and Santhanam, Rahul}, title = {{Excluding PH Pessiland}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {85:1--85:25}, 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.85}, URN = {urn:nbn:de:0030-drops-156819}, doi = {10.4230/LIPIcs.ITCS.2022.85}, annote = {Keywords: average-case complexity, pseudorandomness, meta-complexity} }
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 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Shuichi Hirahara and François Le Gall. Test of Quantumness with Small-Depth Quantum Circuits. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 59:1-59:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{hirahara_et_al:LIPIcs.MFCS.2021.59, author = {Hirahara, Shuichi and Le Gall, Fran\c{c}ois}, title = {{Test of Quantumness with Small-Depth Quantum Circuits}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {59:1--59:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.59}, URN = {urn:nbn:de:0030-drops-144996}, doi = {10.4230/LIPIcs.MFCS.2021.59}, annote = {Keywords: Quantum computing, small-depth circuits, quantum cryptography} }
Feedback for Dagstuhl Publishing