Reading Group : Spring 2008 February 1, 2008 Danupon Nanongkai Paper: Balloon popping with applications to ascending auctions. [pdf] February 8, 2008 Subrahmanyam Kalyanasundaram Introduction to Expanders February 22, 2008 Shiva Kintali Paper: Interdomain routing and games. [pdf] February 29, 2008 Chandrasekar Karthekeyan Applications: - Error reduction of RP algorithms with reduced number of bits - PRGs to cheat space bound distinguishers Additional Notes March 28, 2008 April 4, 2008 Danupon Nanongkai April 11, 2008 April 18, 2004 Reading Group : Fall 2007 September 28, 2007 Experts Method - Deeparnab Chakrabarty Paper: The Multiplicative Weights Update Method: A Meta-Algorithm and Applications. Sanjeev Arora, Elad Hazan and Satyen Kale. [pdf] [ps] October 12, 2007 Cyrptography in NC0 - Akshay Wadia Paper: Cryptography in NC0. Benny Applebaum, Yuval Ishai and Eyal Kushilevitz. [ps] October 26, 2007 Subrahmanyam Kalyanasundaram Paper: Finding disjoint paths in expanders deterministically and online. Noga Alon and Michael Capalbo. [pdf] November 2, 2007 Learning Boolean Functions - Varun Kanade Papers: Learning Boolean Functions via the Fourier Transform. Yishay Mansour. [ps] Learning Decision Trees using the Fourier Specturm. Eyal Kushilevitz and Yishay Mansour. [pdf] [ps] November 9, 2007 Natural Proofs - Tejas Iyer Paper: Natural Proofs. Alexander A. Razborov and Steven Rudich. [pdf] [ps] November 16, 2007 Agnostic Learning - Justin Cranshaw Paper: Towards Efficient Agnostic Learning. Michael Kearns, Robert Schapire and Linda Sellie. [pdf] [ps]