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.