Navid Talebanfard
Research interests: combinatorics of complexity theory, satisfiability, and so on
Publications
Peter Frankl, Svyatoslav Gryaznov, Navid Talebanfard, A variant of the VC-dimension with applications to depth-3 circuits, Innovations in Theoretical Computer Science (ITCS), 2022. arxiv
Michal Koucký, Vojtěch Rödl, Navid Talebanfard, A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm. Logical Methods in Computer Science, 2021. journal
Dominik Scheder, Navid Talebanfard, Super Strong ETH is True for PPSZ with Small Resolution Width, Computational Complexity Conference (CCC), 2020. ECCC, conference version
Nicola Galesi, Navid Talebanfard, Jacobo Torán, Cops-Robber Games and the Resolution of Tseitin Formulas, ACM Transactions on Computation Theory, 2020. First version appeared in Theory and Application of Satisfiability Testing (SAT), 2018. journal version, conference version
Alexander Smal, Navid Talebanfard, Prediction from Partial Information and Hindsight, An Alternative Proof, Information Processing Letters, 2018. ECCC, journal version (note that the ECCC version contains a more general result regarding decision trees.)
Ilario Bonacina, Navid Talebanfard, Strong ETH and Resolution via Games and the Multiplicity of Strategies, Algorithmica, 2017. Special issue of International Symposium on Parameterized and Exact Computation (IPEC), 2015. journal version, conference version
Pavel Pudlák, Dominik Scheder, Navid Talebanfard, Tighter Hard Instances for PPSZ, International Colloquium on Automata, Languages, and Programming (ICALP), 2017. arxiv, conference version
Navid Talebanfard, On the Structure and the Number of Prime Implicants of 2-CNFs, Discrete Applied Mathematics, 2016. arxiv, journal version
Ilario Bonacina, Navid Talebanfard, Improving resolution width lower bounds for k-CNFs with applications to the Strong Exponential Time Hypothesis, Information Processing Letters, 2016. journal version
Kristoffer A. Hansen, Balagopal Komarath, Jayalal Sarma, Sven Skyum, Navid Talebanfard, Circuit Complexity of Properties of Graphs with Constant Planar Cutwidth, Mathematical Foundations of Computer Science (MFCS), 2014. conference version
Shiteng Chen, Dominik Scheder, Navid Talebanfard, Bangsheng Tang, Exponential Lower Bounds for PPSZ k-SAT Algorithm, ACM-SIAM Symposium on Discrete Algorithms (SODA), 2013. conference version
Manuscripts
- Pavel Hrubeš, Navid Talebanfard, On the extension complexity of polytopes separating subsets of the Boolean cube. submitted. arxiv
Recent teaching
- Selected topics in computational complexity: mathematical tools, Charles University. Co-taught with Pavel Hrubeš and Pavel Pudlák. Winter 2021.
Seminars
- Complexity seminar, Institute of Mathematics, CAS.
- Logic seminar, Institute of Mathematics, CAS.
- Seminar on limits of efficient computation, Computer Science Institute, Charles University.
Workshops
- Co-organizer of Complexity Thoery with a Human Face, 2nd Edition, October 2021.
- Co-organizer of Complexity Theory with a Human Face, September 2020.
- Co-organizer of FEALORA workshop, November 2018.