Theory Reading Group

Fall 2006 Schedule

Date Information
Friday, December 15 2006 Topic:Circuit lower bounds for approximate majority.
Links:On Probabilistic Time versus Alternating Time by Emanuele Viola.
Presenter:Scott Diehl.
1:00pm, 4331 CS.
Thursday, December 7 2006 Topic:Space hierarchies for semantic models.
Presenter:Jeff Kinne.
3:00pm, 4310 CS.
Thursday, November 9 2006 Paper(s): Algorithms for matching and matroid problems by Nick Harvey.
3:00pm, 4310 CS.
Thursday, November 2 2006 Paper(s): Same as last week -
A random polynomial time algorithm for approximating the volume of convex sets, Journal of the ACM, 1991, by Dyer, Frieze, and Kannan;
Random walks and an O(n^5) time algorithm for volumes of convex sets, Random Structures and Algorithms, 1997, by Kannan, Lovasz, and Simonovits.
11:30am, 4331 CS.
Thursday, October 26 2006 Paper(s): A random polynomial time algorithm for approximating the volume of convex sets, Journal of the ACM, 1991, by Dyer, Frieze, and Kannan;
Random walks and an O(n^5) time algorithm for volumes of convex sets, Random Structures and Algorithms, 1997, by Kannan, Lovasz, and Simonovits.
11:30am, 4331 CS.
Thursday, October 19 2006 Paper:"Derandomizing homomorphism testing in general groups",2004 STOC, pp 427-435, by Amir Shpilk and Avi Wigderson.
Link:PDF
3:00pm, 4331 CS.
Thursday, October 12 2006 Topic: "Show and tell"
Links:
Presenter: "All who attend".
11:30am, 4331 CS.
Thursday, September 28 2006 Topic: Quantum Zero Knowledge Proof Systems
Links:
Presenter: Bess Berg.
11:30am, 4331 CS.
Thursday, September 21 2006 Topic: Space hierarchies for semantic models
Links: A Generic Time Hierarchy for Semantic Models with One Bit of Advice by D. van Melkebeek and K. Pervyshev.
Presenter: Jeff Kinne.
11:30am, 4331 CS.