  As a classic example of Khachiyan shows, some semidefinite programs (SDPs)
have solutions whose size -- the number of bits necessary to describe them --
is exponential in the size of the input. Exponential size solutions are the
main obstacle to solve a long standing open problem: can we decide feasibility
of SDPs in polynomial time?
  We prove that large solutions are actually quite common in SDPs: a linear
change of variables transforms every strictly feasible SDP into a Khachiyan
type SDP, in which the leading variables are large. As to "how large", that
depends on the singularity degree of a dual problem. Further, we present some
SDPs in which large solutions appear naturally, without any change of
variables. We also partially answer the question: how do we represent such
large solutions in polynomial space?
