The power and weakness of randomness (when you are short on time)
Man has grappled with the meaning and utility of randomness for
centuries. Research in the Theory of Computation in the last thirty
years has enriched this study considerably. I'll describe two main
aspects of this research on randomness, demonstrating respectively its
power and weakness for making algorithms faster. I
will address the role of randomness in other computational settings,
such as space bounded computation and probabilistic and zero-knowledge
Date: Wednesday, May 12, 2010
Tea: 4:00 pm-4:30 pm
Talk: 4:30 pm-5:30 pm
When & Where
About the Simons Foundation
Established in 1994, the Simons Foundation is a private foundation based in New York City. With assets of $2 billion and annual grants of approximately $170 million, the foundation is dedicated to advancing the frontiers of research in basic science and mathematics.
Simons Foundation programs in Mathematics & Physical Sciences support mathematics, theoretical computer science and theoretical physics, and the foundation's Life Sciences programs have focused on research that promotes synergy between biology and mathematics.
The foundation is also committed to advancing autism research. Launched in 2005, the Simons Foundation Autism Research Initiative (SFARI) is a research campaign whose mission is to improve the diagnosis and treatment of autism spectrum disorders by funding, catalyzing and driving innovative research of the greatest quality and relevance.