N. Talebanfard

activity

20142026

most citedTighter Hard Instances for PPSZ

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

collaborators

Showing 2021Show all

3 papers · 1 filter

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…