6.842 Randomness and Computation, Fall 2017

6.842 Randomness and Computation (Fall 2017)

Time: MW 11:00-12:30

Place: 4-261

Announcements:

Fourth homework is posted! (see below)

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

(09/06) Lecture 1: Introduction. The probabilistic method (examples: hypergraph coloring, sum-free subsets). Begin the Lovasz Local Lemma? [scanned notes] and [scribe notes]
(09/11) Lecture 2: The Lovasz Local Lemma. Example: hypergraph coloring revisited. Moser-Tardos Algorithm for finding solutions guaranteed by LLL. [scanned notes] and [scribe notes]
(09/13) Lecture 3: Finish Moser-Tardos Algorithm. (see handwritten notes from last time) and [scribe notes] [latex]
(09/18) Lecture 4: Randomized complexity classes. Derandomization via enumeration. Pairwise independence and derandomization (example: max-cut). [scanned notes] and [scribe notes] [latex]
(09/20) Lecture 5: Pairwise independent hash functions. 2-point sampling. Interactive proofs. The class IP. Graph nonisomorphism is in IP. [scanned notes] and [scribe notes] [latex]
(09/25) Lecture 6: IP models with public versus private coins. A protocol for lower bounding the size of the set (using pairwise independent hashing). [scanned notes] [scribe notes] [lec6-7-scribe notes]
(09/27) Lecture 7: Continued last lecture. [lec6-7-scribe notes]
(10/1) Lecture 8: Derandomizing via the method of conditional expectations. Intro to Markov chains and random walks on graphs. [scanned notes]
(10/4) Lecture 9: Random Walks, Stationary Distribution, Cover Times. [scanned notes] [scribe notes]
(10/11) Lecture 10: times (continued). Undirected st-connectivity is in RL. Linear algebra and mixing times. Saving randomness via random walks. [scanned notes] [scribe notes] latex
(10/16/) Lecture 11: Reducing Randomness via Random Walks on Special Graphs [scanned notes] [scribe notes]
(10/18) Lecture 12: Undirected S-T Conn revisited (deterministic logspace) [scanned notes] [scribe notes] [latex]
(10/23) Lecture 13: Szemeredi's Regularity Lemma; Testing dense graph property of triangle-freeness [scanned notes]
(10/25) Lecture 14: Testing triangle-freeness [scanned notes] [scribe notes] [latex]
(10/30) Lecture 15: Linearity Testing, Self-Correcting, Begin Fourier Analysis of Boolean Functions [scanned notes]
(11/6) Lecture 16: Begin learning (see lec 18 for notes)
(11/8) Lecture 17: The low degree algorithm (see lec 18 for notes), Fourier concentration
(11/13) Lecture 18: Noise sensitivity and Fourier Concentration. Linear Threshold functions. [scanned notes]
(11/15) Lecture 19: Learning large Fourier coefficients. [scanned notes]
(11/20) Lecture 20 (Lecture 19 Continued): Learning large Fourier coefficients. [scanned notes]
(11/22) Lecture 21: Weakly learning monotone functions [scanned notes] [scribe notes]
(11/27) Lecture 22: Weak vs. strong learning, boosting [scanned notes] [scribe notes] [latex] [preamble-latex]
(11/29) Lecture 23: (Lecture 22 continued): Weak vs. strong learning, boosting [scanned notes]
(12/4) Lecture 24: (Lecture 22 continued): Weak vs. strong learning, boosting [scanned notes]
(12/6) Lecture 25: Amplifying hardness. Yao's XOR lemma [scanned notes] [scribe notes] [latex]
(12/11) Lecture 26: NP has probabilistically checkable proof systems requiring only constant queries[scanned notes]

Homework

Homework 1. Posted September 11, 10am. Last update September 11, 10am. Due September 18. NOTE: ONE WEEK EXTENSION ON PROBLEM 3! Problem 3 now due on September 25. Hint for problem 1. Solutions: problem 1. problem 2.

problem 3.

Homework 2. Posted September 18, 2017 at 11:12am. Due September 25, 2017. Hint for problem 2. Solutions: problem 2.
Homework 3. Posted September 25, 2017 at 11:22am. Last update October 1, 8:00pm. Due October 2, 2017 Hint for problem 2. Solutions: problem 1. problem 2.
Homework 4. Posted October 4, 2017 at 3:30pm. Due October 11. Hint. Solutions: problem 1
Homework 5. Posted October 18, 2017. Due October 25. EXTENSION ON PROBLEM 2 to October 30. Last update October 24, 6:30 pm. Hint for problem 2. Solutions: problem 1 problem 2
Homework 6. Solutions: problem 1 problem 1 (latex) problem 2 problem 3 problem 3 (latex) Posted October 30, 2017. Due November 13.
Homework 7. Posted November 21, 2017. Due December 4.

Useful information

(9/5) 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.
Instructions for graders.