Professor Avi Wigderson on a computational theory of randomness

Avi Wigderson is a professor of Mathematics at the Institute for Advanced Study in Princeton. After studying Computer Science at Technion in Haifa, he obtained his PhD in 1983 from Princeton University. He held then various visiting positions including IBM Research at San Jose, MSRI Berkeley, and IAS Princeton. From 1986 to 2003 he was associate professor at the Hebrew University in Jerusalem. Wigderson has been for two decades a leading figure in the field of Mathematics of Computer Science, with fundamental contributions, in particular in Complexity Theory, Randomness, and Cryptography. He has been invited speaker at ICM in Tokyo (1990), and Zurich (1994), and plenary speaker in Madrid (2006). Among many awards he received both the Nevanlinna Prize (1994), and the Gödel Prize (2009).

This lecture about a computational theory of randomness was hold on 10 May 2012 at ETH Zurich, when Avi Wigderson was invited as guest speaker of the Wolfgang Pauli Lectures. The Wolfgang Pauli Lectures are an annual lecture series that is devoted alternately to physics, mathematics and biology. They are named after the great theoretical physicist and Nobel laureate Wolfgang Pauli, who was professor at ETH Zurich from 1928 until his death in 1958.

[MsShith]

Chaos theory suggests that actually, it says that in order for a system to be considered chaotic then even a small neglectable change in it's initial condition can lead to a significant change in the folowing phases of the system .

[ashiit]

All the 3 lectures of the series are really good.

[SaveriusTianhui]

Interesting and intuitive def of randomness, cool applications.

[AmusedChild]

Thank you for the upload. I am wondering about the Doebeli and Herron experiments showing independent similar mutations of bacteria in segregated test tubes, and if this demonstrates an apparent constraint on "random" mutations. (I don't expect an answer - it's just a problem that intrigues me.)

[dalethebelldiver]

the construction of pure elements is a perfect test of random construction.  Will the completed assembly of atoms be helium or gold?  IS there such thing as a completed element or is test sample relative to the time it is tested?  

[MrOreo]

Deterministic world...so does it mean pure randomness lays only in the begining conditions which determinded it all?

[joshuacook]

At 49:08, you claim that if P != NP, then you can derandomize your algorithm resulting in a deterministic polynomial algorithm. Could you give a source? We know that BPP is a subset of the polynomial hierarchy by the Sipser-Lautemann theorem, thus if P = NP the polynomial hierarchy collapses and P = BPP as well. Thus if you have a source that shows if P != NP then P = BPP, then we know that for sure P = BPP, but last time I knew this was an open question.

Am I missing something?

[davidwilkie]

If we accept that the Universe is a "closed" system, then the reasoning is that all possible combinations exist within probability one, but the process of discovery may take forever(?)
Therefore it's a psuodo-random event, and evolution would be direction-less if the combined quantum properties of Pi were not psudo-random and "self-defining" in/as resonance?

If the phrase Mathematicians use, "In some sense" is a real Notional statement of an existential fact, in some proportion, then the eternally-complete value of Pi, e etc, is Prime(?).

[ESEJERITO]

pudiera medirse con matemáticas vectoriales como la de los poliedros en otra di mención  multiplicado por el numero de posibles cara frac-tales dividido por el posible tiempo elevado a la masa del objeto. ¿?

[dalethebelldiver]

I say there is no such thing as random.  Random can always be explained if the TOTAL HIERARCHICAL ENVIRONMENT IS UNDERSTOOD.  This includes time and space and energy summed up to predict the outcome of any reaction.