Navid Talebanfard

According to our database, Navid Talebanfard authored at least 17 papers between 2013 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of two.

2024

Bounded Depth Frege Lower Bounds for Random 3-CNFs via Deterministic Restrictions.

Svyatoslav Gryaznov, Navid Talebanfard

CoRR, 2024

Local Enumeration and Majority Lower Bounds.

Mohit Gurumukhani, Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Navid Talebanfard

Proceedings of the 39th Computational Complexity Conference, 2024

2023

On the Extension Complexity of Polytopes Separating Subsets of the Boolean Cube.

Pavel Hrubes, Navid Talebanfard

Discret. Comput. Geom., July, 2023

2022

A Variant of the VC-Dimension with Applications to Depth-3 Circuits.

Peter Frankl, Svyatoslav Gryaznov, Navid Talebanfard

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Linear Branching Programs and Directional Affine Extractors.

Svyatoslav Gryaznov, Pavel Pudlák, Navid Talebanfard

Proceedings of the 37th Computational Complexity Conference, 2022

2020

Super Strong ETH is true for strong PPSZ.

Dominik Scheder, Navid Talebanfard

Electron. Colloquium Comput. Complex., 2020

Super Strong ETH Is True for PPSZ with Small Resolution Width.

Dominik Scheder, Navid Talebanfard

Proceedings of the 35th Computational Complexity Conference, 2020

2019

A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm.

Michal Koucký, Vojtech Rödl, Navid Talebanfard

Electron. Colloquium Comput. Complex., 2019

2018

Prediction from partial information and hindsight, an alternative proof.

Alexander V. Smal, Navid Talebanfard

Inf. Process. Lett., 2018

Cops-Robber games and the resolution of Tseitin formulas.

Nicola Galesi, Navid Talebanfard, Jacobo Torán

Electron. Colloquium Comput. Complex., 2018

2017

Strong ETH and Resolution via Games and the Multiplicity of Strategies.

Ilario Bonacina, Navid Talebanfard

Algorithmica, 2017

Tighter Hard Instances for PPSZ.

Pavel Pudlák, Dominik Scheder, Navid Talebanfard

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

Improving resolution width lower bounds for k-CNFs with applications to the Strong Exponential Time Hypothesis.

Ilario Bonacina, Navid Talebanfard

Inf. Process. Lett., 2016

On the structure and the number of prime implicants of 2-s.

Navid Talebanfard

Discret. Appl. Math., 2016

2014

On the Structure and the Number of Prime Implicants of k-CNF Formulas.

Navid Talebanfard

CoRR, 2014

Circuit Complexity of Properties of Graphs with Constant Planar Cutwidth.

Kristoffer Arnsfelt Hansen, Balagopal Komarath, Jayalal Sarma, Sven Skyum, Navid Talebanfard

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

2013

Exponential Lower Bounds for the PPSZ <i>k</i>-SAT Algorithm.

Dominik Scheder, Bangsheng Tang, Shiteng Chen, Navid Talebanfard

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013