Princeton University
|
Computer Science COS 598D
|
|
| News:
· Everyone interested in this course is welcome to join the mailing list |
Professor: Boaz Barak - 405 CS Building. Email: Phone: 609-981-4982 (I prefer email)
Graduate Coordinator: Melissa Lawson - 310 CS Building - 258-5387 mml@cs.princeton.edu
Grading: TBD, there may be some homeworks.
February 2008
Sun Mon Tue Wed Thu Fri Sat
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29
|
March 2008
Sun Mon Tue Wed Thu Fri Sat
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31
|
April 2008
Sun Mon Tue Wed Thu Fri Sat
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30
|
May 2008
Sun Mon Tue Wed Thu Fri Sat
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31
|
Reading: Natural proofs were defined in this paper by Razborov and Rudich.
The connection between rigidity and lower bounds is
from this paper of valiant. The notion of of
natural proofs for matrix rigidity and its connection to decoding parity with
noise was given in this paper of
Alekhnovich.
The following "mini book" by Hoory, Linial and Wigderson is fantastic resource on expander graphs and their applications. For extractors an excellent starting point is Shaltiel survey. See also Stinson's survey on the leftover hash lemma.
Reading for next week: We'll start covering some notions
in cryptography, and I will assume some basic concepts such as those taught
in my undergrad
crypto class last term. Please read the following
draft of the crypto chapter from my complexity book, and in particular
go over Section 9.3 including the proofs of Theorems 9.10 (unpredictability implies
pseudorandomness) and 9.11 (Goldreich-Levin hardcore bit).
Lecture notes by Moritz Hardt and Srdjan Krstic
The result that one-way functions imply pseudorandom generators was achieved for non-uniform security by Impagliazzo, Levin, and Luby (STOC '89) and in the uniform case by Håstad (STOC '90). They joined forces for the journal version commonly known as HILL.
Our presentation was inspired by the papers of Thomas Holenstein who first proved in 2005 a uniform version of the hardcore lemma (that was originally proven in this FOCS 95 paper of Impagliazzo for the non-uniform setting) and then in 2006 used it to give a simpler proof of the HILL result. However, I presented a different proof of the hardcore lemma from this paper by Satyen Kale. I believe that like Russell's proof, the current proof can be "uniformized" as well, but I didn't verify this.
One observation useful for the uniform setting is that we can use a notion of pseudoentropy where the high entropy distribution
depends on the distinguisher. Some relations between different notions of entropy are explored in this paper by me, Ronen Shaltiel and Avi Wigderson (although this
paper focused mainly on the case of constant distance epsilon as opposed to negligible epsilon as is in cryptography; still
I believe some of the results are relevant for HILL).
Lecture notes by Mohammad Mahmoody-Ghidary
The construction of universal-one-way hash functions from one-way permutations is from Naor-Yung 1989 while the construction based on one-way functions is by Rompel 1990.
For a full description of the one-way permutation based construction, as well as its use
for constructing signature schemes, see Section 6.4.3 of Goldreich's "Foundations of Cryptography Vol II" -
see this Internet draft. For a full proof
of Rompel's construction, see this paper by Katz and Koo.
Lecture Notes by Sina Jafarpour
The interactive hashing protocol we presented is due to Ostrovsky, Venkatesan and Yung (Eurocrypt 92) but the proof that it yields a "coin tossing to the well" protocol is by Naor, Ostrovsky, Venkatesan and Yung (NOVY - Crypto 92). The proof we presented in class is due to Haitner and Reingold (CCC 07), you can also see slides of this paper.
For the result that statistically hiding commitments can be based on any one-way function see
this manuscript by Haitner, Nguyen,
Ong, Reingold and Vadhan.
Lecture notes by Aditya Bhaskara and Siddhartha Sen
Some of the presentation was from the Communication Complexity
chapter of my upcoming book with Sanjeev Arora. The result that ACC can be computed
by a symmetric function on top of a polynomial of polylog degree and quasipoly size is by Yao,
some improvements were given in this paper
of Beigel and Tarui.
Lecture Notes by Aravindan Vijayaraghavan
Exposition of main part of Forster's proof by David Stuerer.
Razborov's paper can be found here. This proof inspired Raz in his proof of the parallel repetition theorem (see also this simplified proof by Holenstein).
Forster's paper can be found here. See also the
corresponding technical report. Forster's result and its extensions was used in many results in communication complexity. A recent example is this paper by Razborov and Sherstov.
Forster's result can be viewed as a much stronger version of a simpler older result (contained in this paper of Nisan and Wigderson) that the discrepancy of low rank matrices is high. (Forster shows this is true even if only the sign rank is low.)
Lecture notes by Simion Philip
Sherstov's paper can be found here.
Here's a tutorial on group representations
by Henry Cohn. (Thanks to Chris Umans for the link.)
Dimension expanders, matrix multiplication.
Lubotzky-Zelmanov paper on dimension expander over complex numbers and Dvir-Shpilka paper on (weaker) dimension expanders oover finite fields.
The approach for matrix multiplication based on group representations was developed in the following
two papers of Cohn and Umans and Cohn, Kleinberg, Szegedy and Umans. See also this SIAM news article.
Lecture notes by Srdjan Krstic
Definition of lattices and some basic properties. Some computational problems on lattices. The LLL algorithm. Definition of the smoothing parameter. Worst-case to average case reduction - collision resistant hash function based on the worst-case hardness of shortest vector problem (guest lecture: Benny Applebaum).
Much of the material was based on the lecture notes of Oded Regev's excellent course
on Lattices in Computer Science (particularly lecture 1 - lattices, lecture 2 - LLL , and lecture
12 - worst-case to average case reduction). The original worst-case to average
case reduction was by Ajtai. The version we presented using the smoothing parameter is from this
this paper of Micciancio and Regev though we used a slightly different definition in the class.
Lecture notes by David Steurer
See also Boaz's lecture outline (latex source). (See also these slides mostly taken from Oded Regev's presentations.)
The first public key encryption based on worst-case lattice problem was given by Ajtai and Dwork. The version we presented is a variant of Regev's cryptosystem (see also powerpoint presentation). There have been some improved schemes since then, in particular see this paper of Gentry, Peikert and Vaikuntanathan and this paper of Peikert and Waters.
A fascinating result that we did not talk about is given in this paper by Regev (see also powerpoint presentation) who showed a simple cryptosystem that is based on the quantum worst-case hardness of the standard shortest vector lattice problem.