Processing math: 0%
\def\<#1>{\left<#1\right>} \newcommand{\L}[1]{L_{\mathrm{bip}}(#1)} \newcommand{\disjpairs}{\mathcal{D}} \DeclareDocumentCommand\setdef{mo}{\left\{#1\IfNoValueTF{#2}{}{ : #2}\right\}}

Bipartite formula complexity: a progress towards Problem 6.57

A bipartite formula F(x,y) has two groups of variables. Input leaves are arbitrary(!) boolean functions, each depending only on x-variables or on y-variables. Gates are AND and OR. For a boolean function f(x,y) of 2n variables, let \L{f} denote the minimum number of leaves in a bipartite formula computing f. [Note that \L{f} is just the bipartite formula complexity of the bipartite N\times N graph G_f defined by f with N:=2^n (Sects. 1.7.1 and 6.15 in the book).]

It is clear that every (ordinary) DeMorgan formula is a very special bipartite formula with all input functions being trivial ones: variables or their negations. So, since the highest known lower bounds for DeMorgan formulas are only cubic in the number of variables, proving such a (cubic) lower bound for (more general) bipartite formulas is a hard task.

Using a recent upper bound of Reichardt on the degree of polynomials approximating formulas of a given size, Avishay Tal has shown that \L{f}=\Omega(n^2/\log^2 n) holds for the inner product function f=IP_n. The graph G_f of this function is the bipartite graph whose adjacency \pm 1 matrix is the N\times N Hadamard H matrix with N=2^n (see Appendix A.3).

Recall the following theorem of Jürgen Forster (Sect. 4.11).

Theorem 1 (Forster [1]) The sign-rank of H is at least \sqrt{N}=2^{n/2}.
The next main tool is the following result of Ben Reichardt. For the rest, it will be convenient to treat the boolean domain as \{-1,1\}. The transition between this domain and \{0,1\} is given by simple functions (1-x)/2 and (-1)^x. Thus, -1 corresponds to 1 ("true") and +1 to 0 ("false").
Theorem 2 (Reichardt [2]) Suppose that a boolean function f:\{-1,1\}^n\to\{-1,1\} can be computed by a DeMorgan formula of size s. Then there is a multilinear polynomial p of degree O(\sqrt{s}) such that |f(z)-p(z)|\leq 1/3 holds for all z\in\{-1,1\}^n.
By the sign-rank of a boolean function f:\{-1,1\}^{2n}\to\{-1,1\} we will mean the sign-rank of the matrix M_f[x,y]=f(x,y).
Theorem 3 (Tal [3]) The sign-rank of any boolean function f(x,y) is at most s^{O(\sqrt{s})} where s=\L{f}.
Together with Theorem 1, this already yields the claimed lower bound \L{f}=\Omega(n^2/\log^2 n) for the inner product function f=IP_n.

Proof (of Thm. 3): Take a bipartite formula F(x,y) with s leaves computing f. At the i-th leaf, a product f_i(x)\cdot g_i(y) is computed, where one of f_i,g_i is the constant 1). Let F' be a read-once de Morgan formula obtained from F by replacing the i-th input gate with a formal variable z_i, for all i\in[s]. Theorem 2 gives us a multilinear polynomial p(z)=\sum_{S\subseteq [s]\colon |S|\leq d}c_S\prod_{i\in S}z_i of degree d=O(\sqrt{s}) such that F'(z)-1/3\leq p(z)\leq F'(z)+1/3 holds for all z\in\{-1,1\}^s. In particular, \mathrm{sgn}(p(z))= F'(z) holds for all z\in\{-1,1\}^s. Now replace back input variables z_i by the corresponding products f_i(x)\cdot g_i(y). Then for every x\in\{-1,1\}^n and y\in\{-1,1\}^n, the value F(x,y) is the signum of p(f_1(x)\cdot g_1(y),\cdots, f_1(x)\cdot g_1(y)) =\sum_{S\subseteq [s]\colon |S|\leq d}c_S\prod_{i\in S}f_i(x) \cdot \prod_{i\in S}g_i(y)\,. Each summand on the right-hand side corresponds to a matrix of rank 1 over the reals. Hence, their sum corresponds to a matrix of rank at most the total number s^{O(d)}=s^{O(\sqrt{s})} of summands. Thus, the matrix M_f=f(x,y) of our function f is at most s^{O(\sqrt{s})}, as claimed. \Box

References:

  1. J. Forster, A linear lower bound on the unbounded eror probabilistic communication complexity, J. Comput. Syst. Sci. 65:4 (2002) 612-625.
  2. B.W. Reichardt, Reflections for quantum query algorithms, arxiv.org/abs/1005.1601
  3. A. Tal, The bipartite formula complexity of Inner-Product is quadratic, ECCC Report No. 181, 2016.

S. Jukna, November 2016