|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|
(In-)approximability of CSPs under UGC contd.,
Approximation resistance from pairwise independence (Austrin-Mossel)
|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.