1;95;0c## CS761: Derandomization and Pseudorandomness (2022-23 Sem I)

Course Contents The course is about trying to understand randomness and its role in computer science, specifically in design of algorithms. There are settings like cryptography, distributed computing, communication complexity where randomness is known to play a essential role. In algorithm design, use of randomness often leads to elegant, simple, and fast algorithms. However, it is unclear whether use of randomness allows us to design efficient algorithms for a strictly larger class of problems as compared to that without using randomness. It is commonly believed that the answer is no. That is, every problem with an efficient randomized algorithm is believed to have an efficient algorithm without randomization. The course will cover various kinds of settings where randomization is used and will introduce fundamental techniques which enables one to do away with randomness. Randomness will be viewed as a resource and we will deal with its tradeoff with other resources like -- time, space, communication etc.

We plan to cover the following topics.

Pre-requisites: You are expected to know basics of algorithms (CS218/CS601), linear algebra, graph theory, finite fields.

Course Meetings: Mon, Thu 19:00-20:55 (SIC 201)

Lectures

Presentation topics

References