Communication Complexity Meets Combinatorial Optimization
Event details
| Date | 14.07.2022 |
| Hour | 10:00 › 12:00 |
| Speaker | Weiqiang Yuan |
| Location | |
| Category | Conferences - Seminars |
EDIC candidacy exam
Exam president: Prof. Friedrich Eisenbrand
Thesis advisor: Prof. Mika Göös
Thesis co-advisor: Prof. Ola Svensson
Co-examiner: Prof. Michael Kapralov
Abstract
Extension complexity is an active direction in theoretical computer science that studies the power of linear programming. In this write-up, I will first summarize the history of extension complexity, with a focus on the developments in the past 10 years. Afterwards, I will talk about three relevant papers. The first paper solves a 20-year-old open problem. It shows that the TSP polytope has exponential extension complexity. The second paper proves almost tight lower bounds on extension complexity of approximating MAX-CUT and MAX-3SAT. The proof relies on a novel query-to-communication lifting theorem. The third paper, on the other hand, gives an upper bound. It exhibits an extended formulation of polynomial size for every regular matroid. Finally, I will discuss some frontier problems in this field.
Background
Exam president: Prof. Friedrich Eisenbrand
Thesis advisor: Prof. Mika Göös
Thesis co-advisor: Prof. Ola Svensson
Co-examiner: Prof. Michael Kapralov
Abstract
Extension complexity is an active direction in theoretical computer science that studies the power of linear programming. In this write-up, I will first summarize the history of extension complexity, with a focus on the developments in the past 10 years. Afterwards, I will talk about three relevant papers. The first paper solves a 20-year-old open problem. It shows that the TSP polytope has exponential extension complexity. The second paper proves almost tight lower bounds on extension complexity of approximating MAX-CUT and MAX-3SAT. The proof relies on a novel query-to-communication lifting theorem. The third paper, on the other hand, gives an upper bound. It exhibits an extended formulation of polynomial size for every regular matroid. Finally, I will discuss some frontier problems in this field.
Background
- Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds, STOC 2012, by Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf (https://dl.acm.org/doi/10.1145/2213977.2213988)
- Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs, STOC 2017, by Pravesh K. Kothari, Raghu Meka, Prasad Raghavendra (https://dl.acm.org/doi/10.1145/3055399.3055438)
- Regular matroids have polynomial extension complexity, Mathematics of Operation Research, by Manuel Aprile, Samuel Fiorini (https://arxiv.org/abs/1909.08539#:~:text=We%20prove%20that%20the%20extension,O(n%5E6).)
Practical information
- General public
- Free