Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#348689] of Benjamin Rossman

Papers Published

  1. Rossman, B, The monotone complexity of k-clique on random graphs, Annual Symposium on Foundations of Computer Science (Proceedings) (January, 2010), pp. 193-201, ISBN 9780769542447 [doi]
    (last updated on 2022/05/19)

    It is widely suspected that Erdocombining double acute accents-Rényi random graphs are a source of hard instances for clique problems. Giving further evidence for this belief, we prove the first average-case hardness result for the k-clique problem on monotone circuits. Specifically, we show that no monotone circuit of size O(nk/4) solves the k-clique problem with high probability on G(n, p) for two sufficiently far-apart threshold functions p(n) (for instance n-2/(k-1) and 2n-2/(k-1)). 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 quasi-sunflowers, a new relaxation of sunflowers in which petals may overlap slightly on average. A "quasi-sunflower lemma" (à la the Erdocombining double acute accents-Rado sunflower lemma) leads to our novel lower bounds within Razborov's method of approximations. © 2010 IEEE.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320