Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



TR11-138 | 24th October 2011 11:45

Complexity Lower Bounds through Balanced Graph Properties


Authors: Guy Moshkovitz
Publication: 24th October 2011 12:12
Downloads: 1136


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 $3n/2$ on the rank of $n\times n\times n$ 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).

ISSN 1433-8092 | Imprint