How Do Exponential Size Solutions Arise in Semidefinite Programming?

Explore the prevalence and implications of exponential size solutions in semidefinite programming (SDP) through this 50-minute lecture by Gabor Pataki from UNC Chapel Hill. Delve into Khachiyan's classic example demonstrating SDPs with solutions requiring an exponential number of bits to describe. Examine the impact of these large solutions on the long-standing open problem of determining SDP feasibility in polynomial time. Challenge the common belief that large solutions in SDPs are rare by learning how a linear change of variables can transform any strictly feasible SDP into a Khachiyan-type problem with large leading variables. Investigate the relationship between solution size and the singularity degree of dual problems. Discover naturally occurring SDPs with large solutions and gain insights into representing these solutions in polynomial space.