N. Talebanfard

activity

20142026

most citedTighter Hard Instances for PPSZ

1 citations · 2 across the 10 of their papers we have counts for

collaborators

12 papers

cs.CC2026

The Switching Lemma shows what the Switching Lemma cannot prove: an unconditional natural-proofs barrier

Bruno Loff, Suhail Sherif, Navid Talebanfard +1

Razborov and Rudich (JCSS'97) observed that all known lower-bound proofs follow a certain pattern: when showing that a function $F$ is hard, along the way the proof provides us wit…

cs.CC2026

Optimal Depth-Three Circuits for Inner Product

Mohit Gurumukhani, Daniel Kleber, Ramamohan Paturi +2

We show that Inner Product in $2 n$ variables, $IP_{n} (x, y) = x_{1} y_{1} \oplus \dots \oplus x_{n} y_{n}$ , can be computed by depth-3 bottom fan-in 2 circuits of size $\mathsf{poly}…

cs.CC2026

Optimal Monotone Depth-Three Circuit Lower Bounds for Majority

Mohit Gurumukhani, Daniel Kleber, Ramamohan Paturi +3

Gurumuhkani et al. (CCC'24) introduced the local enumeration problem $E n u m (k, t)$ as follows: for a natural number $k$ and a parameter $t$ , given an $n$ -variate $k$ -CNF with no sat…

cs.CC2025

Local Enumeration: The Not-All-Equal Case

Mohit Gurumukhani, Ramamohan Paturi, Michael Saks +1

Gurumukhani et al. (CCC'24) proposed the local enumeration problem Enum(k, t) as an approach to break the Super Strong Exponential Time Hypothesis (SSETH): for a natural number $k$ …

cs.CC2024

Local Enumeration and Majority Lower Bounds

Mohit Gurumukhani, Ramamohan Paturi, Pavel Pudlák +2

Depth-3 circuit lower bounds and $k$ -SAT algorithms are intimately related; the state-of-the-art $Σ_{3}^{k}$ -circuit lower bound and the $k$ -SAT algorithm are based on the same combina…

cs.CC2024

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

Svyatoslav Gryaznov, Navid Talebanfard

A major open problem in proof complexity is to demonstrate that random 3-CNFs with a linear number of clauses require super-polynomial size refutations in bounded-depth Frege syste…

cs.CC2022

Linear Branching Programs and Directional Affine Extractors

Svyatoslav Gryaznov, Pavel Pudlák, Navid Talebanfard

A natural model of read-once linear branching programs is a branching program where queries are $F_{2}$ linear forms, and along each path, the queries are linearly independe…

cs.CC2021

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

Peter Frankl, Svyatoslav Gryaznov, Navid Talebanfard

We introduce the following variant of the VC-dimension. Given $S \subseteq {0, 1}^{n}$ and a positive integer $d$ , we define $U_{d} (S)$ to be the size of the largest subset…

cs.CG2021

On the extension complexity of polytopes separating subsets of the Boolean cube

Pavel Hrubeš, Navid Talebanfard

We show that 1. for every $A \subseteq {0, 1}^{n}$ , there exists a polytope $P \subseteq R^{n}$ with $P \cap {0, 1}^{n} = A$ and extension complexity $O (2^{n /2})$ , 2. there ex…

cs.LO2021

A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm

Michal Koucký, Vojtěch Rödl, Navid Talebanfard

We show that for every $r \geq 2$ there exists $ε_{r} > 0$ such that any $r$ -uniform hypergraph with $m$ edges and maximum vertex degree $o (m)$ contains a set of at most $(\fra…

cs.CC2016★ 1 cited

Tighter Hard Instances for PPSZ

Pavel Pudlák, Dominik Scheder, Navid Talebanfard

We construct uniquely satisfiable $k$ -CNF formulas that are hard for the algorithm PPSZ. Firstly, we construct graph-instances on which "weak PPSZ" has savings of at most $(2 + ε)…

cs.DM2014★ 1 cited

On the Structure and the Number of Prime Implicants of 2-CNFs

Navid Talebanfard

Let $m (n, k)$ be the maximum number of prime implicants that any $k$ -CNF on n variables can have. We show that $3^{n /3} \leq m (n, 2) \leq (1 + o (1)) 3^{n /3}$ .