Program for Randomness in Computation

Special Session on Randomness in Computation
Fall Central Section Meeting of the American Mathematical Society
University of Nebraska-Lincoln, October 21-23, 2005



Friday, October 21

Session I (8:30-11:30)

8:30 - 9:00 Satyanarayana V. Lokam
Quadratic Lower Bounds on Matrix Rigidity
9:00 - 9:30 Christopher Umans
Reconstructive Dispersers and Hitting Set Generators
9:30 - 10:00 Amnon Ta-Shma
If NP Languages are Hard on the Worst-Case then it is Easy to Find Their Hard Instances
10:00 - 10:30 break
10:30 - 11:00 Jack H. Lutz
Dimensions of Copeland-Erdös Sequences
11:00 - 11:30 Xiaoyang Gu
Finite-State Dimension and Relative Frequencies

Session II (1:45-3:15)

1:45 - 2:15 Eric Allender
On the Complexity of Numerical Analysis
2:15 - 2:45 Ryan W. O'Donnell
Stability and Chaos in Elections (with Applications in Mathematics and Computer Science)
2:45 - 3:15 Emanuele Viola
Pseudorandom Bits for Low Complexity Classes: New Results and Applications


Saturday, October 22

Session III (8:30-11:30)

8:30 - 9:00 Lance Fortnow
Connections Between Kolmogorov and Computational Complexity
9:00 - 9:30 Jaikumar Radhakrishnan
The List-Decoding Radius for Reed-Solomon Codes
9:30 - 10:00 Sambuddha Roy
The Directed Planar Reachability Problem
10:00 - 10:30 break
10:30 - 11:00 Ravi Kumar
On Separating Nondeterminism and Randomization in Communication Complexity
11:00 - 11:30 Rahul Santhanam
Hierarchies for Smoothed Probabilistic Classes


[an error occurred while processing this directive] [an error occurred while processing this directive]