The PLAN
Date | Title | Speakers |
---|---|---|
Oct 1 2014 | Hastad’s 3-bit PCP | Abbas |
Oct 15 | (In-)approximability of CSPs under UGC | Christos |
Oct 22 | Hardness of MAXCUT under UGC | Abbas |
Oct 29 |
(In-)approximability of CSPs under UGC contd., Approximation resistance from pairwise independence (Austrin-Mossel) |
Christos, Chidambaram |
Nov 5 | Approximation resistance from pairwise independent subgroups (Chan) | Chidambaram |
Nov 12 | Invariance principles and isoperimetry | Nisheeth |
Nov 19 | SDP integrality gaps from UGC hardness | Nisheeth |
Dec 3 | Extension complexity lower bounds for the correlation polytope | Christos |
Mar 25 2015 | MAXCUT integrality gaps for Sherali-Adams | Christos |
Apr 1 | Approximate Constraint Satisfaction Requires Large LP Relxations | Chidambaram |
When and Where:
The talks are usually scheduled on Wednesday afternoons. The venue could be any one of the following: MA B1 524 or INJ 114 or INF 211.
How to register for talk announcements:
If you are interested in hearing/contributing talks about lower bound results in computer science then register for this group by searching for “lower” in groups.epfl.ch (the group is titled lower-bounds-reading-group).
Note for speakers:
Talks must be made accessible and understandable to a wide audience within TCS. Some papers involve many technical details. The job of a good speaker is to correctly judge which ones to show and which ones to hide during a talk. The goal is to make it easy for the audience to read the papers on their own after the talk.