Complexity seminar

Circuit lower bounds via non-negative rank

Pavel Hrubeš

IM CAS

Friday, 15. March 2019 - 13:30 to 15:00

in IM, rear building, ground floor

The non-negative rank of a matrix is a quantity which has found several applications in communication

complexity and extension complexity of polytopes. We will show that certain lower bounds on non-negative rank

imply, at least in principle, circuit lower bounds. With a Boolean function $f$ and $\epsilon>0$, we associate

an explicit matrix $M_\epsilon(f)$ so that the circuit size of $f$ is at least the non-negative rank of

$M_{\epsilon}(f)$, for $\epsilon$ sufficiently small. We also discuss continuity properties of the

non-negative rank.

complexity and extension complexity of polytopes. We will show that certain lower bounds on non-negative rank

imply, at least in principle, circuit lower bounds. With a Boolean function $f$ and $\epsilon>0$, we associate

an explicit matrix $M_\epsilon(f)$ so that the circuit size of $f$ is at least the non-negative rank of

$M_{\epsilon}(f)$, for $\epsilon$ sufficiently small. We also discuss continuity properties of the

non-negative rank.