I try to understand the $n^{1-\epsilon}$ hardness of approximating clique for any $\epsilon$ provided in [1]: www.nada.kth.se/~johanh/cliqueinap.ps
In fact, I only want to understand the proof of theorem 2.8 (page 10) of [1], which in fact is due to [7]: https://www.cs.utexas.edu/users/diz/pubs/approx.ps.
Theorem 2.8 (proved in [7]) says: Suppose any language in NP admits a PCP with log random bit and f amortized free bits, then unless NP=ZPP for any $\epsilon$ max clique cannot be approximated within $n^{\frac{1}{1+f+\epsilon}}$
As [1] proves that "for any $f > 0$, there exists PCP verifier (for a L in NP) with f amoritzed free bits", I understand that the result follows immediatly.
To prove theorem 2.8, I want to be sure that I correctly understand the hypothesis, and hence my first question.
1) We are given "a PCP verifier with $f$ amortized free bits". I know that $f$ amoritzed free bits implies that the number of free bits is at most $f log(\frac{1}{s})$, where $s$ is the soundess of the verifier. Thus, is it correct to say that "there exists $s>0$ such that we are given a PCP verifier with soundess $s$ and that uses $f log(\frac{1}{s}))$ free bits ? (i.e. we do not control the soundness and the number of free bits, but only the relation between these two numbers)
2) If this is true, how can we adapt the Lemma 2.11 of [7]? Indeed, in Lemma 2.11, the verifier reads $c$ bits and has a soundess 1/2. I understand that I can replace $c$ by $f log(\frac{1}{s}))$ in the number of vertices of the created graph, but how can we adapt the disperser to handle the soundess s ?
Thank you very much for your answer.
Best regards
