18.434: Seminar in Theoretical Computer Science

Spring 2016

Monday, Wednesday, Friday 10:00am - 11:00am, 2-151


This is an undergraduate seminar in theoretical computer science. It carries CIM credit for the math department. As with all CIM subjects, the emphasis is on communication, both oral and written. Enrollment is limited by the department.

In this spring, we will cover various mathematical topics in theoretical computer science, with a focus on approximation algorithms.

Announcements Course Information
Date(s) Topic Presenter(s) Notes
Wed Feb 3 Introduction, choosing topics Yuan Zhou
Fri Feb 5
Mon Feb 8
Central Limit Theorem and Chernoff bounds Yuan Zhou Notes-Yuan
Wed Feb 10
Fri Feb 12
Spectral Graph Theory I Chris & Emanuele Notes-Chris
Tue Feb 16
Wed Feb 17
Spectral Graph Theory II Paul & Vinay Notes-Vinay
Fri Feb 19
Mon Feb 22
Fields and polynomials Evan & Rishad Notes-Rishad
Wed Feb 24
Fri Feb 26
Error correcting codes Simon & Lawrence Notes-Simon
Mon Feb 29
Wed Mar 2
Derandomization Yuan Notes-Yuan
Fri Mar 4
Mon Mar 7
Expanders David & Logan Notes-Logan
Wed Mar 9
Fri Mar 11
Mon Mar 14
Communication complexity and information theory Vinay & Victor Notes(on CC)-Victor
Notes(on information theory)-Vinay
Notes(on Shannon's theorem)-Vinay
Wed Mar 16
Fri Mar 18
Mon Mar 28
Linear and semidefinite programming Ming Yang & Brian Notes(on LP)-Ming
Notes(on SDP)-Brian
Notes(on Solvers)-Brian
Wed Mar 30
Fri Apr 1
LP and SDP relaxations and approximation algorithms Yuan & Ming Yang Notes-Yuan
Mon Apr 4
Wed Apr 6
Constraint Satisfation Problems Logan & Victor Notes-Victor
Fri Apr 8
Mon Apr 11
Treewidth Gerrod Notes-Gerrod
Wed Apr 13
Fri Apr 15
Analysis of Boolean functions David & Paul Notes-Paul
Wed Apr 20
Fri Apr 22
LP (and SDP) hierarchies Emanuele & Chris Notes-Emanuele
Mon Apr 25
Wed Apr 27
Rounding hierarchies Yuan Notes-Yuan
Fri Apr 29
Mon May 2
Wed May 4
Hardness of approximation I Rishad & Evan Notes-Rishad
Fri May 6
Mon May 9
Hardness of approximation II Simon & Yuan Notes-Simon
Wed May 11 TBD


The topics listed with a star (*) will span 3 45-minute sessions, while the rest will span 2 sessions.