License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2015.392
URN: urn:nbn:de:0030-drops-50785
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5078/
Go to the corresponding LIPIcs Volume Portal

Rossman, Benjamin

Correlation Bounds Against Monotone NC^1

pdf-format:
30.pdf (0.6 MB)

Abstract

This paper gives the first correlation bounds under product distributions, including the uniform distribution, against the class mNC^ of polynomial-size O(log(n))-depth monotone circuits. Our main theorem, proved using the pathset complexity framework introduced in [Rossmann,arXiv:1312.0355], shows that the average-case k-CYCLE problem (on Erdös-Renyi random graphs with an appropriate edge density) is 1/2 + 1/poly(n) hard for mNC^1. Combining this result with O'Donnell's hardness amplification theorem [O'Donnell,2002], we obtain an explicit monotone function of n variables (in the class mSAC^1) which is 1/2 + n^(-1/2+epsilon) hard for mNC^1 under the uniform distribution for any desired constant epsilon > 0. This bound is nearly best possible, since every monotone function has agreement 1/2 + Omega(log(n)/sqrt(n)) with some function in mNC^1 [O'Donnell/Wimmer,FOCS'09].

Our correlation bounds against mNC^1 extend smoothly to non-monotone NC^1 circuits with a bounded number of negation gates. Using Holley's monotone coupling theorem [Holley,Comm. Math. Physics,1974], we prove the following lemma: with respect to any product distribution, if a balanced monotone function f is 1/2 + delta hard for monotone circuits of a given size and depth, then f is 1/2 + (2^(t+1)-1)*delta hard for (non-monotone) circuits of the same size and depth with at most t negation gates. We thus achieve a lower bound against NC^1 circuits with (1/2-epsilon)*log(n) negation gates, improving the previous record of 1/6*log(log(n)) [Amano/Maruoka,SIAML J. Comp.,2005]. Our bound on negations is "half" optimal, since \lceil log(n+1) \rceil negation gates are known to be fully powerful for NC^1 [Ajtai/Komlos/Szemeredi,STOC'83; Fischer,GI'75].

BibTeX - Entry

@InProceedings{rossman:LIPIcs:2015:5078,
  author =	{Benjamin Rossman},
  title =	{{Correlation Bounds Against Monotone NC^1}},
  booktitle =	{30th Conference on Computational Complexity (CCC 2015)},
  pages =	{392--411},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-81-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{33},
  editor =	{David Zuckerman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5078},
  URN =		{urn:nbn:de:0030-drops-50785},
  doi =		{10.4230/LIPIcs.CCC.2015.392},
  annote =	{Keywords: circuit complexity, average-case complexity}
}

Keywords: circuit complexity, average-case complexity
Collection: 30th Conference on Computational Complexity (CCC 2015)
Issue Date: 2015
Date of publication: 06.06.2015

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