Skip to main content

Correlation bounds against monotone NC1

Publication ,  Conference
Rossman, B
Published in: Leibniz International Proceedings in Informatics, LIPIcs
June 1, 2015

This paper gives the first correlation bounds under product distributions, including the uniform distribution, against the class mNC1 of polynomial-size O(log n)-depth monotone circuits. Our main theorem, proved using the pathset complexity framework introduced in [56], shows that the average-case k-CYCLE problem (on Erdos-Rényi random graphs with an appropriate edge density) is 1/2+ 1/poly(n) hard for mNC1. Combining this result with O'Donnell's hardness amplification theorem [43], we obtain an explicit monotone function of n variables (in the class mSAC1) which is 1/2+n-1/2+∈ hard for mNC1 under the uniform distribution for any desired constant ∈ > 0. This bound is nearly best possible, since every monotone function has agreement 1/2 + Ω(log n√n) with some function in mNC1 [44]. Our correlation bounds against mNC1 extend smoothly to non-monotone NC1 circuits with a bounded number of negation gates. Using Holley's monotone coupling theorem [30], we prove the following lemma: with respect to any product distribution, if a balanced monotone function f is 1/2 + δ hard for monotone circuits of a given size and depth, then f is 1/2 + (2t+1 - 1)δ hard for (non-monotone) circuits of the same size and depth with at most t negation gates. We thus achieve a lower bound against NC1 circuits with (1/2 - ∈) log n negation gates, improving the previous record of 1/6 log log n [7]. Our bound on negations is "half" optimal, since dlog(n + 1)e negation gates are known to be fully powerful for NC1 [3, 21].

Duke Scholars

Published In

Leibniz International Proceedings in Informatics, LIPIcs

DOI

ISSN

1868-8969

ISBN

9783939897811

Publication Date

June 1, 2015

Volume

33

Start / End Page

392 / 411
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Rossman, B. (2015). Correlation bounds against monotone NC1. In Leibniz International Proceedings in Informatics, LIPIcs (Vol. 33, pp. 392–411). https://doi.org/10.4230/LIPIcs.CCC.2015.392
Rossman, B. “Correlation bounds against monotone NC1.” In Leibniz International Proceedings in Informatics, LIPIcs, 33:392–411, 2015. https://doi.org/10.4230/LIPIcs.CCC.2015.392.
Rossman B. Correlation bounds against monotone NC1. In: Leibniz International Proceedings in Informatics, LIPIcs. 2015. p. 392–411.
Rossman, B. “Correlation bounds against monotone NC1.” Leibniz International Proceedings in Informatics, LIPIcs, vol. 33, 2015, pp. 392–411. Scopus, doi:10.4230/LIPIcs.CCC.2015.392.
Rossman B. Correlation bounds against monotone NC1. Leibniz International Proceedings in Informatics, LIPIcs. 2015. p. 392–411.

Published In

Leibniz International Proceedings in Informatics, LIPIcs

DOI

ISSN

1868-8969

ISBN

9783939897811

Publication Date

June 1, 2015

Volume

33

Start / End Page

392 / 411