In this paper we present a combinatorial approach for proving complexity lower bounds. We mainly focus on the following instantiation of it. Consider a pair of properties of m-edge regular hypergraphs. Suppose they are ``indistinguishable'' with respect to hypergraphs with m−t edges, in the sense that every such hypergraph has the same number of super-hypergraphs satisfying each property. Roughly speaking, we show that finding a pair of distinct such properties implies an m(t−1) lower bound on the rank of explicit tensors.

We also show, albeit non-explicitly, that near-optimal rank lower bounds can be obtained in this manner. Furthermore, we consider the t=2 case and prove that it already implies non-trivial lower bounds. In particular, we derive a (tight) lower bound of 3n2 on the rank of nnn tensors naturally associated with hypergraph forests (which apparently was not known before; in fact, our bound also applies to the so-called border rank, and as such, is not far from the best lower bounds known).