# Pseudorandomness and Derandomization Markus BlĂ¤ser

## News

04.02.2019

#### Exams

Please make appointments for the oral exams by email. The duration of the exams will be between 30 and 45 minutes.

A typical starting question might be "What is a pseudorandom generator and what is it good for?¨ Such questions give you the chance to talk about... Read more

Please make appointments for the oral exams by email. The duration of the exams will be between 30 and 45 minutes.

A typical starting question might be "What is a pseudorandom generator and what is it good for?¨ Such questions give you the chance to talk about some topic and you should seize this opportunity. More specific questions might be "How does the NW generator work?" and "What are the main proof ideas?". Of course we do not expect a full proof, but a good answer should provide the main ideas and concepts.

You will not be asked to solve certain exercises.

16.01.2019

#### Today's tutorial

Dear all,

In today's tutorial, in lieu of discussing a problem set, I will talk a little bit about the BLR-test (to determine how close to linear a Boolean function is), which uses the results about Fourier analysis of Boolean functions from the last problem set.... Read more

Dear all,

In today's tutorial, in lieu of discussing a problem set, I will talk a little bit about the BLR-test (to determine how close to linear a Boolean function is), which uses the results about Fourier analysis of Boolean functions from the last problem set. Time and place as usual.

05.12.2018

#### No tutorial today

Dear all,

unfortunately, I am ill at the moment, and so is the usual stand-in for the tutorial, Marc. Therefore, there is no tutorial today.

Cheers,
Cornelius

04.12.2018

#### Assignment 4

In exercise 4.3, in the definition of epsilon-close to linear, the condition inside the probability should be f_x(z) = a(z) instead of  f_x(z) \not= a(z). I am sorry.

03.12.2018

#### Assignment 5

will go online this Wednesday (Dec 5), on popular request. It will be due one week later.

19.11.2018

#### Regular lecture instead of a tutorial

There will be a regular lecture instead of a tutorial on Wed, Nov 21,  2018. There will be no lecture on Mon, Dec 3, 2018.

07.11.2018

#### No lecture on Mon, Nov 12.

As already mentioned in class, there will be no lecture on Mon, Nov 12.

30.10.2018

On Wed, Oct. 31, we will have a regular lecture instead of the tutorial (at the same time as the tutorial). The lecture takes place in the tutorial room.

23.10.2018

#### Room for Tutorials

The room for the tutorials is Seminar room 5 (011) in E2 4, and we begin at 4.15pm every Wednesday.

## Pseudorandomness and Derandomization

### Time and Date:

• Monday 10:15 - 12:00, E1.3 SR015

First lecture will be on Monday, October 22!

### Tutorials:

• Wednesday 16:15 - 17:45, E2 4 Seminar Room 05 (011)

### Assignments:

There will be weekly assignments. To be admitted to the exam, you have to achieve half the points in the assignments.

### Exams:

There will be oral exams at the end of the semester.

### Prerequisites:

Core lecture "Complexity Theory" is highly recommended.