Lectures 1 and 2 of John Watrous' lecture notes
Monday, November 30, 2015
Monday, November 23, 2015
Lecture 40
Remember to enter your CIOS comments for this course and all your courses.
Laszlo Babai's first talk on his new graph isomorphism algorithm is now on video. Babai is an excellent lecturer and I highly recommend finding 100 minutes to watch the talk.
Today we covered time-space tradeoffs for SAT from the papers:
Time-space tradeoffs for satisfiability by L. Fortnow. .
Time-space lower bounds for satisfiability by L. Fortnow, R. Lipton, D. van Melkebeek, and A. Viglas.
Laszlo Babai's first talk on his new graph isomorphism algorithm is now on video. Babai is an excellent lecturer and I highly recommend finding 100 minutes to watch the talk.
Today we covered time-space tradeoffs for SAT from the papers:
Time-space tradeoffs for satisfiability by L. Fortnow. .
Time-space lower bounds for satisfiability by L. Fortnow, R. Lipton, D. van Melkebeek, and A. Viglas.
Friday, November 20, 2015
Lecture 39
Assignment 4, our last assignment, has been posted to T-Square and is due on Wednesday, December 2 at 8 PM. There will be no final exam.
Arefin Huq covered zero-knowledge for Sudoku from the paper Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku Puzzles by Ronen Gradwohl, Moni Naor, Benny Pinkas and Guy N. Rothblum.
He also discussed bit commitment and presented the zero-knowledge proof for graph isomorphism, comparing and contrasting with the Arthur-Merlin protocol for graph non-isomorphism.
Arefin Huq covered zero-knowledge for Sudoku from the paper Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku Puzzles by Ronen Gradwohl, Moni Naor, Benny Pinkas and Guy N. Rothblum.
He also discussed bit commitment and presented the zero-knowledge proof for graph isomorphism, comparing and contrasting with the Arthur-Merlin protocol for graph non-isomorphism.
Wednesday, November 18, 2015
Lecture 38
Conclude lecture series on PCP theorem with Proof of BLR test and PCP systems for quadratic-SAT.
Monday, November 16, 2015
Friday, November 13, 2015
Wednesday, November 11, 2015
Lecture 35
A sketch of the proof of the amplification lemma (Lemma 6.1 in Dinur). Introduction to the assignment tester.
Monday, November 9, 2015
Lecture 34
Second part of prep that converts bounded degree regular graph to an expander with self-loops (Definition 4.3 and Lemma 4.4 of Dinur).
Construction of Graph Powering for Amplification step (follows after Theorem 1.7 in Dinur).
Construction of Graph Powering for Amplification step (follows after Theorem 1.7 in Dinur).
Friday, November 6, 2015
Wednesday, November 4, 2015
Lecture 32
Continuation of PCP proof. Laid out the three lemmas: Preprocessing (Lemma 1.9 in Dinur's paper), Amplification and Composition. Gave construction of the first phase of the preprocessing lemma (Def 4.1).
Monday, November 2, 2015
Lecture 31
We have begun working through Irit Dinur's proof of the PCP theorem by gap amplification. Today we defined constraint graphs, stated the main theorem (Theorem 1.7) and defined expander graphs (Section 2.1).
Subscribe to:
Posts (Atom)