\frac{(p-1)^l\cdot l!}{(p-1)\cdot l} = (p-1)^{l-1}\cdot (l-1)!$ many sets of $\mathfrak{F}$, and hence there exists an element $x\in Z$ such that it is contained in more than $(p-1)^{l-1}\cdot (l-1)!$ sets of $\mathfrak{F}$. Now consider the collection of those sets that contain $x$ and remove $x$ from it. By induction you have a sunflower of $p$ petals, put back $x$ into the core and we have got the required sunflower \end{proof} We shall have $\mathfrak{F} = \{X_1, X_2, \cdots, X_r, Y_1, \cdots, Y_s\}$ and choose $m$ such that $m = (p-1)^l\cdot l!$, hence if we have more than $m$ clique indicators, we ``pluck'' the sunflower. If $X_1, \cdots,X_p$ form the $p$-petalled sunflower, replace all of them by the common intersection $X_1 \cap X_2$. And hence, with every plucking, the number of clique indicators go down by $1$, repeat this process until you have at most $m$ clique indicators. Thus we have approximated an $\vee$ gate, we shall call it $A \sqcup B$. \\ Approximating an $\wedge$ gate requires a little more work. $A\wedge B$ looks like \begin{eqnarray*} A\wedge B & = & \parn{\bigvee_{i=1}^r I_{X_i}}\wedge \parn{\bigvee_{j=1}^s I_{Y_j}}\\ & = & \bigvee_{i=1}^r \bigvee_{j=1}^s \parn{I_{X_i} \wedge I_{Y_j}} \end{eqnarray*} We now have two problems, firstly $I_{X_i} \wedge I_{Y_j}$ isn't even a clique indicator. This can be tackled by just replacing $I_{X_i}\wedge I_{Y_j}$ by $I_{X_i \vee Y_j}$. If $|X_i + Y_j| > l$, just drop this clique indicator. As for our second problem of having a union of $2m$ clique indicators, apply the plucking as before to reduce this number to $m$. This approximator will be denoted by $A\sqcap B$\\ The approximator of the output gate will be our approximate circuit $C'$. \subsection{Approximated circuit makes lots of errors} \begin{lemma} Either $C'$ is $0$ on all positive tests or the number of negative tests on which $C'$ is $1$ is at least $$\parn{1 - \frac{\binom{l}{2}}{k-1}}(k-1)^n$$ \end{lemma} \begin{proof} The only way $C'$ is $0$ on all positive instance is when our $A\sqcap B$ approximator throws out all clique indicators because their sizes are greater than $l$. Hence, if it is non-zero on positive test cases, $$ C' = \bigvee_{i=1}^r I_{X_i} $$ where $0\neq r \leq m$ and $|X_i|\leq l$. Pick a negative instance at random among the $(k-1)^n$ choices. The probability that the approximator outputs a $1$ is clearly upper bounded by the probability that $I_{X_1}$ outputs a $1$, which is equal to $1 - \Pr[I_{X_1} = 0]$. $I_{X_1}$ outputs a $0$ if and only if two vertices of $X_1$ lie in the same partition of the random negative test, and this happens with probability $$ \frac{\binom{|X_i|}{2}}{k-1} \leq \frac{\binom{l}{2}}{k-1} $$ Hence, the number of errors made on negative tests is lower bounded as claimed in the lemma. \end{proof} \subsection{Each gate makes few errors on positive tests} \begin{lemma} The number of positive tests on which $C'$ fails is at most $$ size(C)\cdot m^2\cdot \binom{n-l-1}{k-l-1} $$ \end{lemma} \begin{proof} We shall consider the errors introduced by the approximator at a single gate, and then apply the union bound to get the bound claimed. If $g = A \vee B$, then our construction for the approximator for $g$ involves taking a simple $\vee$ (which doesn't introduce any error) and then repeatedly plucking until we get down our number of clique indicators. The plucking operation replaces a larger clique indicator $I_{X_i}$ by $I_X$ with $X\subseteq X_i$ and hence will accept only more graphs and cannot make the approximator answer a $0$. Hence $A \sqcup B$ introduces no errors on positive tests. \\ Suppose $g = A\wedge B$, our first step was to replace $I_{X_i}\wedge I_{Y_j}$ by $I_{X_i \cup Y_j}$. These two functions behave the same on positive tests and hence won't introduce any errors. The second step was to drop indicators of size greater than $l$. Dropping such clique indicators may make the approximator err on those positive graphs that contain a clique on these $l+1$ or more places, and there are at most $\binom{n-l-1}{k-l-1}$ of them and there are at most $m^2$ clique indicators, giving us the bound claimed. \end{proof} \subsection{Each gate makes few errors on negative tests} \begin{lemma} The number of negative tests on which $C'$ fails is at most $$ size(C)\cdot m^2 \cdot \parn{\frac{\binom{l}{2}}{k-1}}^p \cdot (k-1)^n $$ \end{lemma} \begin{proof} Again, we shall analyse the errors introduced at each gate. If $g = A \vee B$ then the errors have to be introduced at the plucking operations. We need to consider the negative tests that are accepted after plucking which were rejected before. Pick the $(k-1)$-partition randomly among the $(k-1)^n$ partitions, and let $G$ be the resulting negative graph. For any sunflower $Z_1, \cdots, Z_p$, we estimate the probability that $I_{Z_i}$ outputs $0$ on $G$ whereas $I_Z$ outputs a $1$. \begin{eqnarray*} Pr\left[I_{Z} = 1 \wedge \parn{\bigvee I_{Z_i} = 0} \right] & \leq & \Pr\left[\bigvee I_{Z_i} =0|I_Z = 1 \right]\\ & = & \prod_{i=1}^p \Pr\left[I_{Z_i}=0 | I_Z = 1\right]\\ & \leq & \prod \Pr[I_{Z_i}=0]\\ & \leq & \parn{\frac{\binom{l}{2}}{k-1}}^p \end{eqnarray*} The first line follows from the definition of conditional probability. The second line is true because the petals of the sunflower are disjoint and hence the probabilities are independent. The third is true because ``$Z_i$ is not a clique'' is less likely to happen given the fact that $Z$ is a clique\footnote{if this intuition is not clear, the reader should work out the easy details}. The fourth line follows because $Z_i$ is not a clique if and only if two vertices of it fall in the same partition. And since there are at most $m$ plucks, the desired bound follows if $g$ is an $\vee$ gate. \\ Suppose $g = A \wedge B$, the step where we replace $I_{X_i} \wedge I_{Y_j}$ by $I_{X_i \vee Y_j}$ does not cause any graph that was rejected before to be accepted now. The step of dropping large clique indicators also doesn't not cause additional negative graphs to be accepted. It's again the plucking process that creates the trouble, and that goes through the same analysis as given for the $\vee$ gate. And since there are at most $m^2$ packing's, the claimed bound is obtained. \end{proof} \subsection{Choosing parameters} If we choose $l = \floor{\sqrt{k}}$, $p = \ceil{\sqrt{k}\log n}$ and $m = (p-1)^l\cdot l!$, the lemmas would then show that $$ size(C) = n^{\Omega(\sqrt{k})} $$ The details are left to the reader. \end{document}