towards next meeting (i.e., for 14/12/10)

[עודד גולדרייך‎]

Hi all.

Firstly let me apologize for my failure to explain
the technical issues regarding absolute differences
that arise in the hybrid argument.
My feeling is that you can resolve this issue by yourself
by looking at the text again and recalling the concerns that arise.
(I think this may be better than my trying to explain this yet again,
but if you wish otherwise -- do let me know before next meeting.)

Indeed, these issues must be understood and dealt with,
but they are rather "technical" and "low level" (i.e., they are
not really interesting nor illuminating in any way...).
I find that such issues are best understood by oneself...

Second, I'm very grateful to you for communicating to me
(via Gilad Braunschvig) your preferances towards next meeting.
It seems that there were mixed opinions wrt to whether move
forward or not, and it was suggested that I
1. Given the next reading assignment.
2. Devote next meeting to first answering additional Q&A
(questions&answers)
that may arise re today's material (i.e., Sec 3.2), then move to
Q&A
about the new material (i.e., Sec 3.3 -- see below), and only then
move to motivating new material.
I am happy to act as suggested.

Below is the new reading material towards next meeting (of 14/12/10)

OBLIGATORY MATERIAL
Section 3.3.1 (definition of PRG == pseudorandom generators),
Section 3.3.2 (on increasing the stretch function),
and Section 3.3.6 (PRG implies OWF (one-way functions).
In Sec 3.3.2 you'll see another use of the hybrid method,
but this time things are less "transparent";
an alternative proof (also via an hybrid argument)
can be seen in the exercise below (do take a look at it,
even if you postpone actually working out all details!).

ADDITIONAL/OPTIONAL MATERIAL
Sections 3.3.3, 3.3.4, and 3.3.5.
Sec 3.3.5 would be my highest priority.
Sec 3.3.4, which is a short discussion, is merely for a wider context.
Sec 3.3.3 is "for the sake of elegancy"...

EXERCISE TO BE SUBMITTED (on 21/12/10):
Exercise 19 -- an alternative method for increasing
the stretch of PRGs (i.e., simple iteration).
(Note: you may submit it by 21/12, but I recommend that you do take a
look at
this exercise (and solve it "in principle" (i.e., w.o. details)) when
you read the material.)