Complexity Lower Bounds through Balanced Graph Properties

摘要

We present a combinatorial approach for proving complexity lower bounds, we focus on the following instantiation of this approach. For a property of regular hyper graphs with $m$ edges and an arbitrary hyper graph $G$ with $m-t$ edges, we may count the number of super-hyper graphs of $G$ (i.e., hyper graphs obtained by adding $t$ edges) satisfying the property. Suppose that we find a pair of these properties where every such $G$ has the same number of super-hyper graphs satisfying each property. We show that in this case, we immediately obtain an explicit $m/(t-1)$ lower bound on the rank of tensors (which are high-dimensional matrices). Notice that if the hyper graphs are $3$-uniform, this implies a lower bound of $Omega(m/t)$ for arithmetic circuits. We also show, albeit non-explicitly, that essentially-optimal lower bounds can be obtained using this approach. Furthermore, we exemplify our approach in the $t=2$ case, and prove that even in this case we can already obtain interesting lower bounds. In particular, we derive a (tight) lower bound of $3n/2$ on the rank of $ntimes ntimes n$ tensors that are naturally associated with hyper graph trees. In fact, our bound also applies to the stronger notion of {em border} rank, for which our result essentially matches the best lower bounds known.