Welcome to the Theory Reading Group at Dartmouth's CS Department! We have vigorous, exciting discussions/presentations on recent research in Theoretical CS, accompanied by choice snacks. We meet on Tuesdays 3:45-4:45 in Sudikoff 114. Everyone is welcome; email "theory" at "cs" if you'd like to join the discussion.

Fall 2005 Schedule

Sep 27, 2005 (Amit)

• The EQUALITY problem in communication complexity: two non-trivial protocols and their analyses.
  Partly based on the paper Communication Complexity in a 3-Computer Model, Andris Ambainis; Algorithmica 16 (3) : 298--301, 1996.

Oct 4, 2005 (Anna)

• Private Information Retrieval, Benny Chor, Oded Goldreich, Madhu Sudan; JACM 45 (6) : 965--982, 1998.

Oct 11, 2005 (Anna)

• We will continue to discuss the private information retrieval paper from last week. Please come with questions!

Oct 18, 2005 (Chittaranjan)

• Randomized simultaneous messages: solution of a problem of Yao in communication complexity, László Babai, Peter Kimmel; TR-2001-07, CS Dept, U. Chicago, 2001. The main result is a matching lower bound for the upper bound in the paper presented on Sep 27.

Oct 26, 2005 (Chittaranjan)

• We will continue the discussion of the Babai-Kimmel paper, led by Chittaranjan.

Nov 1, 2005 (Amit)

• Amit will wrap up the proof of the lower bound that we have been discussing during the previous two meetings.
  Useful link: A homework set from a course of Andrew Yao.

Nov 8, 2005 (Raz)

• Rajendra Magar will discuss a more advanced Private Information Retrieval from Upper bound on the communication complexity of private information retrieval , Andris Ambainis; ICALP 1997. This will be a follow-up to Anna's presentations.

Nov 15, 2005 (Raz)

• Raz will continue and conclude the previous week's reading.

No meeting on Nov 22, 2005; Thanksgiving break

Nov 29, 2005 (Amit)

• Wrap-up for this term (details TBA); discussion about future plans.