
Upload Video
videos in mp4/mov/flv
close
Upload video
Note: publisher must agree to add uploaded document 
Upload Slides
slides or other attachment
close
Upload Slides
Note: publisher must agree to add uploaded document 
Feedback
help us improve
close
Feedback
Please help us improve your experience by sending us a comment, question or concern
Click in the textarea below, and then press Enter key to start playing the video. You will be asked to press Enter again to pause the video and typein your transcript.
{{current_subtitle}}
 [{{time_string(subtitle.start_time)}}  {{time_string(subtitle.end_time)}}] {{subtitle.text}}
Description
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 worstcase and averagecase complexity of $k$Clique{} on monotone circuits, in light of an $wtOmega(n^k)$ worstcase 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{