Randomness and Hardness

This semester, Prof. Arvind is offering a lecture series on the issues related to randomness and hardness, extractors, expanders and error correcting codes. Last 5 lectures he has been talking about randomness and hardness. For the first time I have had such a great introduction to the topic. I shall now write a small summary of few issues discussed during these lectures. But only techinical issues are infact from the lecture. All the other junk is self cooked, so please excuse Arvind if any errors below.

First of all why should one try to relate randomness and hardness? Lets eavesdrop on the following conversation.

A: You are always doing something unexpected
B: Why what happened...?
A: I mean, "knowing you so long" I felt you would have said 'yes' to join for picnic...but you are "truly random"
B: truly random??
A: yes, very very "hard" for me to predict..

As is evident, 'random' and 'hard to predict' are almost synonymous phrases.

Next, What is random and what is not?
So to define any sort of randomness one would like to have a observer dependent view point. This is infact what is called pseudorandom. Say I am God (if you wish) and I know everything and I remember everything and I have all the time in the world. Well then, may be nothing is random and I will know what is in store next. But if I am merely a mortal, then even an unexpected rain is a random event. But suppose I am a mortal working in for weather forecasting, then again things are different. In other words if I am a resource bounded computation machine, then depending on how little or how huge my resources, some function will 'seem' truly random to me. Hence, computer scientists define randomness with respect to a resource bounded complexity class. The main point is, one doesn't have to be truly random, one just should 'seem' to be random, pseudorandom.

The focus of the course has been on building pseudorandom generators (PRG). They are typically functions which take small (length m) strings which are "truly random" and output longer (length n) strings (m less than n) . The output of the PRG is a valid input to a random algorithm A from a complexity class C. And C is a complexity class to which output of this PRG seems truly random. Now suppose one needs to have a algorithm B to do exactly what A does, but without using any random bits. In this the PRG plays a important role. What B does is runs over all choices of inputs to PRG (all length m strings) and does exactly what A would do. Now note that B doesn't use any randomness. Also thanks to the property of PRG of being able to stretch small inputs to longer outputs the algorithm B simply needs to run over all choices of m length strings (2^m) rather than having to run over 2^n choices. This is the process of derandomization. All the effort is being made to unconditionally derandomize random complexity classes like BPP.

Now to technically summarise what has been proved till today:

Nisan and Wigderson's definition for PRG.
Nisan widgerson construction for PRG.
If quick PRG G: m -->n exists then for every nice t(n) BPTIME(t(n)) <= DTIME(2^(m(t(n))). Existence of PRG <--> Hard functions.
If there is a function f in E=DTIME(2^(O(n))) which has subexponential hardness then P=BPP.
If here is a function f in E has polynomial hardness then BPP <= intersection over all c' of DTIME(2^n^c') Theorem by babai,fortnow,nisan,wigderson:If (EXP is not contained in P/poly) then BPP is contained in intersection over all c' of DTIME(2^n^c')

Proof outline: Direct Products for hardness amplification.
Goldreich-Levin Theorem
Two more theorems to come. today he talked about some quasii random strings which I haven't understood yet. So hopefully I type some more later.