Caltech CS Theory Seminar: past talks

Regular time: 2:30 on Wednesdays

Regular venue: 287 Jorgensen

May 2006

• Wednesday, 5/31
      Leonard Schulman
  A partially ordered semigroup connected to the marriage theorem

January 2006

• Wednesday, 1/11
      Farzad Parvaresh
  On the algebraic list decoding of error-correcting codes

December 2005

• Wednesday, 12/7
      Kevin Ko
  

November 2005

• Wednesday, 11/30
      Chaitanya Swamy
  

• Wednesday, 11/16
      Lin Xiao
  

• Wednesday, 11/9
      Michael Langberg
  

• Wednesday, 11/2
      Shankar Kalyanaraman
  

October 2005

• Wednesday, 10/26
      Xiaojie Gao
  

• Wednesday, 10/19
      Nevin Kapur
  

• Wednesday, 10/12
      Chris Umans
  

• Wednesday, 10/5
      David Soloveichik
  

June 2005

• Thursday, 6/16
      Matt Cook
      Valiant's "Holographic Algorithms"

April 2005

• Wednesday, 4/19
      Michael Langberg (Moore 239, 3:00pm)
      Oblivious channels

March 2005

• Wednesday, 3/9
      Jie Gao (Moore 239, 3:00pm)
      The hardness of localization problem by local angle information

• Wednesday, 3/2
      Mike Langberg (Moore 239, 3:00pm)
      Strong concentration and oblivious channels

February 2005

• Wednesday, 2/23
      Shankar Kalyanaraman
      (title)

• Wednesday, 2/16
      Tudor Stoenescu
      Decentralized Resource Allocation Mechanisms in Networks

• Wednesday, 2/9
      Sidharth Jaggi
      Correction of adversarial errors in networks

• Wednesday, 2/2
      Xiaojie Gao
      Superimposed codes

January 2005

• Wednesday, 1/26, 3:00pm in Moore 239
      Kevin Ko
      "Stochastic Linear Control Over a Communication Channel", Tatikonda, Sahai, and Mitter

December 2004

• Wednesday, 12/8
      Manor Mendel
      Measured descent: A new embedding method for finite metrics

• Wednesday, 12/1
      Shankar Kalyanaraman
      Seedless extractors from a constant number of weak random sources

November 2004

• Wednesday, 11/10
      Leonard Schulman
      Channel coding for distributed control

October 2004

• Wednesday, 10/20, 4:00 in 080 Moore
      Santosh Vempala
      How to Compute the Volume?

• Wednesday, 10/6, 4:00 in 080 Moore
      Yuval Rabani
      Low Distortion Maps between Point Sets

August 2004

• Monday, 8/16, 1:30
      Tom Hayes
      Recent work on randomly sampling graph colorings

May 2004

• Wednesday, 5/19
      Alex Sprintson
      Efficient Backup Allocation in Networks with Partial Information

• Wednesday, 5/12
      Noam Berger
      How to gamble forever

• Wednesday, 5/5
      Matt Cook
      Relational Circuits

April 2004

• Wednesday, 4/28
      Yuval Cassuto
      List decoding

• Wednesday, 4/7
      Nevin Kapur
      Asymptotic distributional analysis of the space requirement of random m-ary search trees

• Thursday, 4/1, 4:00pm (Jrg 74)
      Umesh Vazirani
      Expander Flows, Geometric Embeddings and Graph Partitioning

March 2004

• Wednesday, 3/31, 3:00pm
      Mike Langberg
      Private Codes

• Friday,  3/5, 2:30pm (Low group: Jorgensen 287)
      Babak Hassibi
      ITR rotation

February 2004

• Friday,  2/27, 1:00pm (Jrg 74)
      Miklos Santha
      Quantum and Classical Query Complexities of Local Search are Polynomially Related

• Wednesday,  2/25, 2:30pm (Jrg 287)
      Michelle Effros
      ITR rotation

• Tuesday,  2/24, 6:00pm (Murray group: room?)
      Steven Low
      ITR rotation

