Click in the text-area below, and then press Enter key to start playing the video. You will be asked to press Enter again to pause the video and type-in your transcript.

{{current_subtitle}}

  • [{{time_string(subtitle.start_time)}} - {{time_string(subtitle.end_time)}}] {{subtitle.text}}

Description

Understanding the average-case complexity of natural problems on natural distributions is an important challenge for complexity theory. In this paper we consider the average-case complexity of the $k$-Clique{} problem (for fixed $k$) on monotone circuits. A natural class of distributions in this context are ErdH{o}s-R'enyi random graphs $G(n,p)$ at threshold functions $p(n) in Theta(n^{-2/(k-1)})$, for which $Pr(G(n,p)$ contains a $k$-clique$)$ is bounded away from $0$ and $1$. Our main result is a lower bound of $omega(n^{k/4})$ on the size of monotone circuits which solve $k$-Clique{} (asymptotically almost surely) on $G(n,p)$ for two sufficiently far-apart threshold functions $p(n)$, such as $n^{-2/(k-1)}$ and $2n^{-2/(k-1)}$. This result complements a previous lower bound cite{STOC08} of $omega(n^{k/4})$ on the size of $AC^0$ circuits which solve $k$-Clique{} on $G(n,p)$ for a single threshold function $p(n)$. These two lower bounds---obtained by different techniques in the different settings of $AC^0$ and monotone circuits---support an intuition that {em random graphs at the threshold may be a source of hard instances for $k$-Clique{} in general}. (Note that similar beliefs about random extsc{SAT} are common in statistical physics.)

In addition, we show that $k/4$ in this lower bound is tight up to $o(k)$ by constructing monotone circuits of size $n^{k/4 + O(1)}$ which solve $k$-Clique{} on $G(n,p)$ for all functions $p : N o [0,1]$ (monotonizing a construction of $AC^0$ circuits due to Amano cite{Amano09}). This moreover demonstrates a gap between the worst-case and average-case complexity of $k$-Clique{} on monotone circuits, in light of an $wtOmega(n^k)$ worst-case lower bound due to Razborov cite{Razborov85}.

One technical contribution of this paper is the introduction of a new variant of sunflowers called {em $(p,q)$-sunflowers}, in which petals may overlap (but not too much on average). We prove a combinatorial theorem (along the lines of the ErdH{

Questions and Answers

You need to be logged in to be able to post here.