Skip to main navigation
Skip to Content
Computer Science
University of Toronto
Quercus
Student Support
Contact
About
History of U of T Computer Science
Computer Science at U of T Mississauga
Computer Science at U of T Scarborough
Employment Opportunities for Faculty/Lecturers
How to Find Us
Contact
Undergraduate
Prospective Undergraduates
Current Undergraduates
Graduate
Prospective Graduate Students
Current Graduate Students
Research
Research Areas
Partner with us
People
Faculty
Staff
In Memoriam
Alumni and Friends
Honours & Awards
Women in Computer Science
Graduate Student Society
Undergraduate Student Union
Undergraduate Artificial Intelligence Group
Undergraduate Theory Group
News & Events
News
Events
@DCS Update
Alumni
Donate
You are viewing: >
Home
>
News & Events
>
Events
> Theory Seminar - Feb 15
About
Undergraduate
Graduate
Research
People
News & Events
Theory Seminar - Feb 15
Event date: Friday, February 15, 2013, at 11:10 AM
Location: GB 248
Speaker: Thomas Watson
University of California, Berkeley
Title: The Computational Complexity of Randomness
Abstract:
This talk will give an overview of our doctoral research, which addresses several topics regarding the role of randomness in computational complexity. The bulk of the talk will focus on "Time Hierarchies for Sampling Distributions", in which we show that "a little more time gives a lot more power to sampling algorithms." More precisely, we prove that for every constant k>=2, every polynomial time bound t, and every polynomially small eps, there exists a family of distributions on k elements that can be sampled exactly in polynomial time but cannot be sampled within statistical distance 1-1/k-eps in time t. This implies the following general time hierarchy for sampling distributions on arbitrary-size domains such as {0,1}^n: For every polynomial time bound t and every constant eps>0, there exists a family of distributions that can be sampled exactly in polynomial time but cannot be sampled within statistical distance 1-eps in time t. Our proof involves a new connection to list-decodable codes for communication over a certain type of noisy channel.