Tardos Function Counterexample to Blum's $P\neq NP$ Claim In this thread, Norbet Blum's attempted $P \neq NP$ proof is succinctly disproved by noting that the Tardos function is a counterexample to Theorem 6.

Theorem 6: Let $f \in \mathcal{B}_n$ be any monotone Boolean function. Assume that there is a CNF-DNF-approximator $\mathcal{A}$ which can be used to prove a lower bound for $C_m(f)$. Then $\mathcal{A}$ can also be used to prove the same lower bound for $C_{st}(f)$.

Here's my problem: the Tardos function is not a Boolean function, so how does it satisfy the hypotheses of Theorem 6?

In this paper, they discuss the complexity of the function $\varphi(X) \leq f(v)$, which is not in general a monotone Boolean function, since increasing edges can make $\varphi(X)$ larger to make $\varphi(X) \leq f(v)$ false when it was true with fewer $1$'s in the input. The function $\varphi(X) \geq f(v)$ does not, in general, compute $1$ on $T_1$ and $0$ on $T_0$.

In fact, the test sets $T_1$ and $T_0$ are chosen precisely so that computing $1$ on $T_1$ and $0$ on $T_0$ with monotonicity means your function in precisely computing CLIQUE (they define the boundary of the $1$'s and $0$'s in the lattice of inputs), so these remarks imply that the Tardos function is the same as CLIQUE, which is clearly not true.

Yet, so many people -- and such knowledgeable people -- claim that the Tardos function provides an immediate counterexample, so there must be something I'm missing. Could you please provide a detailed explanation or proof for those of us who are interested parties but not quite on your level?
so these remarks imply that the Tardos function $f$ is the same as
  CLIQUE.


Short answer - NO. 

It is only a monotone "clique-like": accepts all $k$-cliques, and rejects all  complete $(k-1)$-partite graphs. It can, however, accept some graphs rejected by CLIQUE: graphs $G$ with $\omega(G) &lt; k$ but $\chi(G)\geq k$ (so-called "non-perfect" graphs). The paper by Grötschel,
Lovász and Schrijver implies that $f$ has a non-monotone circuit of polynomial size. But, according to Theorem 6 in the "proof", any monotone clique-like Boolean function requires non-monotone circuits of super-polynomial size. 
So, one of these two papers must be wrong. The GLS-1981 paper stood for already > 35 years  ...

What Tardos does is the following. She starts from the graph function $\varphi(G):=\vartheta(\overline{G})$, where $\vartheta$ is the famous Lovász' theta-function. The fundamental fact is that the number
$\varphi(G)$ is sandwiched between the clique number and the chromatic number: $\omega(G)\leq \varphi(G)\leq \chi(G)$. 
She then uses the fact that $\vartheta(G)$ can be approximated in polynomial time. Based on this, she defines a graph-function $\phi(G)$ with the following properties:


 Values of $\phi(G)$ can be computed in polynomial time (in the number $n$ of vertices).
 $\phi$ is monotone: adding edges can only increase its value.
 $\omega(G)\leq \phi(G)\leq \chi(G)$ holds for all graphs $G$.


Then (as Clement C. notes) she defines the desired monotone Boolean function $f$ as: $f(G)=1$ iff $\phi(G)\geq k$. By (1), the function has a (non-monotone) circuit of polynomial size. By (2), $f$ is a monotone Boolean function. By (3), 
$f$ accepts all $k$-cliques, and rejects all complete $(k-1)$-partite graphs.

See here for technical details.