The SQ argument in Balazs Szorenyi's paper
This is a standard adversary argument, not very different from adversary arguments taught in undergraduate algorithms courses. If you are unfamiliar with such arguments, then you can check out these notes by Jeff Erickson. 

The idea for the proof is that the SQ oracle is controlled by an adversary, and the adversary does not have to initially commit to a specific $f^*$. Instead, the adversary always makes sure that some $f^*$ is consistent with the oracle answers. In Szorenyi's paper, the adversary will make sure that there is always some $f_i$ which is consistent with all of the query answers. More precisely, let $\cal G$ be the set of all $f_i$ which are consistent with answering $0$ to all queries so far. If no queries have been answered yet, then $\mathcal{G} = \{f_1, \ldots, f_d\}$. Szorenyi shows that answering a new query by $0$ decreases $|\cal G|$ by at most $2d/(d\tau^2 - 1)$, so as long as $|\mathcal{G}| &gt; 2d / (d\tau^2-1)$, the adversary can keep answering queries by $0$ and $\cal G$ will remain non-empty. Moreover, while this is true, the algorithm cannot stop and output an answer, because any possible concept it outputs will have correlation less than $\tau$ with $|\mathcal{G}| - d / (d\tau^2-1)&gt; 0$ many concepts in $\mathcal{G}$. But any concept in $\mathcal{G}$ could be $f^*$, and the algorithm would output the wrong answer for at least one such possible $f^*$.

Another way to see the last point is the following. Suppose that the algorithm outputs something while $|\mathcal{G}| &gt; 2d / (d\tau^2-1)$. Then take an element of $\cal G$ that has correlation less than $\tau$ with the algorithm's output, and call it $f^*$. Rerun the whole process again with the oracle always outputting $0$: all the oracle answers are consistent with $f^*$ (by the construction of $\cal G$) and the algorithm would produce the same output, but that output would be incorrect for $f^*$. Note that this assumes that the algorithm is deterministic.

One detail he doesn't mention is that once $|\mathcal{G}| \le 2d / (d\tau^2-1)$, the adversary can pick some $f^* \in \mathcal{G}$ and answer new queries in any way consistent with $f^*$. This doesn't matter much in the proof because it can only happen once $(d\tau^2 - 1)/2$ queries have been made.