2006/01/01 by Stasys Jukna, Jukna, Stasys
Computer Science · Mathematics · #ACC-circuits #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Graph complexity #Limits and Structures in Graph Theory #Sylvester graphs #communication complexity #single level conjecture
paper · doi:10.4230/dagsemproc.06111.8
openalex publication_date 2006/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Sigma2 eq Pi2 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.