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. |