Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 1-952, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@Proceedings{santhanam:LIPIcs.CCC.2024, title = {{LIPIcs, Volume 300, CCC 2024, Complete Volume}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {1--952}, 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}, URN = {urn:nbn:de:0030-drops-203955}, doi = {10.4230/LIPIcs.CCC.2024}, annote = {Keywords: LIPIcs, Volume 300, CCC 2024, Complete Volume} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 0:i-0:xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{santhanam:LIPIcs.CCC.2024.0, author = {Santhanam, Rahul}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {0:i--0:xiv}, 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.0}, URN = {urn:nbn:de:0030-drops-203961}, doi = {10.4230/LIPIcs.CCC.2024.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Noel Arteche, Erfan Khaniki, Ján Pich, and Rahul Santhanam. From Proof Complexity to Circuit Complexity via Interactive Protocols. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{arteche_et_al:LIPIcs.ICALP.2024.12, author = {Arteche, Noel and Khaniki, Erfan and Pich, J\'{a}n and Santhanam, Rahul}, title = {{From Proof Complexity to Circuit Complexity via Interactive Protocols}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {12:1--12:20}, 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.12}, URN = {urn:nbn:de:0030-drops-201557}, doi = {10.4230/LIPIcs.ICALP.2024.12}, annote = {Keywords: proof complexity, circuit complexity, interactive protocols} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Zhenjian Lu and Rahul Santhanam. Impagliazzo’s Worlds Through the Lens of Conditional Kolmogorov Complexity. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 110:1-110:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{lu_et_al:LIPIcs.ICALP.2024.110, author = {Lu, Zhenjian and Santhanam, Rahul}, title = {{Impagliazzo’s Worlds Through the Lens of Conditional Kolmogorov Complexity}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {110:1--110:17}, 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.110}, URN = {urn:nbn:de:0030-drops-202538}, doi = {10.4230/LIPIcs.ICALP.2024.110}, annote = {Keywords: meta-complexity, Kolmogorov complexity, one-way functions, average-case complexity} }
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)
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)
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)
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 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} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Hanlin Ren and Rahul Santhanam. Hardness of KT Characterizes Parallel Cryptography. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 35:1-35:58, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{ren_et_al:LIPIcs.CCC.2021.35, author = {Ren, Hanlin and Santhanam, Rahul}, title = {{Hardness of KT Characterizes Parallel Cryptography}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {35:1--35:58}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.35}, URN = {urn:nbn:de:0030-drops-143091}, doi = {10.4230/LIPIcs.CCC.2021.35}, annote = {Keywords: one-way function, meta-complexity, KT complexity, parallel cryptography, randomized encodings} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Shafi Goldwasser, Russell Impagliazzo, Toniann Pitassi, and Rahul Santhanam. On the Pseudo-Deterministic Query Complexity of NP Search Problems. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 36:1-36:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{goldwasser_et_al:LIPIcs.CCC.2021.36, author = {Goldwasser, Shafi and Impagliazzo, Russell and Pitassi, Toniann and Santhanam, Rahul}, title = {{On the Pseudo-Deterministic Query Complexity of NP Search Problems}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {36:1--36:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.36}, URN = {urn:nbn:de:0030-drops-143104}, doi = {10.4230/LIPIcs.CCC.2021.36}, annote = {Keywords: Pseudo-determinism, Query complexity, Proof complexity} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Michael Saks and Rahul Santhanam. Circuit Lower Bounds from NP-Hardness of MCSP Under Turing Reductions. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 26:1-26:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{saks_et_al:LIPIcs.CCC.2020.26, author = {Saks, Michael and Santhanam, Rahul}, title = {{Circuit Lower Bounds from NP-Hardness of MCSP Under Turing Reductions}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {26:1--26:13}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.26}, URN = {urn:nbn:de:0030-drops-125786}, doi = {10.4230/LIPIcs.CCC.2020.26}, annote = {Keywords: Minimum Circuit Size Problem, Turing reductions, circuit lower bounds} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Rahul Santhanam. Pseudorandomness and the Minimum Circuit Size Problem. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 68:1-68:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{santhanam:LIPIcs.ITCS.2020.68, author = {Santhanam, Rahul}, title = {{Pseudorandomness and the Minimum Circuit Size Problem}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {68:1--68:26}, 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.68}, URN = {urn:nbn:de:0030-drops-117532}, doi = {10.4230/LIPIcs.ITCS.2020.68}, annote = {Keywords: Minimum Circuit Size Problem, Pseudorandomness, Average-case Complexity, Natural Proofs, Universality Conjecture} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Lijie Chen, Shuichi Hirahara, Igor C. Oliveira, Ján Pich, Ninad Rajgopal, and Rahul Santhanam. Beyond Natural Proofs: Hardness Magnification and Locality. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 70:1-70:48, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{chen_et_al:LIPIcs.ITCS.2020.70, author = {Chen, Lijie and Hirahara, Shuichi and Oliveira, Igor C. and Pich, J\'{a}n and Rajgopal, Ninad and Santhanam, Rahul}, title = {{Beyond Natural Proofs: Hardness Magnification and Locality}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {70:1--70:48}, 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.70}, URN = {urn:nbn:de:0030-drops-117550}, doi = {10.4230/LIPIcs.ITCS.2020.70}, annote = {Keywords: Hardness Magnification, Natural Proofs, Minimum Circuit Size Problem, Circuit Lower Bounds} }
Published in: Dagstuhl Reports, Volume 9, Issue 3 (2019)
Anna Gál, Rahul Santhanam, and Till Tantau. Computational Complexity of Discrete Problems (Dagstuhl Seminar 19121). In Dagstuhl Reports, Volume 9, Issue 3, pp. 64-82, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@Article{gal_et_al:DagRep.9.3.64, author = {G\'{a}l, Anna and Santhanam, Rahul and Tantau, Till}, title = {{Computational Complexity of Discrete Problems (Dagstuhl Seminar 19121)}}, pages = {64--82}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2019}, volume = {9}, number = {3}, editor = {G\'{a}l, Anna 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.9.3.64}, URN = {urn:nbn:de:0030-drops-112920}, doi = {10.4230/DagRep.9.3.64}, annote = {Keywords: circuit complexity, communication complexity, computational complexity, parametrisation, randomness} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Igor Carboni Oliveira, Rahul Santhanam, and Srikanth Srinivasan. Parity Helps to Compute Majority. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 23:1-23:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{oliveira_et_al:LIPIcs.CCC.2019.23, author = {Oliveira, Igor Carboni and Santhanam, Rahul and Srinivasan, Srikanth}, title = {{Parity Helps to Compute Majority}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {23:1--23:17}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.23}, URN = {urn:nbn:de:0030-drops-108453}, doi = {10.4230/LIPIcs.CCC.2019.23}, annote = {Keywords: Computational Complexity, Boolean Circuits, Lower Bounds, Parity, Majority} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Igor Carboni Oliveira, Ján Pich, and Rahul Santhanam. Hardness Magnification near State-Of-The-Art Lower Bounds. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 27:1-27:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{oliveira_et_al:LIPIcs.CCC.2019.27, author = {Oliveira, Igor Carboni and Pich, J\'{a}n and Santhanam, Rahul}, title = {{Hardness Magnification near State-Of-The-Art Lower Bounds}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {27:1--27:29}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.27}, URN = {urn:nbn:de:0030-drops-108494}, doi = {10.4230/LIPIcs.CCC.2019.27}, annote = {Keywords: Circuit Complexity, Minimum Circuit Size Problem, Kolmogorov Complexity} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Igor Carboni Oliveira, Rahul Santhanam, and Roei Tell. Expander-Based Cryptography Meets Natural Proofs. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{carbonioliveira_et_al:LIPIcs.ITCS.2019.18, author = {Carboni Oliveira, Igor and Santhanam, Rahul and Tell, Roei}, title = {{Expander-Based Cryptography Meets Natural Proofs}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {18:1--18:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.18}, URN = {urn:nbn:de:0030-drops-101112}, doi = {10.4230/LIPIcs.ITCS.2019.18}, annote = {Keywords: Pseudorandom Generators, One-Way Functions, Expanders, Circuit Complexity} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Ninad Rajgopal, Rahul Santhanam, and Srikanth Srinivasan. Deterministically Counting Satisfying Assignments for Constant-Depth Circuits with Parity Gates, with Implications for Lower Bounds. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 78:1-78:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{rajgopal_et_al:LIPIcs.MFCS.2018.78, author = {Rajgopal, Ninad and Santhanam, Rahul and Srinivasan, Srikanth}, title = {{Deterministically Counting Satisfying Assignments for Constant-Depth Circuits with Parity Gates, with Implications for Lower Bounds}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {78:1--78:15}, 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.78}, URN = {urn:nbn:de:0030-drops-96607}, doi = {10.4230/LIPIcs.MFCS.2018.78}, annote = {Keywords: circuit satisfiability, circuit lower bounds, polynomial method, derandomization} }
Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Igor Carboni Oliveira and Rahul Santhanam. Pseudo-Derandomizing Learning and Approximation. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 55:1-55:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{carbonioliveira_et_al:LIPIcs.APPROX-RANDOM.2018.55, author = {Carboni Oliveira, Igor and Santhanam, Rahul}, title = {{Pseudo-Derandomizing Learning and Approximation}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)}, pages = {55:1--55:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-085-9}, ISSN = {1868-8969}, year = {2018}, volume = {116}, editor = {Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.55}, URN = {urn:nbn:de:0030-drops-94598}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.55}, annote = {Keywords: derandomization, learning, approximation, boolean circuits} }
Published in: Dagstuhl Reports, Volume 8, Issue 1 (2018)
Albert Atserias, Jakob Nordström, Pavel Pudlák, and Rahul Santhanam. Proof Complexity (Dagstuhl Seminar 18051). In Dagstuhl Reports, Volume 8, Issue 1, pp. 124-157, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@Article{atserias_et_al:DagRep.8.1.124, author = {Atserias, Albert and Nordstr\"{o}m, Jakob and Pudl\'{a}k, Pavel and Santhanam, Rahul}, title = {{Proof Complexity (Dagstuhl Seminar 18051)}}, pages = {124--157}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2018}, volume = {8}, number = {1}, editor = {Atserias, Albert and Nordstr\"{o}m, Jakob and Pudl\'{a}k, Pavel and Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.8.1.124}, URN = {urn:nbn:de:0030-drops-92864}, doi = {10.4230/DagRep.8.1.124}, annote = {Keywords: bounded arithmetic, computational complexity, logic, proof complexity, satisfiability algorithms} }
Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)
Shuichi Hirahara, Igor C. Oliveira, and Rahul Santhanam. NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 5:1-5:31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{hirahara_et_al:LIPIcs.CCC.2018.5, author = {Hirahara, Shuichi and Oliveira, Igor C. and Santhanam, Rahul}, title = {{NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits}}, booktitle = {33rd Computational Complexity Conference (CCC 2018)}, pages = {5:1--5:31}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-069-9}, ISSN = {1868-8969}, year = {2018}, volume = {102}, editor = {Servedio, Rocco A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.5}, URN = {urn:nbn:de:0030-drops-88831}, doi = {10.4230/LIPIcs.CCC.2018.5}, annote = {Keywords: NP-hardness, Minimum Circuit Size Problem, depth-3 circuits} }
Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)
Shuichi Hirahara and Rahul Santhanam. On the Average-Case Complexity of MCSP and Its Variants. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 7:1-7:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{hirahara_et_al:LIPIcs.CCC.2017.7, author = {Hirahara, Shuichi and Santhanam, Rahul}, title = {{On the Average-Case Complexity of MCSP and Its Variants}}, booktitle = {32nd Computational Complexity Conference (CCC 2017)}, pages = {7:1--7:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-040-8}, ISSN = {1868-8969}, year = {2017}, volume = {79}, editor = {O'Donnell, Ryan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.7}, URN = {urn:nbn:de:0030-drops-75406}, doi = {10.4230/LIPIcs.CCC.2017.7}, annote = {Keywords: minimum circuit size problem, average-case complexity, circuit lower bounds, time-bounded Kolmogorov complexity, hardness} }
Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)
Igor C. Carboni Oliveira and Rahul Santhanam. Conspiracies Between Learning Algorithms, Circuit Lower Bounds, and Pseudorandomness. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 18:1-18:49, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{oliveira_et_al:LIPIcs.CCC.2017.18, author = {Oliveira, Igor C. Carboni and Santhanam, Rahul}, title = {{Conspiracies Between Learning Algorithms, Circuit Lower Bounds, and Pseudorandomness}}, booktitle = {32nd Computational Complexity Conference (CCC 2017)}, pages = {18:1--18:49}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-040-8}, ISSN = {1868-8969}, year = {2017}, volume = {79}, editor = {O'Donnell, Ryan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.18}, URN = {urn:nbn:de:0030-drops-75327}, doi = {10.4230/LIPIcs.CCC.2017.18}, annote = {Keywords: boolean circuits, learning theory, pseudorandomness} }
Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)
Andrew Drucker, Jesper Nederlof, and Rahul Santhanam. Exponential Time Paradigms Through the Polynomial Time Lens. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 36:1-36:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{drucker_et_al:LIPIcs.ESA.2016.36, author = {Drucker, Andrew and Nederlof, Jesper and Santhanam, Rahul}, title = {{Exponential Time Paradigms Through the Polynomial Time Lens}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {36:1--36:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.36}, URN = {urn:nbn:de:0030-drops-63871}, doi = {10.4230/LIPIcs.ESA.2016.36}, annote = {Keywords: exponential time paradigms, branching, dynamic programming, lower bounds} }
Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)
Ruiwen Chen, Rahul Santhanam, and Srikanth Srinivasan. Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 1:1-1:35, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{chen_et_al:LIPIcs.CCC.2016.1, author = {Chen, Ruiwen and Santhanam, Rahul and Srinivasan, Srikanth}, title = {{Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits}}, booktitle = {31st Conference on Computational Complexity (CCC 2016)}, pages = {1:1--1:35}, 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.1}, URN = {urn:nbn:de:0030-drops-58447}, doi = {10.4230/LIPIcs.CCC.2016.1}, annote = {Keywords: threshold circuit, satisfiability algorithm, circuit lower bound} }
Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)
Lance Fortnow and Rahul Santhanam. New Non-Uniform Lower Bounds for Uniform Classes. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{fortnow_et_al:LIPIcs.CCC.2016.19, author = {Fortnow, Lance and Santhanam, Rahul}, title = {{New Non-Uniform Lower Bounds for Uniform Classes}}, booktitle = {31st Conference on Computational Complexity (CCC 2016)}, pages = {19:1--19:14}, 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.19}, URN = {urn:nbn:de:0030-drops-58503}, doi = {10.4230/LIPIcs.CCC.2016.19}, annote = {Keywords: Computational complexity, nondeterminism, nonuniform complexity} }
Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)
Igor Carboni Oliveira and Rahul Santhanam. Majority is Incompressible by AC^0[p] Circuits. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 124-157, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{oliveira_et_al:LIPIcs.CCC.2015.124, author = {Oliveira, Igor Carboni and Santhanam, Rahul}, title = {{Majority is Incompressible by AC^0\lbrackp\rbrack Circuits}}, booktitle = {30th Conference on Computational Complexity (CCC 2015)}, pages = {124--157}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-81-1}, ISSN = {1868-8969}, year = {2015}, volume = {33}, editor = {Zuckerman, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.124}, URN = {urn:nbn:de:0030-drops-50658}, doi = {10.4230/LIPIcs.CCC.2015.124}, annote = {Keywords: interactive communication, compression, circuit lower bound} }
Published in: Dagstuhl Reports, Volume 4, Issue 10 (2015)
Olaf Beyersdorff, Edward A. Hirsch, Jan Krajicek, and Rahul Santhanam. Optimal algorithms and proofs (Dagstuhl Seminar 14421). In Dagstuhl Reports, Volume 4, Issue 10, pp. 51-68, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@Article{beyersdorff_et_al:DagRep.4.10.51, author = {Beyersdorff, Olaf and Hirsch, Edward A. and Krajicek, Jan and Santhanam, Rahul}, title = {{Optimal algorithms and proofs (Dagstuhl Seminar 14421)}}, pages = {51--68}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2015}, volume = {4}, number = {10}, editor = {Beyersdorff, Olaf and Hirsch, Edward A. and Krajicek, Jan and Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.4.10.51}, URN = {urn:nbn:de:0030-drops-48923}, doi = {10.4230/DagRep.4.10.51}, annote = {Keywords: computational complexity, proof complexity, approximation algorithms, optimal algorithms, optimal proof systems, speedup theorems} }
Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Maurice Jansen and Rahul Santhanam. Stronger Lower Bounds and Randomness-Hardness Trade-Offs Using Associated Algebraic Complexity Classes. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 519-530, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
@InProceedings{jansen_et_al:LIPIcs.STACS.2012.519, author = {Jansen, Maurice and Santhanam, Rahul}, title = {{Stronger Lower Bounds and Randomness-Hardness Trade-Offs Using Associated Algebraic Complexity Classes}}, booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)}, pages = {519--530}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-35-4}, ISSN = {1868-8969}, year = {2012}, volume = {14}, editor = {D\"{u}rr, Christoph and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.519}, URN = {urn:nbn:de:0030-drops-34307}, doi = {10.4230/LIPIcs.STACS.2012.519}, annote = {Keywords: Computational Complexity, Circuit Lower Bounds, Polynomial Identity Testing, Derandomization} }
Published in: Dagstuhl Seminar Proceedings, Volume 9421, Algebraic Methods in Computational Complexity (2010)
Harry Buhrman, Lance Fortnow, and Rahul Santhanam. Unconditional Lower Bounds against Advice. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 9421, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{buhrman_et_al:DagSemProc.09421.8, author = {Buhrman, Harry and Fortnow, Lance and Santhanam, Rahul}, title = {{Unconditional Lower Bounds against Advice}}, booktitle = {Algebraic Methods in Computational Complexity}, pages = {1--11}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {9421}, editor = {Manindra Agrawal and Lance Fortnow and Thomas Thierauf and Christopher Umans}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09421.8}, URN = {urn:nbn:de:0030-drops-24112}, doi = {10.4230/DagSemProc.09421.8}, annote = {Keywords: Advice, derandomization, diagonalization, lower bounds, semantic classes} }
Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)
Mark Braverman, Stephen Cook, Pierre McKenzie, Rahul Santhanam, and Dustin Wehr. Fractional Pebbling and Thrifty Branching Programs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 109-120, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{braverman_et_al:LIPIcs.FSTTCS.2009.2311, author = {Braverman, Mark and Cook, Stephen and McKenzie, Pierre and Santhanam, Rahul and Wehr, Dustin}, title = {{Fractional Pebbling and Thrifty Branching Programs}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {109--120}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-13-2}, ISSN = {1868-8969}, year = {2009}, volume = {4}, editor = {Kannan, Ravi and Narayan Kumar, K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2311}, URN = {urn:nbn:de:0030-drops-23111}, doi = {10.4230/LIPIcs.FSTTCS.2009.2311}, annote = {Keywords: Branching programs, space complexity, tree evaluation, pebbling} }
Feedback for Dagstuhl Publishing