teaching

Course Description

Randomized algorithms are everywhere in computer science, and they're crucial for areas such as cryptography and learning. Why then do theorists believe that when solving decision problems, random algorithmic choices can always be efficiently replaced by carefully planned deterministic choices? More generally, can we simulate algorithmic randomness in efficient ways, and if so - how?

In this course we'll dive into the BPP = P conjecture, which is one of the main conjectures in complexity theory. Starting from the definitions and classical results from the 1990s, we'll make our way to very recent research, passing through areas such as circuit complexity, error-correcting codes, interactive proof systems, cryptography, and more. Our goal will be to understand the conjecture and its theoretical basis, to learn about its recent strengthenings and about new approaches to studying it, and to get introduced to its broader implications on computer science.

Prerequisites

The course will assume basic background in complexity theory, which means that should have studied at least one course that includes complexity content (e.g., CSCC63 or CSC463 or CSC2401). If you're interested in the course but are unsure whether or not you have the necessary prerequisites, you're more than welcome to email me and ask about it.

MEETINGS SCHEDULE: https://docs.google.com/document/d/1yjBP7rXqWaEQQ8RA0E5vKA2qAVN9lVdtYh8tfR48m1o/edit

Course Description

Randomness is a keystone in entire areas of computer science, such as cryptography and learning. Why then do most complexity theorists believe that randomness isn't necessary when solving decision problems and natural search problems? And what makes this conjecture so important?

This course will focus on the key challenge when studying this conjecture, which is derandomization: Efficiently simulating algorithms that use randomness by "deterministic" algorithms that don't use randomness. We will study the connection of derandomization to other main questions in complexity theory, such as complexity class separations, circuit lower bounds, meta-complexity problems, and more. This is the area of research that is typically called "hardness vs randomness". 

On our way from hardness to randomness and back we'll take a wild ride throughout complexity theory: We will study results from circuit complexity, interactive proof systems, coding theory, randomness extraction, learning theory, and more.

Prerequisites

I'll assume basic background in complexity theory, e.g. having studied at least one course that includes complexity content. You should be comfortable with basic modeling conventions (i.e., algorithm analysis and encodings of objects and of algorithms as strings), know about standard resources (time, space, randomness), and be familiar with the relations between complexity classes (e.g., P and NP and BPP and PSPACE).

If you're interested in the course but unsure whether your background suffices, it's likely that you can prepare well enough by reading ahead of time. Feel free to contact me about it.

Syllabus and learning goals

The course is designed for you to learn about derandomization, about its known connections with other main questions in complexity theory, and about technical tools used to obtain results in this area so far.

• The first part of the course will focus on classical "hardness-to-randomness" results, such as Yao's unpredictability vs pseudorandomness lemma, the Nisan-Wigderson generator, the Impagliazzo-Wigderson generator based on uniform hardness, the Sudan-Trevisan-Vadhan coding-based hardness amplification, and the connection between pseudorandom generators and randomness extractors. These can generally be found in complexity textbooks such as Goldreich's or Arora-Barak. 

• In the second part of the course we'll focus on more advanced (and more recent) "hardness-to-randomness" results, including the polynomial-based derandomizations of Shaltiel and Umans, applications of IP=PSPACE and of doubly-efficient proof systems to derandomization, and non-black-box derandomization and its connections to new types of lower bounds as well as to meta-complexity problems.

• In the last part of the course we'll take the converse route, typically called "derandomization implies circuit lower bounds". We will study modern Karp-Lipton theorems, the Impagliazzo-Kabanets-Wigderson result, Williams' algorithmic method for circuit lower bounds, and transformations of derandomization algorithms to (non-deterministic) pseudorandom generators.

Ideally, at the end of the course you'll feel comfortable reading newly published papers in the area and thinking about them independently.

Expected work

• Thinking about the material, understanding it and internalizing what you learn.

• Presenting technical results from a research paper in class (either once or twice, for an hour).

• Preparing for some of the classes by reading preliminary materials online (typically catching up from existing lecture notes, e.g. about finite field theory or coding theory).