I'm trying to reconstruct the proof using matrix counting that there exists two subsets $A,B$ of $\{1,\cdots,N\}$ with $\#A=\#B$ such that for any $a\in A$ and $b\in B$, $a+b$ is prime, and $\#A=\#B$ is of order $\log(N)$. I know the general ideal but I'm having trouble with some of the details. We form an $N\times N$ matrix $P$ where the entry $(i,j)$ is 1 if $i+j$ is prime and 0 otherwise. We want to find a $k\times k$ minor of $P$ consisting entirely of 1s, where $k$ is of order $\log(N)$. We know that there are at least $\frac{CN^2}{\log(N)}$ 1 entries in the matrix using a crude estimate. For a prime $p\leq N$, there are $p-1$ ways to write $p$ as a sum, so we have a crude lower bound $\sum\_{p\leq N}(p-1)$, which is bounded from below by $\frac{CN^2}{\log(N)}$ by the prime number theorem. So there are at least $\frac{CN^2}{\log(N)}$ 1 entries in $P$. 


Now suppose that $k$ is sufficiently large so that every single $k\times k$ minor of $P$ contains at least one zero. We already know that there are approximately $2(N/2)^2=N^2/2$ zeroes in $P$ (just by removing all pairs $(i,j)$ with the same parity). So consider the subarray $P\_{OE}$ consisting of all pairs $(i,j)$ with $i$ odd and $j$ even, and $P\_{EO}$ the subarray consisting of all pairs $(i,j)$ with $i$ even and $j$ odd. $P$ is symmetric so $P\_{EO}$ is the transpose of $P\_{OE}$. If every $k\times k$ minor of $P\_{OE}$ contains a zero, there must be quite a large number of zero entries in the array $P\_{OE}$. $P\_{OE}$ has size (approximately) $\frac{N}{2}\times\frac{N}{2}$. So we want to find some number $F\_k$ with the property that any family of ordered pairs intersecting every $k\times k$ minor of $\{(i,j): 1\leq i,j\leq N/2\}$ has at least size $F\_k$. Then there at least $2F\_k$ more zero entries in $P$ in addition to the ones from same parity pairs (since $P\_{EO}$ has the same number of zero entries as $P\_{OE}$). 


In that case, then the number of 1 entries in $P$ is at most $N^2-\frac{N^2}{2}-2F\_k$. We can then (hopefully) rearrange this to get a lower bound on $k$, so that if $k$ is below that bound, there is a $k\times k$ minor of only 1s. So we want the bound to be order $\log(N)$. This number $F\_k$ is the smallest number of zeroes we can put down in $P\_{OE}$ to ruin every $k\times k$ minor. I'm struggling to find a good enough $F\_k$. A fairly easy argument shows that $F\_k$ is at least $\frac{N}{2k}\left(\frac{N}{2}-k\right)$. To see this, let $X$ be a set intersecting every $k\times k$ minor. Just pick $k$ rows out of $\frac{N}{2}$. Then among these $k$ rows, there must be at least $\frac{N}{2}-(k-1)$ elements of $X$, otherwise we could find $k$ columns missed by $X$. Then we cut the row space up into approximately $\frac{N}{2k}$ pairwise disjoint collections of $k$ rows. So $\#X$ must be at least (approximately) $\frac{N}{2k}(\frac{N}{2}-k)$. 


This result in the following approximation


$$\frac{C\log(N)}{N^2}\leq N^2-\frac{N^2}{2}-\frac{N}{2k}\left(\frac{N}{2}-k\right)$$


You can multiply through by $k$ and get a lower bound for $k$ but it doesn't seem to be good enough. The bound is only $O(1)$, and it should be $O(\log(N))$. Is there a better bound we can get on $F\_k$? I tried to use some kind of sieving argument but I couldn't really make it work. 



Finding a sufficiently large complete bipartite subgraph using matrix counting
This is essentially the [Zarankiewicz problem](http://en.wikipedia.org/wiki/Zarankiewicz_problem), a well known and hard problem in extremal combinatorics.


There is an upper bound to the quantity you call $F\_k$, given by the Kővári–Sós–Turán theorem mentioned in the Wikipedia article. Fortunately, this is enough to conclude that you can take your original sets with $|A|=|B|$ about $\log n$.


