BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Communication Complexity Meets Combinatorial Optimization
DTSTART:20220714T100000
DTEND:20220714T120000
DTSTAMP:20260429T043218Z
UID:af8f17dfc689e1fffa9e6c4a23bc093fd7d5333dcb3786c3972187d6
CATEGORIES:Conferences - Seminars
DESCRIPTION:Weiqiang Yuan\nEDIC candidacy exam\nExam president: Prof. Frie
 drich Eisenbrand\nThesis advisor: Prof. Mika Göös\nThesis co-advisor: Pr
 of. Ola Svensson\nCo-examiner: Prof. Michael Kapralov\n\nAbstract\nExtensi
 on complexity is an active direction in theoretical computer science that 
 studies the power of linear programming. In this write-up\, I will first s
 ummarize the history of extension complexity\, with a focus on the develop
 ments 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 t
 he TSP polytope has exponential extension complexity. The second paper pro
 ves almost tight lower bounds on extension complexity of approximating MAX
 -CUT and MAX-3SAT. The proof relies on a novel query-to-communication lift
 ing theorem. The third paper\, on the other hand\, gives an upper bound. I
 t exhibits an extended formulation of polynomial size for every regular ma
 troid. Finally\, I will discuss some frontier problems in this field.\n\nB
 ackground \n\n	Linear vs. semidefinite extended formulations: exponential 
 separation and strong lower bounds\, STOC 2012\, by Samuel Fiorini\, Ser
 ge Massar\, Sebastian Pokutta\, Hans Raj Tiwary\, Ronald de Wolf (https
 ://dl.acm.org/doi/10.1145/2213977.2213988)\n	Approximating rectangles by j
 untas and weakly-exponential lower bounds for LP relaxations of CSPs\, STO
 C 2017\, by Pravesh K. Kothari\, Raghu Meka\, Prasad Raghavendra (http
 s://dl.acm.org/doi/10.1145/3055399.3055438)\n	Regular matroids have polyno
 mial extension complexity\, Mathematics of Operation Research\, by Manuel
  Aprile\, Samuel Fiorini (https://arxiv.org/abs/1909.08539#:~:text=We%20p
 rove%20that%20the%20extension\,O(n%5E6).)\n
LOCATION:BC 233 https://plan.epfl.ch/?room==BC%20233
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR