Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Svyatoslav Gryaznov, Pavel Pudlák, and Navid Talebanfard. Linear Branching Programs and Directional Affine Extractors. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{gryaznov_et_al:LIPIcs.CCC.2022.4, author = {Gryaznov, Svyatoslav and Pudl\'{a}k, Pavel and Talebanfard, Navid}, title = {{Linear Branching Programs and Directional Affine Extractors}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {4:1--4:16}, 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.4}, URN = {urn:nbn:de:0030-drops-165664}, doi = {10.4230/LIPIcs.CCC.2022.4}, annote = {Keywords: Boolean Functions, Average-Case Lower Bounds, AC0\lbrack2\rbrack, Affine Dispersers, Affine Extractors} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Peter Frankl, Svyatoslav Gryaznov, and Navid Talebanfard. A Variant of the VC-Dimension with Applications to Depth-3 Circuits. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 72:1-72:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{frankl_et_al:LIPIcs.ITCS.2022.72, author = {Frankl, Peter and Gryaznov, Svyatoslav and Talebanfard, Navid}, title = {{A Variant of the VC-Dimension with Applications to Depth-3 Circuits}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {72:1--72:19}, 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.72}, URN = {urn:nbn:de:0030-drops-156680}, doi = {10.4230/LIPIcs.ITCS.2022.72}, annote = {Keywords: VC-dimension, Hypergraph, Clique, Affine Disperser, Circuit} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Dominik Scheder and Navid Talebanfard. Super Strong ETH Is True for PPSZ with Small Resolution Width. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 3:1-3:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{scheder_et_al:LIPIcs.CCC.2020.3, author = {Scheder, Dominik and Talebanfard, Navid}, title = {{Super Strong ETH Is True for PPSZ with Small Resolution Width}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {3:1--3:12}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.3}, URN = {urn:nbn:de:0030-drops-125552}, doi = {10.4230/LIPIcs.CCC.2020.3}, annote = {Keywords: k-SAT, PPSZ, Resolution} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Nicola Galesi, Dmitry Itsykson, Artur Riazanov, and Anastasia Sofronova. Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 49:1-49:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{galesi_et_al:LIPIcs.MFCS.2019.49, author = {Galesi, Nicola and Itsykson, Dmitry and Riazanov, Artur and Sofronova, Anastasia}, title = {{Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {49:1--49:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.49}, URN = {urn:nbn:de:0030-drops-109932}, doi = {10.4230/LIPIcs.MFCS.2019.49}, annote = {Keywords: Tseitin formula, treewidth, AC0-Frege} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Pavel Pudlák, Dominik Scheder, and Navid Talebanfard. Tighter Hard Instances for PPSZ. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 85:1-85:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{pudlak_et_al:LIPIcs.ICALP.2017.85, author = {Pudl\'{a}k, Pavel and Scheder, Dominik and Talebanfard, Navid}, title = {{Tighter Hard Instances for PPSZ}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {85:1--85:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.85}, URN = {urn:nbn:de:0030-drops-74144}, doi = {10.4230/LIPIcs.ICALP.2017.85}, annote = {Keywords: k-SAT, Strong Exponential Time Hypothesis, PPSZ, Resolution} }
Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
Ilario Bonacina and Navid Talebanfard. Strong ETH and Resolution via Games and the Multiplicity of Strategies. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 248-257, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{bonacina_et_al:LIPIcs.IPEC.2015.248, author = {Bonacina, Ilario and Talebanfard, Navid}, title = {{Strong ETH and Resolution via Games and the Multiplicity of Strategies}}, booktitle = {10th International Symposium on Parameterized and Exact Computation (IPEC 2015)}, pages = {248--257}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-92-7}, ISSN = {1868-8969}, year = {2015}, volume = {43}, editor = {Husfeldt, Thore and Kanj, Iyad}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.248}, URN = {urn:nbn:de:0030-drops-55876}, doi = {10.4230/LIPIcs.IPEC.2015.248}, annote = {Keywords: Strong Exponential Time Hypothesis, resolution, proof systems} }
Feedback for Dagstuhl Publishing