AMS Sectional Meeting Program by Special Session

Current as of Saturday, October 29, 2005 01:24:04

Associate secretaries:
Susan J Friedlander, AMS susan@math.northwestern.edu

Friday October 21, 2005, 8:30 a.m.-10:50 a.m.
Special Session on Randomness in Computation, I
Room 347, Avery Hall
Organizers:
John M. Hitchcock, University of Wyoming jhitchco@cs.uwyo.edu
Aduri Pavan, Iowa State University pavan@cs.iastate.edu
Vinodchandran Variyam, University of Nebraska-Lincoln vinod@cse.unl.edu
- 8:30 a.m.
  Quadratic Lower Bounds on Matrix Rigidity.
  Satyanarayana V. Lokam*, Microsoft Research, Redmond, WA
  (1011-68-177)
- 9:00 a.m.
  Reconstructive Dispersers and Hitting Set Generators.
  Christopher Umans*, Computer Science Dept., Caltech, Pasadena CA
  (1011-68-269)
- 9:30 a.m.
  If NP languages are hard on the worst-case then it is easy to find their hard instances.
  Dan Gutfreund, Hebrew University
  Ronen Shaltiel, University of Haifa
  Amnon Ta-Shma*, Tel-Aviv University
  (1011-68-355)
- 10:00 a.m.
  Dimensions of Copeland-Erd\"os Sequences.
  Jack H. Lutz*, Department of Computer Science, Iowa State University
  (1011-68-292)
- 10:30 a.m.
  Finite-State Dimension and Relative Frequencies.
  Xiaoyang Gu*, Department of Computer Science, Iowa State University
  (1011-68-337)

Friday October 21, 2005, 1:45 p.m.-3:05 p.m.
Special Session on Randomness in Computation, II
Room 347, Avery Hall
Organizers:
John M. Hitchcock, University of Wyoming jhitchco@cs.uwyo.edu
Aduri Pavan, Iowa State University pavan@cs.iastate.edu
Vinodchandran Variyam, University of Nebraska-Lincoln vinod@cse.unl.edu
- 1:45 p.m.
  On the Complexity of Numerical Analysis.
  Eric Allender*, Rutgers University
  Peter Buergisser, University of Paderborn
  Johan Kjeldgaard-Pedersen, PA Consulting Group, Copenhagen
  Peter Bro Miltersen, University of Aarhus
  (1011-68-219)
- 2:15 p.m.
  Stability and chaos in elections (with applications in mathematics and computer science).
  Ryan W. O'Donnell*, Microsoft Research
  (1011-60-381)
- 2:45 p.m.
  Pseudorandom bits for low complexity classes: new results and applications.
  Emanuele Viola*, Harvard University
  (1011-68-277)

Saturday October 22, 2005, 8:30 a.m.-10:00 p.m.
Special Session on Randomness in Computation, III
Room 347, Avery Hall
Organizers:
John M. Hitchcock, University of Wyoming jhitchco@cs.uwyo.edu
Aduri Pavan, Iowa State University pavan@cs.iastate.edu
Vinodchandran Variyam, University of Nebraska-Lincoln vinod@cse.unl.edu
- 8:30 a.m.
  Connections Between Kolmogorov and Computational Complexity.
  Lance Fortnow*, University of Chicago
  (1011-68-98)
- 9:00 a.m.
  The list-decoding radius for Reed-Solomon codes.
  Eli Ben-Sasson, Toyota Technological Institute at Chicago
  Swastik Kopparty, MIT
  Jaikumar Radhakrishnan*, Toyota Technological Institute at Chicago and Tata Institute, Mumbai
  (1011-68-255)
- 9:30 a.m.
  The Directed Planar Reachability Problem.
  Eric Allender, Rutgers University
  Samir Datta, Chennai Mathematical Institute
  Sambuddha Roy*, Rutgers University
  (1011-68-239)
- 10:00 a.m.
  Break
- 10:30 a.m.
  Discussion
- 11:00 a.m.
  Hierarchies for Smoothed Probabilistic Classes.
  Rahul Santhanam*, Simon Fraser University
  (1011-68-388)

Inquiries: meet@ams.org