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.

Show all
 

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.

 



Privacy Policy | Legal Notice
If you encounter technical problems, please contact the administrators