Title: Big Data as a Powerful Source of Randomness

Speaker: Periklis A. Papakonstantinou (IIIS, Tsinghua University)

  　  　  iiis.tsinghua.edu.cn/~papakons

Time: 7th April 2015, 15:00

Venue: Seminar Room (334), Level 3, Building 5, Institute of Software, CAS

Abstract:

We take an unconventional view over Big Data, where instead of trying to extract useful information from such data -- as in e.g. medicine, finance, and marketing -- we view the proliferation of Big Data as an ever-generating source of low-quality randomness. We devise the first-ever method showing that it is possible to transform this low-quality Big Sources of randomness into a useful, (almost) uniformly distributed random bits. Our method circumvents a number of provable limitations, including a general impossibility result -- i.e. the perhaps surprising issue is that randomness extraction from big sources is at all possible. I'll report progress in the extensive mathematical and experimental study we conducted in this setting in the last four years, a research that concluded just recently.

This is joint work with Guang Yang.

Biography:

Periklis Papakonstantinou studied electronics, computer engineering, computer science, and mathematics. He holds a professional engineering degree, and several graduate degrees, including a PhD in Computer Science from the University of Toronto. Immediately after his PhD he joined ITCS/IIIS at Tsinghua University as a tenure-track assistant professor and PhD supervisor, an appointment he is holding ever since. He is currently leading the Laboratory for the Study of Randomness (RC3) at Tsinghua University. His research contribution is in computational complexity theory (at large), computation over big data, cryptography, and more recently in machine learning. So far, two PhD students have graduated under his supervision following careers in research and industry.