• Friday,  2/20, 3:00pm (Hassibi group: Moore 139)
      Richard Murray
      ITR rotation

• Wednesday,  2/18, 3:00pm (Effros group: Moore 139)
      Leonard Schulman
      ITR rotation

• Wednesday,  2/11
      Xiaojie Gao    

• Thursday,  2/5
      Elchanan Mossel
      Card shuffling, sorting and RC4ing

• Wednesday,  2/4
      Michael Mahoney
      Fast Monte Carlo Algorithms for Massive Data Sets and Approximating Max-Cut

January 2004

• Wednesday,  1/28
      Shankar Kalyanaraman
      Locally-decodable and locally-testable codes

• Wednesday,  1/14
      Chris Umans
      "symmetric alternation" complexity classes

December 2003

• Wednesday,  12/10
      Sridhar Rajagopalan (Jrg 74)
      Web search: mathematical ideas and research themes

• Thursday,  12/4
      Christos Papadimitriou (4pm, 25 Baxter)
      Games and Networks

November 2003

• Wednesday,  12/3
      Alex Sprintson
      Network design problems

• Wednesday,  11/12
      Lawrence Ip
      Limited Randomness LT Codes

• Wednesday,  11/5
      Andrew Jiang
      Interleaving

October 2003

• Wednesday,  10/29
      Mike Langberg
      Property Testing

• Wednesday,  10/22
      Shankar Kalyanaraman
      "List-decoding Using the XOR Lemma" by Luca Trevisan (continued)

• Wednesday,  10/9
      Ron Lavi
      Towards a characterization of truthful combinatorial auctions

• Wednesday,  10/1
      Shankar Kalyanaraman
      "List-decoding Using the XOR Lemma" by Luca Trevisan

September 2003

• Wednesday,  9/25
      Xiaojie Gao  
      Fair router congestion control algorithms

• Wednesday,  9/18
      Po-Shen Loh   
      Stochastic construction of expander graphs

• Wednesday,  9/11
      Henry Cohn
      Sphere-packing

• Thursday,  9/4
      Nevin Kapur
      Singularity analysis

August 2003

• Thursday,  8/21
      Kai Chen
      Coding theory and extractors

• Friday,  8/15
      Chris Umans
      A group-theoretic approach to fast matrix multiplication

• Thursday,  8/7
      Muli Safra
      Analysis of Boolean functions

June 2002

• Wednesday,  6/19
      Ashwin Nayak
      The Shaltiel-Umans extractor construction (continuation of the 5/15 meeting)
   
   
• Wednesday,  6/12,  1:30 pm
      Alex Russell
      Min-entropy cryptography, or How to fool an unbounded adversary with a short key
   
   
• Wednesday,  6/5, 10:30 am
      David DiVincenzo
      Constant-depth quantum circuits and Arthur Merlin games

May 2002

• Wednesday,  5/15
      Ashwin Nayak
      Extractors:  an introduction

• Wednesday,  5/8
      Leonard Schulman
      Majorization inequalities
   
   
• Wednesday,  5/1
      Sean Hallgren
      Impagliazzo, Paturi, and Zane's paper ``Which Problems Have Strongly Exponential Complexity?''

April 2002

• Thursday,  4/11,  2:00 pm
      Jeong Han Kim    (Microsoft Research)
      The Poisson model for random graphs
   
   
• Wednesday,  4/3
      Ben Toner
      Simulating quantum correlations with local hidden variables and classical communication

March 2002

• Wednesday,  3/27
      Yaoyun Shi
      Razborov's new sqrt(n) lower bound for the quantum communication complexity of Set Disjointness
   
   
• Wednesday,  3/6
      Guifre Vidal
      Irreversibility in asymptotic manipulations of entanglement

February 2002

• Wednesday,  2/6
      Patrick Hayden
      Quantum communication complexity of state transformations

January 2002

• Thursday,  1/24,  2:00 pm
      Barbara Terhal
      Non-interacting fermionic quantum computation
   
   
• Thursday,  1/10,  2:00 pm
      Yaoyun Shi
      Improved quantum lower bounds for Collision Finding and Element Distinctness