Speaker: Eric Allender, Professor of Computer Sciences, Rutgers University
Title: Randomness and Complexity
Time and location: 12:30 pm - 2 pm, DIMACS Center, Room 431,
Rutgers University.
Lunch will be served.
Abstract
What is a random sequence?
Many possible answers to this question have been proposed. We will investigate some of the notions of “randomness” and “pseudorandomness” that are of great practical and theoretical importance in computer science.
Along the way, we will provide an introduction to computational complexity theory, including the theory of NP-completeness. We will also introduce Kolmogorov complexity and some variants of this notion.
We will present some simple applications of Kolmogorov complexity. For example, we will show that Kolmogorov complexity can give simple proofs of some statements avout the distribution of prime numbers. Also, we will show how to use Kolmogorov complexity to write “optimal” programs for NP-complete problems. ( That is, we will see how to write a program to find Hamiltonian Cycles whose running time is essentially optimal; unfortunately, nobody know how long this program needs to run to find such cycles.)
If time permits, I will also discuss some of my own research regarding pseudorandom generators, Kolmogorov complexity, and complete sets for complexity classes.