Lower bounds reading group


Schedule of Past/Future Talks:
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.