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 hypergraphs with m edges and an arbitrary hypergraph G with m - t edges, we may count the number of super-hypergraphs of G (i.e., hypergraphs 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-hypergraphs 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 hypergraphs are 3-uniform, this implies a lower bound of Ω(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 n × n × n tensors that are naturally associated with hypergraph trees. In fact, our bound also applies to the stronger notion of border rank, for which our result essentially matches the best lower bounds known.