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
   
 
top of page