[Colloq] Hiring Visit: Emanuele Viola 4/28

[Patricia Freeman]

Emanuele Viola will be joining us for a Hiring Visit on Monday, 4/28.
He will be giving his Talk in 366WVH at 10:30am


CCIS Colloquium Spring 2008

Pseudorandomness

Speaker: Emanuele Viola 

Date: Monday, April 28, 2008 

Talk: 10:30 a.m. - 11:30 a.m., 366 WVH

Abstract

Pseudorandomness is the fascinating theory that studies objects that "look random" despite being constructed with little or no randomness. This theory occupies a central place in computer science. In particular, pseudorandomness has led to algorithmic breakthroughs such as "PRIMES is in P." Pseudorandomness also constitutes the foundation of modern cryptography, and it is surprisingly related to the "P vs NP" problem.

In this talk I will give an introduction to pseudorandomness, and I will discuss some of my results in the area. In particular, I will present our construction of sequences that, while being generated with little randomness, nevertheless "look random" to polynomials. This result marks the first progress on this problem since 1993, and has fostered fruitful interaction between computer scientists and leading mathematicians.

Brief Biography

Emanuele Viola is a Postdoctoral Fellow at Columbia University. He received his Ph.D. in 2006 from Harvard University, and in 2006-2007 he was a member of the Institute for Advanced Study. His work was invited to STOC and FOCS special issues, and he was awarded the SIAM Student Paper Prize in 2006. A former video game developer, Emanuele's research interests include computational complexity and pseudorandomness. Most recently he has been exploring problems at the intersection of computer science and economics.