N. Talebanfard

activity

20212026

collaborators

3 papers

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.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…