License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06111.8
URN: urn:nbn:de:0030-drops-6218
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2006/621/
Go to the corresponding Portal

Jukna, Stasys

Graphs and Circuits: Some Further Remarks

pdf-format:
06111.JuknaStasys.Paper.621.pdf (0.2 MB)

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.

BibTeX - Entry

@InProceedings{jukna:DagSemProc.06111.8,
  author =	{Jukna, Stasys},
  title =	{{Graphs and Circuits: Some Further Remarks}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2006/621},
  URN =		{urn:nbn:de:0030-drops-6218},
  doi =		{10.4230/DagSemProc.06111.8},
  annote =	{Keywords: Graph complexity, single level conjecture, Sylvester graphs, communication complexity, ACC-circuits}
}

Keywords: Graph complexity, single level conjecture, Sylvester graphs, communication complexity, ACC-circuits
Collection: 06111 - Complexity of Boolean Functions
Issue Date: 2006
Date of publication: 30.11.2006

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI