Paper Info
Title
The Monotone Complexity of k-clique on Random Graphs
Abstract
It is widely suspected that Erd\H{o}s-R\'enyi 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(n^{k/4})$ solves the $k$-clique problem with high probability on $\ER(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 {\em quasi-sunflowers}, a new relaxation of sunflowers in which petals may overlap slightly on average. A ``quasi-sunflower lemma'' (\`a la the Erd\H{o}s-Rado sunflower lemma) leads to our novel lower bounds within Razborov's method of approximations.
Year
DOI
Venue
2014
10.1109/FOCS.2010.26
SIAM J. Comput.
Keywords
DocType
Volume
random graphs,monotone complexity,s-rado sunflower lemma,high probability,average-case hardness result,hard instance,em quasi-sunflowers,monotone circuit,enyi random graph,quasi-sunflower lemma,far-apart threshold function,clique problem,random graph,additives,logic gates,circuit complexity,probability,graph theory,approximation algorithms,random processes,average case complexity,lattices,computational complexity,clique,digital tv
Journal
43
Issue
ISSN
Citations 
1
0272-5428
6
PageRank 
References 
Authors
0.58
10
1
Name
Order
Citations
PageRank
Benjamin Rossman129820.00