News
04.02.2019

ExamsPlease 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 tutorialDear all, In today's tutorial, in lieu of discussing a problem set, I will talk a little bit about the BLRtest (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 BLRtest (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 todayDear all, unfortunately, I am ill at the moment, and so is the usual standin for the tutorial, Marc. Therefore, there is no tutorial today. Cheers, 
04.12.2018

Assignment 4In exercise 4.3, in the definition of epsilonclose 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 5will go online this Wednesday (Dec 5), on popular request. It will be due one week later. 
19.11.2018

Regular lecture instead of a tutorialThere 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 TutorialsThe 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: