Theory Seminar
2002-2003
Academic Year
September 9, 2002 | Theory of Computing Seminar
Provably Fast Training Algorithms for Support Vector Machines Osamu Watanabe, Tokyo Institute of Technology, Japan |
September 23, 2002 | Theory of Computing Seminar
Steganography: Undercover Cryptography Nicholas Hopper, Carnegie Mellon University |
September 30, 2002 | Theory of Computing Seminar
Some geometric descriptions of an expander construction Jin-Yi Cai, University of Wisconsin - Madison |
October 7, 2002 | Theory of Computing Seminar
Power from Random Strings Dieter van Melkebeek, University of Wisconsin - Madison |
October 14, 2002 | Theory of Computing Seminar
Time-Space Tradeoff in Derandomizing Probabilistic Logarithmic Space Venkat Chakaravarthy, University of Wisconsin - Madison |
November 4, 2002 | Theory of Computing Seminar
Bounds for the Expected Duration of the Monopolist Game Eric Bach, University of Wisconsin - Madison |
November 11, 2002 | Theory of Computing Seminar
Random sub-problems of a given problem Ravi Kannan, Yale University |
December 9, 2002 | Theory of Computing Seminar
Holographic Proofs and Derandomization Rahul Santhanam, University of Chicago |
February 3, 2003 | Theory of Computing Seminar
On Proving Circuit Lower bounds Against PH: Positive and Negative Results Jin-Yi Cai 2:00pm, CS 2310 |
February 10, 2003 | Theory of Computing Seminar
Nonmonotonicity in Geometric Searching Bernard Chazelle 4:00pm, CS 1325 |
February 17, 2003 | Theory of Computing Seminar
Time-Space Lower Bounds for NP-Complete Problems - Part I Dieter van Melkebeek 2:10pm, CS 2310 |
February 19, 2003 | Theory of Computing Seminar
The Structure of Information Networks Jon Kleinberg 4:00pm, CS 1325 |
February 24, 2003 | Theory of Computing Seminar
Time-Space Lower Bounds for NP-Complete Problems - Part II Dieter van Melkebeek 2:10pm, CS 2310 |
March 6, 2003 | Theory of Computing Seminar
Selfish Routing and the Price of Anarchy Tim Roughgarden 4:00pm, CS 1221 |
March 10, 2003 | Theory of Computing Seminar
On designing seeds for similarity search in genomic DNA Uri Keich 2:25pm, B135 Van Vleck |
March 13, 2003 | Theory of Computing Seminar
Efficiency and Simplicity via Randomness Adam Kalai 4:00pm, CS 1221 |
March 31, 2003 | Theory of Computing Seminar
Gossip and Information flow in Networks David Kempe 4:00pm, TBA |
April 14, 2003 | Theory of Computing Seminar
Random Access to Advice Strings and Collapsing Results Jin-Yi Cai 2:00pm, CS 2310 |
April 25, 2003 | Theory of Computing Seminar
A shortest path algorithm for real-weighted graphs Seth Pettie 10:00am, CS 2310 |
May 1, 2003 | Theory of Computing Seminar
Fighting Spam May Be Easier Thank You Think Cynthia Dwork 4:00am, CS 1325 |
May 8, 2003 | Theory of Computing Seminar
Randomness and Dimension Jack Lutz 11:00am, CS 2310 |
May 12, 2003 | Theory of Computing Seminar
Analysis of a Randomized Selection Algorithm Mark Ward 1:00am, CS 2310 |
May 12, 2003 | Theory of Computing Seminar
A survey of some monotone complexity lower bounds Michael Roman 2:00am, CS 2310 |
June 3, 2003 | Theory of Computing Seminar
Arthur and Merlin take a walk Anne Condon 3:30am, CS 2310 |
August 13, 2003 | Theory of Computing Seminar
Certificates and the Learnability of DNF Formulas Lisa Hellerstein 2:30am, CS 2310 |