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)
Recent teaching
- 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. 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 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.