Navid Talebanfard

• Lecturer in Algorithms at Department of Computer Science, University of Sheffield

• Email: n.talebanfard@sheffield.ac.uk

Research interests: combinatorics of complexity theory, satisfiability, exponential time, etc.

Currently on leave as a Marie Curie Global Fellow working on EXCICO.

Manuscripts

• Bounded Depth Frege Lower Bounds for Random 3-CNFs via Deterministic Restrictions. arxiv (with Svyatoslav Gryaznov)

   

• Local Enumeration and Majority Lower Bounds. arxiv (with Mohit Gurumukhani, Ramamohan Paturi, Pavel Pudlák, and Michael Saks)

Publications

• On the Extension Complexity of Polytopes Separating Subsets of the Boolean Cube. Discrete and Computational Geometry. arxiv, journal version (with Pavel Hrubeš)

   

• Linear Branching Programs and Directional Affine Extractors. Computational Complexity Conference (CCC), 2022. arxiv, conference version (with Svyatoslav Gryaznov and Pavel Pudlák)

   

• A Variant of the VC-Dimension with Applications to Depth-3 Circuits, Innovations in Theoretical Computer Science (ITCS), 2022. arxiv, conference version (with Peter Frankl and Svyatoslav Gryaznov)

   

• A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm. Logical Methods in Computer Science, 2021. journal (with Michal Koucký and Vojtěch Rödl)

   

• Super Strong ETH is True for PPSZ with Small Resolution Width, Computational Complexity Conference (CCC), 2020. ECCC, conference version (with Dominik Scheder)

   

• 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 (with Nicola Galesi and Jacobo Torán)

   

• Prediction from Partial Information and Hindsight, An Alternative Proof, Information Processing Letters, 2018. ECCC, journal version (with Alexander Smal. Note that the ECCC version contains a more general result regarding decision trees.)

   

• 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 (with Ilario Bonacina)

   

• Tighter Hard Instances for PPSZ, International Colloquium on Automata, Languages, and Programming (ICALP), 2017. arxiv, conference version (with Pavel Pudlák and Dominik Scheder)

   

• On the Structure and the Number of Prime Implicants of 2-CNFs, Discrete Applied Mathematics, 2016. arxiv, journal version

   

• Improving resolution width lower bounds for k-CNFs with applications to the Strong Exponential Time Hypothesis, Information Processing Letters, 2016. journal version (with Ilario Bonacina)

   

• Circuit Complexity of Properties of Graphs with Constant Planar Cutwidth, Mathematical Foundations of Computer Science (MFCS), 2014. conference version (with Kristoffer A. Hansen, Balagopal Komarath, Jayalal Sarma, and Sven Skyum)

   

• Exponential Lower Bounds for PPSZ k-SAT Algorithm, ACM-SIAM Symposium on Discrete Algorithms (SODA), 2013. conference version (with Shiteng Chen, Dominik Scheder, and Bangsheng Tang)

Recent teaching

• Automata, Computation and Complexity, University of Sheffield, Autumn 2023.

• Boolean Function Complexity, Department of Algebra, Charles University, Autumn 2022.

• Randomness and computation, Department of Algebra, Charles University, Spring 2022.

• Selected topics in computational complexity: mathematical tools, Charles University. Co-taught with Pavel Hrubeš and Pavel Pudlák. 2021.

Workshops

• Co-organizer of Complexity Theory with a Human Face, 3rd Edition, June 2022.

• Co-organizer of Complexity Theory 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.