  Coin-flipping is a cryptographic task in which two physically separated,
mistrustful parties wish to generate a fair coin-flip by communicating with
each other. Chailloux and Kerenidis (2009) designed quantum protocols that
guarantee coin-flips with near optimal bias. The probability of any outcome in
these protocols is provably at most $1/\sqrt{2} + \delta$ for any given $\delta
> 0$. However, no explicit description of these protocols is known, and the
number of rounds in the protocols tends to infinity as $\delta$ goes to 0. In
fact, the smallest bias achieved by known explicit protocols is $1/4$
(Ambainis, 2001).
  We take a computational optimization approach, based mostly on convex
optimization, to the search for simple and explicit quantum strong
coin-flipping protocols. We present a search algorithm to identify protocols
with low bias within a natural class, protocols based on bit-commitment (Nayak
and Shor, 2003) restricting to commitment states used by Mochon (2005). An
analysis of the resulting protocols via semidefinite programs (SDPs) unveils a
simple structure. For example, we show that the SDPs reduce to second-order
cone programs. We devise novel cheating strategies in the protocol by
restricting the semidefinite programs and use the strategies to prune the
search.
  The techniques we develop enable a computational search for protocols given
by a mesh over the parameter space. The protocols have up to six rounds of
communication, with messages of varying dimension and include the best known
explicit protocol (with bias 1/4). We conduct two kinds of search: one for
protocols with bias below 0.2499, and one for protocols in the neighbourhood of
protocols with bias 1/4. Neither of these searches yields better bias. Based on
the mathematical ideas behind the search algorithm, we prove a lower bound on
the bias of a class of four-round protocols.
