P.Pudlak's lecture at the
Fall school (Sept.'11)

Randomness, pseudorandomnesss and models of arithmetic

In probability theory random sequences of 0s and 1s play an important role. Studying randomness of individual sequences has been studied in the field of algorithmic randomness. In number theory there are some important sequences for which properties of random sequences have been conjectured and some have also been proven. The most important among them is the Mobius function (a sequence of -1s,0s and 1s). In cryptography it has been conjectured that there are low complexity sequences that have such properties. This also has been conjectured for specific sequences. I will present a different perspective from which these phenomena can be studied. It is based on models of weak bounded arithmetics. The idea is to explain pseudorandomness of a specific sequence S by the random behavior of the sequence S in extensions of a fixed model.