  We design new polynomial-time algorithms for recovering planted cliques in
the semi-random graph model introduced by Feige and Kilian 2001. The previous
best algorithms for this model succeed if the planted clique has size at least
$n^{2/3}$ in a graph with $n$ vertices (Mehta, Mckenzie, Trevisan 2019 and
Charikar, Steinhardt, Valiant 2017). Our algorithms work for planted-clique
sizes approaching $n^{1/2}$ -- the information-theoretic threshold in the
semi-random model (Steinhardt 2017) and a conjectured computational threshold
even in the easier fully-random model. This result comes close to resolving
open questions by Feige 2019 and Steinhardt 2017.
  Our algorithms are based on higher constant degree sum-of-squares relaxation
and rely on a new conceptual connection that translates certificates of upper
bounds on biclique numbers in unbalanced bipartite Erd\H{o}s--R\'enyi random
graphs into algorithms for semi-random planted clique. The use of a
higher-constant degree sum-of-squares is essential in our setting: we prove a
lower bound on the basic SDP for certifying bicliques that shows that the basic
SDP cannot succeed for planted cliques of size $k =o(n^{2/3})$. We also provide
some evidence that the information-computation trade-off of our current
algorithms may be inherent by proving an average-case lower bound for
unbalanced bicliques in the low-degree-polynomials model.
