Math @ Duke

Publications [#348682] of Benjamin Rossman
Papers Published
 Rossman, B, Correlation bounds against monotone NC^{1},
Leibniz International Proceedings in Informatics, Lipics, vol. 33
(June, 2015),
pp. 392411, ISBN 9783939897811 [doi]
(last updated on 2022/05/19)
Abstract: This paper gives the first correlation bounds under product distributions, including the uniform distribution, against the class mNC1 of polynomialsize O(log n)depth monotone circuits. Our main theorem, proved using the pathset complexity framework introduced in [56], shows that the averagecase kCYCLE problem (on ErdosRé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+n1/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 nonmonotone 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 (nonmonotone) 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].


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

