Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, and Igor C. Oliveira. Exact Search-To-Decision Reductions for Time-Bounded Kolmogorov Complexity. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 29:1-29:56, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{hirahara_et_al:LIPIcs.CCC.2024.29, author = {Hirahara, Shuichi and Kabanets, Valentine and Lu, Zhenjian and Oliveira, Igor C.}, title = {{Exact Search-To-Decision Reductions for Time-Bounded Kolmogorov Complexity}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {29:1--29:56}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.29}, URN = {urn:nbn:de:0030-drops-204256}, doi = {10.4230/LIPIcs.CCC.2024.29}, annote = {Keywords: average-case complexity, Kolmogorov complexity, search-to-decision reductions} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Sevag Gharibian and Jonas Kamminga. BQP, Meet NP: Search-To-Decision Reductions and Approximate Counting. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 70:1-70:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{gharibian_et_al:LIPIcs.ICALP.2024.70, author = {Gharibian, Sevag and Kamminga, Jonas}, title = {{BQP, Meet NP: Search-To-Decision Reductions and Approximate Counting}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {70:1--70:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.70}, URN = {urn:nbn:de:0030-drops-202134}, doi = {10.4230/LIPIcs.ICALP.2024.70}, annote = {Keywords: Approximate Counting, Search to Decision Reduction, BQP, NP, Oracle Complexity Class} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, and Yuichi Yoshida. One-Tape Turing Machine and Branching Program Lower Bounds for MCSP. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 23:1-23:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{cheraghchi_et_al:LIPIcs.STACS.2021.23, author = {Cheraghchi, Mahdi and Hirahara, Shuichi and Myrisiotis, Dimitrios and Yoshida, Yuichi}, title = {{One-Tape Turing Machine and Branching Program Lower Bounds for MCSP}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {23:1--23:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.23}, URN = {urn:nbn:de:0030-drops-136681}, doi = {10.4230/LIPIcs.STACS.2021.23}, annote = {Keywords: Minimum Circuit Size Problem, Kolmogorov Complexity, One-Tape Turing Machines, Branching Programs, Lower Bounds, Pseudorandom Generators, Hitting Set Generators} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Shuichi Hirahara and Osamu Watanabe. On Nonadaptive Security Reductions of Hitting Set Generators. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{hirahara_et_al:LIPIcs.APPROX/RANDOM.2020.15, author = {Hirahara, Shuichi and Watanabe, Osamu}, title = {{On Nonadaptive Security Reductions of Hitting Set Generators}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {15:1--15:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-164-1}, ISSN = {1868-8969}, year = {2020}, volume = {176}, editor = {Byrka, Jaros{\l}aw and Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.15}, URN = {urn:nbn:de:0030-drops-126182}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.15}, annote = {Keywords: hitting set generator, black-box reduction, average-case complexity} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Shuichi Hirahara. Unexpected Power of Random Strings. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 41:1-41:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{hirahara:LIPIcs.ITCS.2020.41, author = {Hirahara, Shuichi}, title = {{Unexpected Power of Random Strings}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {41:1--41:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.41}, URN = {urn:nbn:de:0030-drops-117262}, doi = {10.4230/LIPIcs.ITCS.2020.41}, annote = {Keywords: Kolmogorov-Randomness, Nonadaptive Reduction, BPP, Symmetric Alternation} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Edith Hemaspaandra, Lane A. Hemaspaandra, Holger Spakowski, and Osamu Watanabe. The Robustness of LWPP and WPP, with an Application to Graph Reconstruction. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{hemaspaandra_et_al:LIPIcs.MFCS.2018.51, author = {Hemaspaandra, Edith and Hemaspaandra, Lane A. and Spakowski, Holger and Watanabe, Osamu}, title = {{The Robustness of LWPP and WPP, with an Application to Graph Reconstruction}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {51:1--51:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-086-6}, ISSN = {1868-8969}, year = {2018}, volume = {117}, editor = {Potapov, Igor and Spirakis, Paul and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.51}, URN = {urn:nbn:de:0030-drops-96330}, doi = {10.4230/LIPIcs.MFCS.2018.51}, annote = {Keywords: structural complexity theory, robustness of counting classes, the legitimate deck problem, PP-lowness, the Reconstruction Conjecture} }
Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)
Shuichi Hirahara and Osamu Watanabe. Limits of Minimum Circuit Size Problem as Oracle. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 18:1-18:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{hirahara_et_al:LIPIcs.CCC.2016.18, author = {Hirahara, Shuichi and Watanabe, Osamu}, title = {{Limits of Minimum Circuit Size Problem as Oracle}}, booktitle = {31st Conference on Computational Complexity (CCC 2016)}, pages = {18:1--18:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-008-8}, ISSN = {1868-8969}, year = {2016}, volume = {50}, editor = {Raz, Ran}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.18}, URN = {urn:nbn:de:0030-drops-58426}, doi = {10.4230/LIPIcs.CCC.2016.18}, annote = {Keywords: minimum circuit size problem, NP-completeness, randomized reductions, resource-bounded Kolmogorov complexity, Turing reductions} }
Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)
Andreas Goerdt, Pavel Pudlák, Uwe Schöning, and Osamu Watanabe. The Propositional Satisfiability Problem -- Algorithms and Lower Bounds (Dagstuhl Seminar 03141). Dagstuhl Seminar Report 374, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)
@TechReport{goerdt_et_al:DagSemRep.374, author = {Goerdt, Andreas and Pudl\'{a}k, Pavel and Sch\"{o}ning, Uwe and Watanabe, Osamu}, title = {{The Propositional Satisfiability Problem -- Algorithms and Lower Bounds (Dagstuhl Seminar 03141)}}, pages = {1--5}, ISSN = {1619-0203}, year = {2003}, type = {Dagstuhl Seminar Report}, number = {374}, institution = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.374}, URN = {urn:nbn:de:0030-drops-152545}, doi = {10.4230/DagSemRep.374}, }