skip to main content

CS 598 MAF - Pseudorandomness

Fall 2020

Official Description

Subject offerings of new and developing areas of knowledge in computer science intended to augment the existing curriculum. See Class Schedule or departmental course information for topics and prerequisites. Course Information: May be repeated in the same or separate terms if topics vary.

Section Description

Title: Pseudorandomness Description: Pseudorandomness is the study of efficiently constructing objects that share desirable features of random objects, yet require no randomness to describe. The theory of pseudorandomness influences and draws from areas in computer science such as computational complexity, algorithms, and cryptography; as well as areas of mathematics such as combinatorics and number theory. This course will explore the core aspects of pseudorandomness by constructing foundational pseudorandom objects such as expander graphs, error-correcting codes, randomness extractors and pseudorandom generators, as well as presenting key techniques such as spectral graph theory, (derandomized) concentration bounds, and the polynomial method. Prerequisites: basic familiarity with probability, linear algebra, algorithms, and computational complexity