Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Marco Carmosino, Kenneth Hoover, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. Lifting for Constant-Depth Circuits and Applications to MCSP. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 44:1-44:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{carmosino_et_al:LIPIcs.ICALP.2021.44, author = {Carmosino, Marco and Hoover, Kenneth and Impagliazzo, Russell and Kabanets, Valentine and Kolokolova, Antonina}, title = {{Lifting for Constant-Depth Circuits and Applications to MCSP}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {44:1--44:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela 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.ICALP.2021.44}, URN = {urn:nbn:de:0030-drops-141135}, doi = {10.4230/LIPIcs.ICALP.2021.44}, annote = {Keywords: circuit complexity, constant-depth circuits, lifting theorems, Minimum Circuit Size Problem, reductions, Switching Lemma} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Rahul Ilango, Bruno Loff, and Igor C. Oliveira. NP-Hardness of Circuit Minimization for Multi-Output Functions. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 22:1-22:36, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{ilango_et_al:LIPIcs.CCC.2020.22, author = {Ilango, Rahul and Loff, Bruno and Oliveira, Igor C.}, title = {{NP-Hardness of Circuit Minimization for Multi-Output Functions}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {22:1--22:36}, 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.22}, URN = {urn:nbn:de:0030-drops-125744}, doi = {10.4230/LIPIcs.CCC.2020.22}, annote = {Keywords: MCSP, circuit minimization, communication complexity, Boolean circuit} }
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 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
Jiawei Gao. On the Fine-Grained Complexity of Least Weight Subsequence in Multitrees and Bounded Treewidth DAGs. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 16:1-16:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{gao:LIPIcs.IPEC.2019.16, author = {Gao, Jiawei}, title = {{On the Fine-Grained Complexity of Least Weight Subsequence in Multitrees and Bounded Treewidth DAGs}}, booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)}, pages = {16:1--16:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-129-0}, ISSN = {1868-8969}, year = {2019}, volume = {148}, editor = {Jansen, Bart M. P. and Telle, Jan Arne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.16}, URN = {urn:nbn:de:0030-drops-114778}, doi = {10.4230/LIPIcs.IPEC.2019.16}, annote = {Keywords: fine-grained complexity, dynamic programming, graph reachability} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Marco L. Carmosino, Russell Impagliazzo, and Manuel Sabin. Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 27:1-27:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{carmosino_et_al:LIPIcs.ICALP.2018.27, author = {Carmosino, Marco L. and Impagliazzo, Russell and Sabin, Manuel}, title = {{Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {27:1--27:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.27}, URN = {urn:nbn:de:0030-drops-90316}, doi = {10.4230/LIPIcs.ICALP.2018.27}, annote = {Keywords: Derandomization, Hardness vs Randomness, Fine-Grained Complexity, Average-Case Complexity, k-Orthogonal Vectors, k-CLIQUE} }
Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)
Marco L. Carmosino, Russell Impagliazzo, Shachar Lovett, and Ivan Mihajlin. Hardness Amplification for Non-Commutative Arithmetic Circuits. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 12:1-12:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{carmosino_et_al:LIPIcs.CCC.2018.12, author = {Carmosino, Marco L. and Impagliazzo, Russell and Lovett, Shachar and Mihajlin, Ivan}, title = {{Hardness Amplification for Non-Commutative Arithmetic Circuits}}, booktitle = {33rd Computational Complexity Conference (CCC 2018)}, pages = {12:1--12:16}, 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.12}, URN = {urn:nbn:de:0030-drops-88772}, doi = {10.4230/LIPIcs.CCC.2018.12}, annote = {Keywords: arithmetic circuits, hardness amplification, circuit lower bounds, non-commutative computation} }
Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. Agnostic Learning from Tolerant Natural Proofs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 35:1-35:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{carmosino_et_al:LIPIcs.APPROX-RANDOM.2017.35, author = {Carmosino, Marco L. and Impagliazzo, Russell and Kabanets, Valentine and Kolokolova, Antonina}, title = {{Agnostic Learning from Tolerant Natural Proofs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)}, pages = {35:1--35:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-044-6}, ISSN = {1868-8969}, year = {2017}, volume = {81}, editor = {Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.35}, URN = {urn:nbn:de:0030-drops-75842}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.35}, annote = {Keywords: agnostic learning, natural proofs, circuit lower bounds, meta-algorithms, AC0\lbrackq\rbrack, Nisan-Wigderson generator} }
Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)
Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. Learning Algorithms from Natural Proofs. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 10:1-10:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{carmosino_et_al:LIPIcs.CCC.2016.10, author = {Carmosino, Marco L. and Impagliazzo, Russell and Kabanets, Valentine and Kolokolova, Antonina}, title = {{Learning Algorithms from Natural Proofs}}, booktitle = {31st Conference on Computational Complexity (CCC 2016)}, pages = {10:1--10:24}, 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.10}, URN = {urn:nbn:de:0030-drops-58557}, doi = {10.4230/LIPIcs.CCC.2016.10}, annote = {Keywords: natural proofs, circuit complexity, lower bounds, learning, compression} }
Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. Tighter Connections between Derandomization and Circuit Lower Bounds. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 645-658, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)
@InProceedings{carmosino_et_al:LIPIcs.APPROX-RANDOM.2015.645, author = {Carmosino, Marco L. and Impagliazzo, Russell and Kabanets, Valentine and Kolokolova, Antonina}, title = {{Tighter Connections between Derandomization and Circuit Lower Bounds}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)}, pages = {645--658}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-89-7}, ISSN = {1868-8969}, year = {2015}, volume = {40}, editor = {Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.645}, URN = {urn:nbn:de:0030-drops-53285}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.645}, annote = {Keywords: derandomization, circuit lower bounds, polynomial identity testing, promise BPP, hardness vs. randomness} }
Feedback for Dagstuhl Publishing