Alex Touzov places second

June 3, 2021

Ph.D. student Alex Touzov won a second prize in the poster session at the 2021 Mixed Integer Programming Workshop for ‘How do exponential size solutions arise in semidefinite programming?” from his joint work with Dr. Gabor Pataki.

According to the citation,  “Aleksandr’s poster contributes to our fundamental understanding of semidefinite programs (SDPs). It shows that any strictly feasible SDP can be converted into a special form with exponentially-large solutions (in terms of the size of the input) via a change of basis, thereby demonstrating that numerically challenging models are not too rare in theory. Moreover, though the solutions for SDPs in this special form are of exponential size, the poster shows how to certify their existence in polynomial space. The poster makes significant progress in addressing the open question “Can we decide feasibility of SDPs in polynomial time?”, among other applications.”

If you would like to see the poster itself, it is here: https://gaborpataki.web.unc.edu/wp-content/uploads/sites/14119/2021/05/MIP-poster.pdf

and the paper is here: https://arxiv.org/abs/2103.00041
 

Congratulations Alex!