Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR11-138 | 24th October 2011 11:45

Complexity Lower Bounds through Balanced Graph Properties

TR11-138
Authors: Guy Moshkovitz
Publication: 24th October 2011 12:12
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).