ECCC-Report TR11-138https://eccc.weizmann.ac.il/report/2011/138Comments and Revisions published for TR11-138en-usMon, 24 Oct 2011 12:12:26 +0200
Paper TR11-138
| Complexity Lower Bounds through Balanced Graph Properties |
Guy Moshkovitz
https://eccc.weizmann.ac.il/report/2011/138In 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).Mon, 24 Oct 2011 12:12:26 +0200https://eccc.weizmann.ac.il/report/2011/138