Welcome to the Theory Reading Group at Dartmouth's CS Department! We have vigorous, exciting discussions/presentations on recent research in theoretical computer science (TCS), accompanied by choice snacks. We meet on Tuesdays 4:00-5:15 in Sudikoff 114. Everyone is welcome; email "ac" at "cs" if you'd like to join the discussion. Each term we center our discussions around a well-defined theme within TCS. For the current term (Spring 2006) the theme is "Fourier analysis and its applications in TCS".
Spring 2006 Schedule
Apr 18, 2006 (Amit) — special meeting time 3:30-4:30
- Amit will introduce Fourier transforms over arbitrary Abelian groups (in particular, discrete Fourier transforms). We will see an example of how to compute Fourier coefficients for a simple but important class of Boolean functions.
Apr 25, 2006 (Amit)
- Amit will discuss the concept of influence of variables on a Boolean function. We will see the proof of a classic theorem of Kahn, Kalai and Linial about such influences. Here is the original paper and here is Stefankovic's Masters thesis, which we shall use as our source for the proof.
May 2, 2006 (Joshua)
- Joshua will present a proof of Beckner's inequalities, which were used last time in the proof of the Kahn-Kalai-Linial theorem.
May 9, 2006 (Anna)
- Anna will start discussing Hastad's landmark paper Some Optimal Inapproximability Results. The discussion for this week will focus on the problem of linear equations mod 2.
May 16, 2006 (Anna)
- Anna will continue presenting Hastad's paper, and the result on the inapproximability of max linear equations mod 2.
May 23, 2006 (Joshua)
- Joshua will continue presenting Hastad's paper. We shall probably focus on MAX-3SAT.
Theory Reading Group | theory@cs.dartmouth.edu | Last updated Mon Apr 17 12:51:16 EDT 2006.
Page maintained by Amit Chakrabarti.
Earlier terms: [ Winter 2006 | Fall 2005 ]