Theory Club

**Theory club** is an
event for theory students to meet regularly and talk about
research. The event has two parts: a social part (with
**snacks provided!**) and a short board
presentation. The topics of each presentation will be broad
and the presentations are designed to be accessible to all
theory students: no prior knowledge is assumed.

** Due to the Coronavirus pandemic, theory club is canceled for the foreseeable future.**

Q: When/where is theory club?

A: Tuesday, 4:30-5:30 (usually) in 6501 GHC.

Q: Who is the event for?

A: All theory students! (And occasionally some faculty, too.)

If you would like to receive notifications for our events, you can sign up for our mailing list.

**Please answer the theory club poll here!** (to pick topics and snacks)

Spring 2020 Schedule

Topic 1: Sum of Squares

February 11, 2020 (GHC 6501)

Does Sum of Squares know about chromatic number?

Speaker: Pravesh Kothari

**Abstract**: I'll talk about a class of questions (most
of them widely open) that ask whether "simple" proof
systems such as sum of squares can estimate about basic
combinatorial properties of graphs.

February 18, 2020 (GHC 6501)

Algorithmic Applications of Sum-of-Squares

Speaker: Ainesh Bakshi

**Abstract**: I will briefly discuss
recent progress in robust statistics, including
applications where low-degree sum-of-squares relaxations
are strictly better than any known (spectral)
algorithms.

February 25, 2020 (GHC 6501)

Rounding Sum-of-Squares Relaxations

Speaker: Andrii Riazanov

**Abstract**: I will outline a common
structure that several Sum-of-Squares -based algorithms
follow, taking as an example the algorithm for the
Planted Sparse Vector problem.

March 3, 2020 (GHC 6501)

Open house - socializing with accepted students

March 10, 2020

Spring break - No theory club

Topic 2: Online Algorithms

March 17-???, 2020

Canceled due to the Covid-19 pandemic.