Graphs and Circuits: Some Further Remarks

Abstract

We consider the power of single level circuits in the context of
  graph complexity. We first prove that the single level conjecture
  fails for fanin-$2$ circuits over the basis ${oplus,land,1}$.
  This shows that the (surpisingly tight) phenomenon, established by
  Mirwald and Schnorr (1992) for quadratic functions, has no analogon
  for graphs. We then show that the single level conjecture fails for
  unbounded fanin circuits over ${lor,land,1}$.  This partially
  answers the question of Pudl'ak, R"odl and Savick'y (1986).  We
  also prove that $Sigma_2
eq Pi_2$ in a restricted version of the
  hierarhy of communication complexity classes introduced by Babai,
  Frankl and Simon (1986).  Further, we show that even depth-$2$
  circuits are surprisingly powerful: every bipartite $n	imes n$
  graph of maximum degree $Delta$ can be represented by a monotone
  CNF with $O(Deltalog n)$ clauses.  We also discuss a relation
  between graphs and $ACC$-circuits.