Math @ Duke

Publications [#348689] of Benjamin Rossman
Papers Published
 Rossman, B, The monotone complexity of kclique on random graphs,
Annual Symposium on Foundations of Computer Science (Proceedings)
(January, 2010),
pp. 193201, ISBN 9780769542447 [doi]
(last updated on 2022/05/19)
Abstract: It is widely suspected that Erdocombining double acute accentsRényi random graphs are a source of hard instances for clique problems. Giving further evidence for this belief, we prove the first averagecase hardness result for the kclique problem on monotone circuits. Specifically, we show that no monotone circuit of size O(nk/4) solves the kclique problem with high probability on G(n, p) for two sufficiently farapart threshold functions p(n) (for instance n2/(k1) and 2n2/(k1)). Moreover, the exponent k/4 in this result is tight up to an additive constant. One technical contribution of this paper is the introduction of quasisunflowers, a new relaxation of sunflowers in which petals may overlap slightly on average. A "quasisunflower lemma" (à la the Erdocombining double acute accentsRado sunflower lemma) leads to our novel lower bounds within Razborov's method of approximations. © 2010 IEEE.


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

