6.842 Randomness and Computation, Spring 2014

6.842 Randomness and Computation (Spring 2014)

Teaching Assistant: Badih Ghazi

Time: MW 1:00-2:30

Place: 36-112

Announcements:

Weekly Office Hours: Monday 3:00-4:00pm, Room 32-G531.

Brief Course description:

We study the power and sources of randomness in computation, concentrating on connections and applications to computational complexity, computational learning theory, cryptography and combinatorics. Topics include:

(1) Basic tools: probabilistic, proofs, Lovasz local lemma, uniform generation and approximate counting, Fourier analysis, influence of variables on functions, random walks, graph expansion, Szemeredi regularity lemma.

(2) Randomness vs. Predictability: pseudorandom generators, weak random sources, derandomization and recycling randomness, computational learning theory, Fourier based learning algorithms, weak vs. strong learning, boosting, average vs. worst case hardness, XOR lemma.

Lecture Notes

(02/05) Lecture 1: Introduction. The probabilistic method (examples: hypergraph coloring, sum-free subsets). Begin the Lovasz Local Lemma. [scanned notes] and [scribe notes]
(02/10) Lecture 2: The Lovasz Local Lemma. Example: hypergraph coloring revisited. Moser-Tardos Algorithm for finding solutions guaranteed by LLL. [scanned notes] and [scribe notes]
(02/12) Lecture 3: Randomized complexity classes. Derandomization via enumeration. Pairwise independence and derandomization (example: max-cut). [scanned notes] and [scribe notes]
(02/18) Lecture 4: Pairwise independent hash functions. A construction. 2-point sampling. Interactive proofs. The class IP. Graph nonisomorphism is in IP. [scanned notes] and [scribe notes]
(02/19) Lecture 5: IP models with public versus private coins. A protocol for lower bounding the size of the set (using pairwise independent hashing). Derandomizing via the method of conditional expectations. [scanned notes] and [scribe notes]
(02/24) Lecture 6: Intro to Markov chains and random walks on graphs. Stationary distributions. Cover times. [scanned notes] and [scribe notes]
(02/26) Lecture 7: Cover times (continued). Undirected st-connectivity is in RL. [scanned notes] and [scribe notes]
(03/03) Lecture 8: Linear algebra and mixing times. Saving randomness via random walks. [scanned notes] and [scribe notes]
(03/5) Lecture 9: s-t connectivity in deterministic logspace [scanned notes] and [scribe notes]
(03/10) Lecture 10: Szemeredi's Regularity Lemma; Application to testing triangle freeness in dense graphs. [scanned notes] and [scribe notes]
(03/12) Lecture 11: Fourier basics. Plancherel's and Parseval's theorems. Linearity testing. [slides] and [scribe notes]
(03/17) Lecture 12: Learning under the uniform distribution. Model. Brute force algorithm. Learning conjunctions. Estimating one Fourier coefficient. [scanned] and [scribe notes]
(03/19) Lecture 13: Fourier representations for basic functions. Learning via the Fourier representation -- the low degree algorithm. Applications of the low degree algorithm. Learning AC0 functions. [scanned] and [scribe notes]
(03/31) Lecture 14: Noise sensitivity and Fourier concentration. Applications to learning linear threshold functions. [scanned]
(04/02) Lecture 15: Learning parity with noise using queries: The Goldreich-Levin algorithm [scanned] and [scribe notes]
(04/07) Lecture 16: Weak learning of monotone functions. Begin strong learners from weak learners: Boosting algorithms. [scanned] and [scribe notes]
(04/09) Lecture 17: Continue boosting algorithms [scanned] and [scribe notes]
(04/14) Lecture 18: More Boosting. [scanned] and [scribe notes]
(04/16) Lecture 19: Boosting and complexity theory: Amplifying hardness. Yao's XOR lemma. [scanned] and [scribe notes]
(04/23) Lecture 20: Pseudorandomness. Computational Indistinguishability. [scanned] and [scribe notes]
(04/28) Lecture 21: Pseudorandomness. Computational Indistinguishability. (Continued) [scanned]
(04/30) Lecture 22: Pseudorandomness vs. next bit unpredictability. One way functions. [scanned]
(05/05) Lecture 23: One way permutations and pseudo-random generators. Hardcore bits. [scanned]
(05/07) Lecture 24: Hardness vs. randomness. The Nisan-Wigderson pseudo-random generator. [scanned]
(05/12) Lecture 25: Weak Random Sources. Randomness Extractors. [scanned]
(07/12) Lecture 26: Weak Random Sources. Randomness Extractors. (Continued) [scanned]

Homework

Homework 1. Posted February 4, 1pm. Last update February 4, 1pm. Due February 12.
Homework 2. Posted February 12, 10pm. Last update February 12, 10pm. Due February 19.
Homework 3. Posted February 19, 9pm. Last update February 19, 9pm. Due February 26.
Homework 4. Posted February 26, 8pm. Last update February 26, 8pm. Due March 5.
Homework 5. Posted March 5, 11pm. Last update March 11, 4pm. Due March 12.
Homework 6. Posted March 12, midnight. Last update March 13, 8pm. Due March 19.
Homework 7. Posted March 20, 4pm. Last update March 20, 4pm. Due April 2.
Homework 8. Posted April 3, 8pm. Last update April 3, 8pm. Due April 10.
Homework 9. Posted April 10, 10pm. Last update April 12, 1pm. Due April 17.
Homework 10. Posted April 21, 11pm. Last update April 22, 2pm. Due April 28.

Homework 11 (Optional).

Solutions

Useful information

(02/04) Course Information [pdf]
References on Markov, Chebyshev and tail inequalities:
- Avrim Blum's Handout on Tail inequalities.
- Avrim Blum's Handout on probabilistic inequalities.
Texts:
- Salil Vadhan's Pseudorandomness.
- Ryan O'Donnell's Analysis of Boolean Functions.
Information for scribes:
- Here is a sample file and the preamble.tex file that it uses. Please get a first draft to me within two days of the lecture. When using the definition environment, make sure to emphasize the term being defined.
- Here are some tips.

Stellar site

See this place in order to turn in homeworks!