日時: 2015年6月22日（月） 17：00–18：30
場所: 東京大学 工学部6号館3階 セミナー室 A/D
http://www.u-tokyo.ac.jp/campusmap/cam01_04_07_j.html
講演者: Sebastian Pokutta
(Georgia Institute of Technology, School of Industrial and Systems Engineering (ISyE) )
題目: The Expressive Power of Linear and Semidefinite Programs
Abstract:
Linear and semidefinite programming are two core optimization paradigms with many important applications in engineering and business. However, the expressive power of these modeling paradigms is only partially understood so far and extended formulations are a powerful and natural tool to analyze the possibilities and limitations of linear and semidefinite programming formulations.
In this talk I will provide an overview of recent breakthrough results in extended formulations, both in the linear and the semidefinite setting, lay out frameworks for establishing lower bounds including techniques from communication complexity and information theory, as well as discuss constructions. I will then explain reduction mechanisms between problems in the context of LPs and SDPs, which allow to establish strong inapproximability results for various problems.