Efficiently generating objects that "look random" despite being constructed using little or no randomness. Connections and applications to computational complexity, cryptography, and combinatorics. Pseudorandom generators, randomness extractors, expander graphs, error-correcting codes,...

This course is about the following question:

How can we enable the analysis of datasets with sensitive information about individuals while protecting the privacy of those individuals?

Computational complexity aims to understand the fundamental limitations and capabilities of efficient computation.  For example, which computational problems inherently require a huge running time to solve, no matter how clever an algorithm one designs? This most basic question of computational complexity is now understood to be both extremely difficult and of great importance, as demonstrated by all the attention given to the famous P vs. NP question.... Read more about CS 221. Computational Complexity

Efficiently generating objects that ``look random'' despite being constructed using little or no randomness. Connections and applications to computational complexity, cryptography, and combinatorics. Pseudorandom generators, randomness extractors, expander graphs, error-correcting codes,...