Rossman, Benjamin
Correlation Bounds Against Monotone NC^1
Abstract
This paper gives the first correlation bounds under product distributions, including the uniform distribution, against the class mNC^ of polynomialsize O(log(n))depth monotone circuits. Our main theorem, proved using the pathset complexity framework introduced in [Rossmann,arXiv:1312.0355], shows that the averagecase kCYCLE problem (on ErdösRenyi 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 nonmonotone 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 (nonmonotone) 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/2epsilon)*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 = {392411},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897811},
ISSN = {18688969},
year = {2015},
volume = {33},
editor = {David Zuckerman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5078},
URN = {urn:nbn:de:0030drops50785},
doi = {10.4230/LIPIcs.CCC.2015.392},
annote = {Keywords: circuit complexity, averagecase complexity}
}
2015
Keywords: 

circuit complexity, averagecase complexity 
Seminar: 

30th Conference on Computational Complexity (CCC 2015)

Issue date: 

2015 
Date of publication: 

2015 