Navid Talebanfard

Research interests: combinatorics of complexity theory, satisfiability, and so on

## Publications

• On the Extension Complexity of Polytopes Separating Subsets of the Boolean Cube. To appear in Discrete and Computational Geometry. arxiv (with Pavel Hrubeš)

• Linear Branching Programs and Directional Affine Extractors. Computational Complexity Conference (CCC), 2022. arxiv (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)