  Template-based synthesis, also known as sketching, is a localized approach to
program synthesis in which the programmer provides not only a specification,
but also a high-level ``sketch'' of the program. The sketch is basically a
partial program that models the general intuition of the programmer, while
leaving the low-level details as unimplemented ``holes''. The role of the
synthesis engine is then to fill in these holes such that the completed program
satisfies the desired specification. In this work, we focus on template-based
synthesis of polynomial imperative programs with real variables,
i.e.~imperative programs in which all expressions appearing in assignments,
conditions and guards are polynomials over program variables. While this
problem can be solved in a sound and complete manner by a reduction to the
first-order theory of the reals, the resulting formulas will contain a
quantifier alternation and are extremely hard for modern SMT solvers, even when
considering toy programs with a handful of lines. Moreover, the classical
algorithms for quantifier elimination are notoriously unscalable and not at all
applicable to this use-case.
  In contrast, our main contribution is an algorithm, based on several
well-known theorems in polyhedral and real algebraic geometry, namely Putinar's
Positivstellensatz, the Real Nullstellensatz, Handelman's Theorem and Farkas'
Lemma, which sidesteps the quantifier elimination difficulty and reduces the
problem directly to Quadratic Programming (QP). Alternatively, one can view our
algorithm as an efficient way of eliminating quantifiers in the particular
formulas that appear in the synthesis problem. The resulting QP instances can
then be handled quite easily by SMT solvers. Notably, our reduction to QP is
sound and semi-complete, i.e.~it is complete if polynomials of a sufficiently
high degree are used in the templates...
