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