Last lecture of the fall :(

We covered Shor's algorithm for factoring numbers in quantum polynomial time, best explained in his paper.

# CS 6520 - Computational Complexity Fall 2015

## Friday, December 4, 2015

## Wednesday, December 2, 2015

### Lecture 42

Quantum Algorithms: Deutsch-Jozsa, Simon, Grover

John Watrous lecture notes, Lecture 5, 6, 12 and 13.

John Watrous lecture notes, Lecture 5, 6, 12 and 13.

## Monday, November 30, 2015

### Lecture 41

Introduction to Quantum Computing: Basic quantum transformations and definition of BQP.

Lectures 1 and 2 of John Watrous' lecture notes

## 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

Subscribe to:
Posts (Atom)