**Accuracy certificates for computational problems with convex structure**

*Arkadi** Nemirovski,
Shmuel Onn and Uriel G. Rothblum*

The goal of the current paper is to
introduce the notion

of certificates which verify the
accuracy of solutions of

computational problems with convex structure;
such problems

include minimizing convex functions, variational inequalities with

monotone operators, computing saddle points
of convex-concave

functions and solving convex Nash equilibrium
problems. We

demonstrate how the implementation of the
Ellipsoid method and

other cutting plane algorithms can be
augmented with the

computation of such certificates without
essential increase of the

computational effort. Further, we show that
(computable)

certificates exist whenever an
algorithm is {capable} to produce

solutions of guaranteed accuracy.