Title: Explicit construction of RIP matrices is Ramsey-hard,
Abstract: Matrices $\Phi\in\R^{n\times p}$ satisfying the Restricted Isometry Property
(RIP) are an important ingredient of the compressive sensing methods. While it
is known that random matrices satisfy the RIP with high probability even for
$n=\log^{O(1)}p$, the explicit construction of such matrices defied the
repeated efforts, and the most known approaches hit the so-called $\sqrt{n}$
sparsity bottleneck. The notable exception is the work by Bourgain et al
\cite{bourgain2011explicit} constructing an $n\times p$ RIP matrix with
sparsity $s=\Theta(n^{{1\over 2}+\epsilon})$, but in the regime
$n=\Omega(p^{1-\delta})$.
In this short note we resolve this open question in a sense by showing that
an explicit construction of a matrix satisfying the RIP in the regime
$n=O(\log^2 p)$ and $s=\Theta(n^{1\over 2})$ implies an explicit construction
of a three-colored Ramsey graph on $p$ nodes with clique sizes bounded by
$O(\log^2 p)$ -- a question in the extremal combinatorics which has been open
for decades.