Princeton University
Computer Science Department

Computer Science COS 598D
Mathematical Methods in Theoretical CS

Boaz Barak

Spring 2008

· Everyone interested in this course is welcome to join the mailing list

Latest Lecture | Admin | Course Info | Reading | Lecture notes

Course Summary

We'll review some theoretical computer science "pearls", particularly those using mathematical tools that I think might find more applications. Our focus will be mainly on explicit constructions of combinatorial objects and lower bounds for restricted computational models.

Lecture Notes

Administrative Information

Lectures: F 1330-1620, Room: TBD

Professor: Boaz Barak - 405 CS Building. Email: Phone: 609-981-4982 (I prefer email)

Graduate Coordinator: Melissa Lawson - 310 CS Building - 258-5387

course mailing list.

Grading: TBD, there may be some homeworks.

Course Information

We'll review some theoretical computer science "pearls", particularly those using mathematical tools that I think might find more applications. Our focus will be on explicit constructions of combinatorial objects, applications for cryptography, and lower bounds for restricted computational models. A very tentative plan is to cover the following: Natural proofs, Matrix rigidity, Alekhnovits - relation to parity w/ noise "natural constructions". cryptosystem, Frankl/Wilson construction of Ramsey graphs, Extractors, expanders, error correcting codes, Deterministic extractors, Pseudorandom generators from one-way functions, Universal one-way hash functions from one-way functions, Statistically hiding commitments and statistical zero knowledge arguments from one-way functions, Lower bounds on communication complexity, Zig-Zag construction and Reingold's algorithm, k-party Communication complexity, relation to lower bounds on ACC, BNS lower bound for generalized inner product, Sherstov's generalized discrepancy technique, lower bounds for disjointness, implications for Lovasz-Shreivjer proof systems. Topological methods - Borsuk-Ulam Theorem and Lovasz' proof the Kneser conjecture. Representations of groups, approach for matrix multiplications, dimension expanders. Lattices and codes, crypto from lattices. Locally decodable codes and Yekhanin's construction. Karchmer-Wigderson games


I'll post here links to the relevant papers.

Lecture Notes and Handouts.

        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

  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  

Lecture 1: Friday, February 8, 2008
Natural proofs, Ramsey, Rigidity

Explicit constructions and lower bounds. Natural proofs for circuit lower bounds. Natural proofs in other construction problems. Hadamard graph is a Ramsey graph - a "natural" construction. Frankl-Wilson graphs - an "unnatural" construction. Matrix rigidity and its connection to lower bounds - Valiant's lemma. Natural proofs for matrix rigidity - Alekhnovich.

Lecture notes by Simion Filip

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.

Lecture 2: Friday, February 15, 2008
Expanders, extractors, hash functions

Some of the presentation was taken from this chapter of my upcoming complexity book with Sanjeev Arora.

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 3: Friday, February 22, 2008
Pseudorandom generators from one-way functions (HILL)

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 4: Friday, February 29, 2008
Universal-one-way hash functions from one-way functions (Rompel, Naor-Yung)

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 5: Friday, March 7, 2008
Statistically hiding commitments based on one-way permutations.

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 6: Friday, March 14, 2008
Communication Complexity

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 7: Friday, March 28, 2008
Razborov disjointness lower bound, Forster's Theorem

Guest lecturer: Moritz Hardt. Razborov's lower bound on the distributional communication complexity of disjointness. Forster lower bound on the sign rank of matrices with small spectral norm.

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 8: Friday, April 4, 2008
Sherstov degree/discrepancy, outline of group representations

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.)

Lecture 9: Friday, April 11, 2008
No class - FOCS deadline

Lecture 10: Friday, April 18, 2008
Applications of group representations

Dimension expanders, matrix multiplication.

Lecture notes by Moritz Hardt

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 11: Friday, April 25, 2008
Lattices I - definition, LLL, worst-case to average case

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 12: Friday, May 2, 2008
Lattices II - dual lattices, Fourier transform, transferance theorems, public key encryption

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.