Published in: Dagstuhl Reports, Volume 13, Issue 3 (2023)
Anna Gál, Meena Mahajan, Rahul Santhanam, Till Tantau, and Manaswi Paraashar. Computational Complexity of Discrete Problems (Dagstuhl Seminar 23111). In Dagstuhl Reports, Volume 13, Issue 3, pp. 17-31, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@Article{gal_et_al:DagRep.13.3.17, author = {G\'{a}l, Anna and Mahajan, Meena and Santhanam, Rahul and Tantau, Till and Paraashar, Manaswi}, title = {{Computational Complexity of Discrete Problems (Dagstuhl Seminar 23111)}}, pages = {17--31}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2023}, volume = {13}, number = {3}, editor = {G\'{a}l, Anna and Mahajan, Meena and Santhanam, Rahul and Tantau, Till and Paraashar, Manaswi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.3.17}, URN = {urn:nbn:de:0030-drops-192261}, doi = {10.4230/DagRep.13.3.17}, annote = {Keywords: circuit complexity, communication complexity, computational complexity, lower bounds, randomness} }
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)
Rahul Santhanam. An Algorithmic Approach to Uniform Lower Bounds. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 35:1-35:26, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{santhanam:LIPIcs.CCC.2023.35, author = {Santhanam, Rahul}, title = {{An Algorithmic Approach to Uniform Lower Bounds}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {35:1--35:26}, 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.35}, URN = {urn:nbn:de:0030-drops-183053}, doi = {10.4230/LIPIcs.CCC.2023.35}, annote = {Keywords: Probabilistic Kolmogorov complexity, sampling algorithms, uniform lower bounds} }
Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Rahul Santhanam. Why MCSP Is a More Important Problem Than SAT (Invited Talk). In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, p. 2:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{santhanam:LIPIcs.FSTTCS.2022.2, author = {Santhanam, Rahul}, title = {{Why MCSP Is a More Important Problem Than SAT}}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)}, pages = {2:1--2:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-261-7}, ISSN = {1868-8969}, year = {2022}, volume = {250}, editor = {Dawar, Anuj and Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.2}, URN = {urn:nbn:de:0030-drops-173943}, doi = {10.4230/LIPIcs.FSTTCS.2022.2}, annote = {Keywords: Minimum Circuit Size Problem, Satisfiability, Cryptography, Learning, Approximation} }
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.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.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 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Ján Pich and Rahul Santhanam. Learning Algorithms Versus Automatability of Frege Systems. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 101:1-101:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{pich_et_al:LIPIcs.ICALP.2022.101, author = {Pich, J\'{a}n and Santhanam, Rahul}, title = {{Learning Algorithms Versus Automatability of Frege Systems}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {101:1--101:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.101}, URN = {urn:nbn:de:0030-drops-164427}, doi = {10.4230/LIPIcs.ICALP.2022.101}, annote = {Keywords: learning algorithms, automatability, proof complexity} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Hanlin Ren and Rahul Santhanam. A Relativization Perspective on Meta-Complexity. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 54:1-54:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{ren_et_al:LIPIcs.STACS.2022.54, author = {Ren, Hanlin and Santhanam, Rahul}, title = {{A Relativization Perspective on Meta-Complexity}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {54:1--54:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra 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.2022.54}, URN = {urn:nbn:de:0030-drops-158646}, doi = {10.4230/LIPIcs.STACS.2022.54}, annote = {Keywords: meta-complexity, relativization, minimum circuit size problem} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, and Akshayaram Srinivasan. Bounded Indistinguishability for Simple Sources. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 26:1-26:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{bogdanov_et_al:LIPIcs.ITCS.2022.26, author = {Bogdanov, Andrej and Dinesh, Krishnamoorthy and Filmus, Yuval and Ishai, Yuval and Kaplan, Avi and Srinivasan, Akshayaram}, title = {{Bounded Indistinguishability for Simple Sources}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {26:1--26:18}, 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.26}, URN = {urn:nbn:de:0030-drops-156223}, doi = {10.4230/LIPIcs.ITCS.2022.26}, annote = {Keywords: Pseudorandomness, bounded indistinguishability, complexity of sampling, constant-depth circuits, secret sharing, leakage-resilient cryptography} }
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.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.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.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 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, and Ilya Volkovich. One-Way Functions and a Conditional Variant of MKTP. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 7:1-7:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{allender_et_al:LIPIcs.FSTTCS.2021.7, author = {Allender, Eric and Cheraghchi, Mahdi and Myrisiotis, Dimitrios and Tirumala, Harsha and Volkovich, Ilya}, title = {{One-Way Functions and a Conditional Variant of MKTP}}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)}, pages = {7:1--7:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-215-0}, ISSN = {1868-8969}, year = {2021}, volume = {213}, editor = {Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.7}, URN = {urn:nbn:de:0030-drops-155181}, doi = {10.4230/LIPIcs.FSTTCS.2021.7}, annote = {Keywords: Kolmogorov complexity, KT Complexity, Minimum KT-complexity Problem, MKTP, Conditional KT Complexity, Minimum Conditional KT-complexity Problem, McKTP, one-way functions, OWFs, average-case hardness, pseudorandom generators, PRGs, pseudorandom functions, PRFs, distinguishers, learning algorithms, NP-completeness, reductions} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Ninad Rajgopal and Rahul Santhanam. On the Structure of Learnability Beyond P/Poly. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 46:1-46:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{rajgopal_et_al:LIPIcs.APPROX/RANDOM.2021.46, author = {Rajgopal, Ninad and Santhanam, Rahul}, title = {{On the Structure of Learnability Beyond P/Poly}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {46:1--46: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.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.46}, URN = {urn:nbn:de:0030-drops-147395}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.46}, annote = {Keywords: Hardness of Learning, Oracle Circuit Classes, Succinct Search, Black-Box Reductions} }
Published in: Dagstuhl Reports, Volume 11, Issue 2 (2021)
Anna Gál, Meena Mahajan, Rahul Santhanam, and Till Tantau. Computational Complexity of Discrete Problems (Dagstuhl Seminar 21121). In Dagstuhl Reports, Volume 11, Issue 2, pp. 1-16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@Article{gal_et_al:DagRep.11.2.1, author = {G\'{a}l, Anna and Mahajan, Meena and Santhanam, Rahul and Tantau, Till}, title = {{Computational Complexity of Discrete Problems (Dagstuhl Seminar 21121)}}, pages = {1--16}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2021}, volume = {11}, number = {2}, editor = {G\'{a}l, Anna and Mahajan, Meena and Santhanam, Rahul and Tantau, Till}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.11.2.1}, URN = {urn:nbn:de:0030-drops-146836}, doi = {10.4230/DagRep.11.2.1}, annote = {Keywords: circuit complexity, communication complexity, computational complexity, lower bounds, randomness} }
Feedback for Dagstuhl Publishing