|Logistics:|| TTh 11-12:30
Unique Number: 51910
Course web page: http://www.cs.utexas.edu/~diz/395T
Office: GDC 4.508
Office Hours: TBD
Randomization is extremely useful in almost all areas of computer science,
such as algorithms, cryptography, and distributed computing.
Can we derandomize algorithms, i.e., convert randomized algorithms into
Can we save random bits for tasks that do require randomness?
How can we get randomness, when the easily accessible sources of randomness
have little entropy?
What does it mean for a fixed object, such as a graph, to be "random-like"?
In this course, we will study these and related questions. Our explorations will lead us to several important, related pseudorandom objects: pseudorandom generators, expander graphs, randomness extractors, and error-correcting codes.
Topics will be similar to those in the 2009 version of this class, but I will include newer results as well. I will post a tentative list of topics later.
|Prerequisites:||Mathematical and computational maturity, plus familiarity with the following topics:
|Any student with a documented disability (physical or cognitive) who requires academic accommodations should contact the Services for Students with Disabilities area of the Office of the Dean of Students at 471-6259 (voice) or 471-4641 (TTY for users who are deaf or hard of hearing) as soon as possible to request an official letter outlining authorized accommodations.|