Remarks on Graph Complexity

We revisit the notion of graph complexity introduced by Pudlák, Rödl, and Savický [PRS]. Using their framework, we show that sufficiently strong superlinear monotone lower bounds for the very special class of 2-slice functions would imply superpolynomial lower bounds for some other functions. Given an n-vertex graph G, the corresponding 2-slice function f _G on n variables evaluates to zero on inputs with less than two 1’s and evaluates to one on inputs with more than two 1’s. On inputs with exactly two 1’s, f _G evaluates to 1 exactly when the pair of variables set to 1 corresponds to an edge in G. Combining our observations with those from [PRS], we can show, for instance, that a lower bound of n1 + Ω(1) on the (monotone) formula size of an explicit 2-slice function f on n variables would imply a 2Ω(l) lower bound on the formula size of another explicit function g on l variables, where $l={\it \Theta}(\log n)$.We consider lower bound questions for depth-3 bipartite graph complexity. We prove some weak lower bounds on this measure using algebraic methods. For instance, our results give a lower bound of Ω((logn/ loglogn)2) for bipartite graphs arising from Hadamard matrices, such as the Paley-type bipartite graphs. A lower bound of nΩ(1) on the depth-3 complexity of an explicit bipartite graph would give superlinear size lower bounds on log-depth boolean circuits for an explicit function. Similarly, a lower bound of $2^{(\log n)^{\Omega(1)}}$ would give an explicit language outside the class $\Sigma_{\rm 2}^{cc}$ of the two-party communication complexity.