Shor's Algorithm - polynomial-time quantum algorithm for factoring

## Saturday, November 18, 2017

## Wednesday, November 15, 2017

### Day 34

More quantum: Deutsch-Jozsa, Grover and Simon

- Rapid solution of problems by quantum computation by David Deutsch and Richard Jozsa
- A fast quantum mechanical algorithm for database search by Lov Grover
- On the Power of Quantum Computation by Dan Simon

## Monday, November 13, 2017

### Day 33

Introduction to Quantum Computing. Gave the matrix definition of quantum machines (see my paper below) and described the Hadamard matrix and its properties.

- One complexity theorist's view of quantum computing by Lance Fortnow

## Friday, November 10, 2017

### Day 32

In this class we showed how MIP = NEXP implies lower bounds on approximating the clique problem and how this led to the PCP theorem. The PCP theorem states that every language in NP has probabilistically checkable proof where the verifier uses O(log n) random bits and makes only a constant number of queries to a proof that just returns bit. Here is a strong version.

For any constant α > 7/8, there is a polynomial-time computable function f mapping 3-CNFs to 3-CNFs such that for all formula φ,

For any constant α > 7/8, there is a polynomial-time computable function f mapping 3-CNFs to 3-CNFs such that for all formula φ,

- If φ is satisfiable then f(φ) is satisfiable.
- If φ is not satisfiable then every assignment to f(φ) satisfies at most an α-fraction of the clauses.

The proof is an assignment, O(log n) random coins are used to pick a clause and only the 3-queries to the variables of that clause are needed.

We also talked about the Unique Games conjecture.

Links:

- Interactive proofs and the hardness of approximating cliques by Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra and Mario Szegedy
- Proof verification and the hardness of approximation problems by Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan and Mario Szegedy. First proof of the PCP theorem.
- The PCP theorem by gap amplification by Irit Dinur. A simpler more combinatorial proof of the PCP theorem.
- Some optimal inapproximability results by Johan Håstad. Gets the tight result for 3-SAT above.
- On the power of unique 2-prover 1-round games by Subhash Khot. This paper introduces unique games.
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs? by Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell
- Compendium of NP Optimization Problems. Good list of problems and their best known approximations and limitations.

## Wednesday, November 8, 2017

### Day 31

Assignment 3 has been graded and solutions posted on the T-Square resource page. Assignment 4 has been posted and is due November 20.

We showed that MIP (in PCP form) was equal to NEXP.

We showed that MIP (in PCP form) was equal to NEXP.

- Non-deterministic exponential time has two-prover interactive protocols by László Babai, Lance Fortnow and Carsten Lund
- Robust Characterizations of Polynomials with Applications to Program Testing by Ronitt Rubinfeld and Madhu Sudan. This is a more direct and robust low-degree test.

## Monday, November 6, 2017

### Day 30

We showed that IP = PSPACE via the Shen proof and introduced the MIP model.

- IP = PSPACE by Adi Shamir
- IP =PSPACE: Simplified proof by Alexander Shen
- On the power of multi-prover interactive protocols by Lance Fortnow, John Rompel and Michael Sipser

## Friday, November 3, 2017

### Day 29

We gave the proof that co-NP and P

^{#P}have interactive protocols (Arthur-Merlin games with unbounded rounds). We will generalize to PSPACE on Monday.- Algebraic methods for interactive proof systems by Carsten Lund, Lance Fortnow, Howard Karloff and Noam Nisan

## Wednesday, November 1, 2017

### Day 28

We proved Toda's theorem that PH is in P

Along the way we needed:

^{#P}.Along the way we needed:

- NP in BPP
^{⊕P}(follows from Valiant-Vazirani discussed last class) - ⊕P
^{⊕P}= ⊕P (Papadimitrious Zachos) - NP in BPP implies PH in BPP (Assignment 3)

Links

- PP is as Hard as the Polynomial-Time Hierarchy by Seinsuke Toda
- A Simple Proof of Toda's Theorem by Lance Fortnow
- Two remarks on the power of counting by Christos Papadimitriou and Stathis Zachos

## Monday, October 30, 2017

### Day 27

We discussed closure properties of #P functions, some basic counting classes and the proof of Valiant Vazirani.

Let f(x,y) be a #P function and r(x) a polynomial-time computable function bounded by a polynomial in |x|.

Let f(x,y) be a #P function and r(x) a polynomial-time computable function bounded by a polynomial in |x|.

- The sum of f(x,y) for all y with |y| = r(x) is in #P.
- The product of f(x,y) for all y with 1 ≤ y ≤ r(x) is in #P.
- (f(x,0) choose r(x)) is in #P.

L is in PP if there is a #P function f and a polynomial-time computable r such that

- x in L implies f(x) ≥ r(x)
- x not in L implies f(x) < r(x).

L is in ⊕P if there is a #P function f such that

- x in L implies f(x) is odd
- x not in L implies f(x) is even

L is in UP if there is a #P function f such that

- x in L implies f(x) = 1
- x not in L implies f(x) = 0

We also proved the Valiant-Vazirani theorem: There is a polynomial q and a probabilistic polynomial-time function f mapping CNF formulas to CNF formulas such that

- If φ is not satisfiable then f(φ) is never satisfiable.
- If φ is satisfiable then with probability at least 1/q(n), f(φ) has a unique satisfying assignment.

Link:

- NP is as easy as detecting unique solutions by Les Valiant and Vijay Vazirani. We gave Noam Ta-Shma's proof of Mulmuley-Vazirani-Vazirani isolation lemma. See also my blog post.

## Friday, October 27, 2017

### Day 26

Avi Wigderson, one of the giants of computational complexity, has released a PDF draft of his new book Mathematics and Computation. The book gives a philosophical and technical overview though a number of topics in computational complexity. Definitely worth downloading and reading if you are interested in the material in this course.

Today we proved Valiant's theorem that the permanent of a matrix is #P-complete.

- The complexity of computing the permanent by Les Valiant
- #P-Completeness Via Many-One Reductions by Viktória Zankó. This paper gives a direct reduction from permanent with exponentially large weights to the permanent of a 0-1 matrix.

## Wednesday, October 25, 2017

### Day 25

Showed that AM in Π

This implies that if Graph Isomorphism is NP-complete then PH collapses to Σ

Introduced counting complexity, #P and the Permanent.

A function f:{0,1}

The permanent of a matrix A is the sum over all permutations s of a

_{2}^{P}and MA in Σ_{2}^{P}∩Π_{2}^{P}and if AM is in co-NP then PH collapses to Σ_{2}^{P}.This implies that if Graph Isomorphism is NP-complete then PH collapses to Σ

_{2}^{P}.Introduced counting complexity, #P and the Permanent.

A function f:{0,1}

^{*}→ℕ is in #P if there is an NP machine M such that f(x) = the number of accepting paths of M(x).The permanent of a matrix A is the sum over all permutations s of a

_{1s(1)}...a_{ns(n)}.## Friday, October 20, 2017

## Wednesday, October 18, 2017

### Day 23

Assignment 3 has been posted on T-Square and due November 1. Assignment 2 grades have been released. Solutions to assignment 2 will be posted in the T-Square resources shortly.

Started our unit on Arthur-Merlin games.

Defined AM and gave the private-coin protocol for graph non-isomorphism and informally described the public coin protocol. We'll do a detailed public-coin protocol on Friday.

Started our unit on Arthur-Merlin games.

Defined AM and gave the private-coin protocol for graph non-isomorphism and informally described the public coin protocol. We'll do a detailed public-coin protocol on Friday.

- Arthur-Merlin on Wikipedia
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes by László Babai and Shlomo Moran.
- Proofs that yield nothing but their validity and a methodology of cryptographic protocol design by Oded Goldreich, Silvio Micali and Avi Wigderson. Among other things this paper gives the first Arthur-Merlin protocol for graph isomorphism.
- Private coins versus public coins in interactive proof systems by Shafi Goldwasser and Michael Sipser
- Graph Isomorphism in Quasipolynomial Time by László Babai

## Monday, October 16, 2017

### Day 22

Today we did the Schwartz-Zippel lemma and used it to give a co-RP algorithm for polynomial identity-testing.

We also showed that BPP is in P/poly and in Σ

Links:

We also showed that BPP is in P/poly and in Σ

^{P}_{2}∪Π^{P}_{2}.Links:

- Fast Probabilistic Algorithms for Verification of Polynomial Identities by Jack Schwartz
- Probabilistic algorithms for sparse polynomials by Richard Zippel
- Two theorems on random polynomial time by Len Adleman. Shows that BPP is in P/poly.
- A complexity theoretic approach to randomness by Michael Sipser and BPP and the polynomial hierarchy by Clemens Lautemann. Show BPP in Σ
^{P}_{2}∪Π^{P}_{2} - Wikipedia articles (with good definitions and proofs) for BPP, Schwartz-Zippel, Polynomial Identity-Testing and BPP in Σ
^{P}_{2}∪Π^{P}_{2}.

## Friday, October 13, 2017

### Day 21

We did the proof of the Chernoff Bounds. Here is a detailed write-up.

We also discussed the polynomial identity testing question: Given a polynomial p(x1,...,xn) described by a circuit of product and sum gates, is that polynomial exactly zero?

To give a probabilistic algorithm for polynomial identity testing we looked at the Schwartz-Zippel lemma and gave part of the proof.

We also discussed the polynomial identity testing question: Given a polynomial p(x1,...,xn) described by a circuit of product and sum gates, is that polynomial exactly zero?

To give a probabilistic algorithm for polynomial identity testing we looked at the Schwartz-Zippel lemma and gave part of the proof.

## Wednesday, October 11, 2017

### Day 20

We introduced probabilistic Turing machines and talked about the classes BPP, RP and ZPP.

A language is in BPP if there is a probabilistic polynomial-time Turing machine such that for all x,

A language is in RP if there is a probabilistic polynomial-time Turing machine such that for all x,

A language is in BPP if there is a probabilistic polynomial-time Turing machine such that for all x,

- If x is in L then the probability that M(x) accepts is at least 2/3.
- If x is not in L then the probability that M(x) accepts is at most 1/3.

A language is in RP if there is a probabilistic polynomial-time Turing machine such that for all x,

- If x is in L then the probability that M(x) accepts is at least 1/2.
- If x is not in L then the probability that M(x) accepts is 0.

A language is in ZPP if there is a probabilistic

*expected*polynomial-time Turing machine such that for all x,- If x is in L then the probability that M(x) accepts is 1.
- If x is not in L then the probability that M(x) accepts is 0.

We sketched why Composite testing is in RP and used Chernoff bounds to reduce the error in probabilistic algorithms to exponentially small. The exact statement of Chernoff bounds I gave in class was incorrect--we'll revisit on Friday.

Links:

- Computational Complexity of Probabilistic Turing Machines by John Gill. Defined the basic complexity classes.
- Miller-Rabin primality test - An RP algorithm for composite testing works even when you have Carmichael numbers.
- Primes in P by Agrawal, Kayal and Saxena

## Friday, October 6, 2017

### Day 19

Finished proof of Razborov-Smolensky. Links in Day 18 post.

Kannan's non-constructive proof that Σ

Links:

Kannan's non-constructive proof that Σ

^{p}_{2}does not have n^{k}-size circuit for any constant k.Links:

- Circuit-size lower bounds and non-reducibility to sparse sets by Ravi Kannan
- Blog post on Kannan's result

## Wednesday, October 4, 2017

### Day 18

First half of Razborov-Smolensky proof that depth d circuits of Mod

Links:

_{3}, AND, OR and NOT gates computing parity must have an exponential number of gates.Links:

- We've been following the proof in Boppana-Sipser
- Algebraic methods in the theory of lower bounds for Boolean circuit complexity by Roman Smolensky
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition by Alexander Razborov

## Monday, October 2, 2017

### Day 17

P-complete sets including Monotone Circuit Value: Given a circuit of just AND/OR gates with variables set to the constants TRUE and FALSE, will the circuit evaluate to TRUE?

The major results in circuit complexity:

The major results in circuit complexity:

- Parity requires exponential-size circuits.
- For distinct primes p and q, there is no polynomial-size constant-depth circuit with AND, OR, NOT and Mod
_{p}gates that can compute the Mod_{q}function. - Clique and Matching do not have polynomial-size monotone circuits even with arbitrary depth.
- *NEXP does not have constant-depth circuits with Mod
_{m}gates for any fixed m, prime or composite.

- The Complexity of Finite Functions by Ravi Boppana and Michael Sipser. A wonderful survey that covers definitions, results, proofs and references of the major circuit functions (except * which came after this survey).
- Nonuniform ACC Circuit Lower Bounds by Ryan Williams. This is the paper proving *.

## Friday, September 29, 2017

### Day 16

Karp-Lipton result that if SAT has a polynomial-size circuit family then PH = Σ

Definitions of circuit complexity classes (NC

Links:

^{p}_{2}.Definitions of circuit complexity classes (NC

^{i}, AC^{i}). NC^{i}is the set of languages accepted by poly-size O(log^{i}n) depth with bounded fan-in. AC^{i}circuits are the same with no restriction on fan-in.Links:

- Some connections between nonuniform and uniform complexity classes by Richard Karp and Richard Lipton.
- Wikipedia article on Karp-Lipton with proof.
- Wikipedia article on NC

## Wednesday, September 27, 2017

## Monday, September 25, 2017

### Day 14

Defined quantified Boolean formula and showed that TQBF, the set of true quantified Boolean formula, is PSPACE-complete.

Assignment 1 has been graded. Average score is 62. Solutions are posted to the resources section of the T-Square site. Assignment 2 will be handed out Wednesday.

Links:

Assignment 1 has been graded. Average score is 62. Solutions are posted to the resources section of the T-Square site. Assignment 2 will be handed out Wednesday.

Links:

- Alternation by Chandra, Kozen and Stockmeyer. This is the paper that showed the equivalence of alternating polynomial time and PSPACE and my other relationships.
- Nice write-up of proof that TQBF is PSPACE-complete via Joan Feigenbaum.

## Friday, September 22, 2017

### Day 13

We talked about the three definitions of the polynomial-time hierarchy, by oracles, alternation and quantification, and the basic properties.

- The equivalence problem for regular expressions with squaring requires exponential space by Albert Meyer and Larry Stockmeyer. This is the paper that first defined the polynomial-time hierarchy.
- The wikipedia article on the polynomial-time hierarchy goes through all three definitions and the basic relationships.
- Completeness in the Polynomial-Time Hierarchy by Marcus Schaefer and Chris Umans. A compendium of problems complete for various higher levels of the hierarchy.

## Wednesday, September 20, 2017

### Day 12

Guest lecture from Venkat.

Defined polynomial-time hierarchy in terns of oracle TMs and stated some simple facts about the hierarchy. Defined alternating Turing machines. Started the proof of the characterization of polynomial-time hierarchy using alternating Turing machines.

Details and links will come in next post.

Defined polynomial-time hierarchy in terns of oracle TMs and stated some simple facts about the hierarchy. Defined alternating Turing machines. Started the proof of the characterization of polynomial-time hierarchy using alternating Turing machines.

Details and links will come in next post.

## Monday, September 18, 2017

### Day 11

Finished proof of Immerman-Szelepcsényi. Links in last post.

Defined oracle Turing machines and the Baker-Gill-Solovay result that there exist oracles A and B such that

Relativizations of the P =? NP Question by Baker, Gill and Solovay
You can simply take A to be any PSPACE-complete problem. For B, here is a good write-up.

Defined oracle Turing machines and the Baker-Gill-Solovay result that there exist oracles A and B such that

- P
^{A}= NP^{A} - P
^{B}≠ NP^{B}

## Friday, September 15, 2017

### Day 10

Today we covered the complements of languages and co-classes and did most of the proof of the Immerman-Szelepcsényi theorem that non-deterministic space is closed under complement. In particular we focused on the proof that NL = co-NL

Definitions:

Definitions:

- The complement of a language L, denoted L, is the set of strings not in L.
- For a complexity class C, we define co-C as the set of languages L for L in C.

Links:

- My writeup of Immerman-Szelepcsényi
- Nondeterministic Space is Closed under Complementation by Neil Immerman
- The method of forced enumeration for nondeterministic automata by Róbert Szelepcsényi

## Wednesday, September 13, 2017

### Day 9

We looked at deterministic and nondeterministic space complexity and showed the basic relationships:

DTIME(f(n)) ⊆ NTIME(f(n)) ⊆ DSPACE(f(n)) ⊆ NSPACE(f(n)) ⊆ ∪

DTIME(f(n)) ⊆ NTIME(f(n)) ⊆ DSPACE(f(n)) ⊆ NSPACE(f(n)) ⊆ ∪

_{c}DTIME(c^{f(n)})
We also proved Savitch's theorem that NSPACE(s(n)) is contained in DSPACE(s

^{2}(n)).
Links:

- Relationships between nondeterministic and deterministic tape complexities by Walter Savitch
- My writeups of Space Complexity and Savitch's Theorem

## Friday, September 8, 2017

### Day 8

Assignment 1, due Monday, September 18, has been posted on T-Square. I highly recommend you start thinking about the problems immediately.

The Berman-Hartmanis Isomorphism Conjecture states that all NP-complete sets are polynomial-time isomorphic to each other. The conjecture is still open.

Let Σ

We say a set S is dense if for some ε>0, |S∩Σ

We showed in class that if the Berman-Hartmanis conjecture is true then every NP-complete set is dense. In paticular under this assumption there are no sparse or finite NP-complete sets and P ≠ NP.

The Berman-Hartmanis conjecture remains open but Mahaney proved the following: If there is a sparse NP-complete set then P = NP. In class we gave the proof of Ogihara and Watanabe which I also wrote up in my blog.

The Berman-Hartmanis Isomorphism Conjecture states that all NP-complete sets are polynomial-time isomorphic to each other. The conjecture is still open.

Let Σ

^{n}be the set of all strings of length n and Σ^{≤n}be the set of all strings of length at most n.We say a set S is dense if for some ε>0, |S∩Σ

^{≤n}| ≥ 2^{nε}for all n. A set S is sparse if for some c, |S∩Σ^{n}|≤ n^{c}. Every finite set is sparse and no dense set is sparse.We showed in class that if the Berman-Hartmanis conjecture is true then every NP-complete set is dense. In paticular under this assumption there are no sparse or finite NP-complete sets and P ≠ NP.

The Berman-Hartmanis conjecture remains open but Mahaney proved the following: If there is a sparse NP-complete set then P = NP. In class we gave the proof of Ogihara and Watanabe which I also wrote up in my blog.

## Wednesday, September 6, 2017

### Day 7

The Cantor-Bernstein Theorem states that for any two arbitrary sets A and B if there are 1-1 functions from A to B and B to A then there is a 1-1 and onto function from A to B. How does this carry into complexity?

Two sets of strings A and B are polynomial-time isomorphic if there is a function f:Σ

We define A to be paddable if there is a function h:Σ

Two sets of strings A and B are polynomial-time isomorphic if there is a function f:Σ

^{*}→Σ^{*}- f is computable in polynomial time
- The inverse of f is computable in polynomial time
- f reduces A to B (x in A iff f(x) in B)
- f is 1-1
- f is onto

We say f is a length-increasing invertible reduction if there is a f:Σ

^{*}→Σ^{*}- f is computable in polynomial time
- The inverse of f is computable in polynomial time
- f is 1-1
- f is length-increasing, i.e., |f(x)| > |x| for all strings x.

^{*}×Σ^{*}→Σ^{*}- h is computable in polynomial time
- For all x,y, x is in A iff h(x,y) is in A
- For all y, |h(x,y)| > |y|
- For all x, y and y' with y≠y', h(x,y)≠h(x,y')
- There is a polynomial-time computable function g s.t. for all x,y, g(h(x,y))=y

- Every A in NP reduces to Satisfiability via a 1-1 length-increasing reduction.
- If B reduces to a paddable set A then there is a reduction from B to A that is length-increasing and invertible.
- If A and B reduce to each other via length-increasing invertible reductions then they are isomorphic.

Essentially all the commonly known NP-complete problems are paddable and thus isomorphic to Satisfiability and each other.

## Friday, September 1, 2017

## Wednesday, August 30, 2017

### Day 5

Finished proof of Cook's theorem. Talked about potential NP-incomplete problems such as Graph Isomorphism, recently shown in quasipolynomial time by Laszlo Babai.

## Monday, August 28, 2017

## Friday, August 25, 2017

### Day 3

Reducibility and NP-Completeness

Papers:

Papers:

- Steve Cook, The Complexity of Theorem-Proving Procedure
- Defined the P v NP problem and showed SAT is NP-complete
- Richard Karp, Reducibility Among Combinatorial Problems
- Shows 21 combinatorial problems NP-complete
- Michael Garey and David Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness
- The reference for NP-completeness. Every computer scientist should own this book.

## Wednesday, August 23, 2017

### Day 2

More introduction to computation, Turing Machines and time complexity. Defined P and briefly NP.

Papers mentioned:

Alan Turing, On Computable Numbers, with an Application to the Entscheidungsproblem

Where he defines the Turing machine. Section 9 is worth reading where he basically defends his thesis that this model defines computability.

Juris Hartmanis and Richard Stearns, On the Computational Complexity of Algorithms

This paper started the field of computational complexity. It's major insight was to consider resources like time and memory as a function of the input size.

Jack Edmonds, Paths, Trees and Flowers

This paper gives a polynomial-time algorithm for graph matching and argues that polynomial-time is a reasonable stand in for efficient computation.

Alan Cobham, The Intrinsic Computational Difficulty of Functions

Cobham gave a similar argument for polynomial time.

Papers mentioned:

Alan Turing, On Computable Numbers, with an Application to the Entscheidungsproblem

Where he defines the Turing machine. Section 9 is worth reading where he basically defends his thesis that this model defines computability.

Juris Hartmanis and Richard Stearns, On the Computational Complexity of Algorithms

This paper started the field of computational complexity. It's major insight was to consider resources like time and memory as a function of the input size.

Jack Edmonds, Paths, Trees and Flowers

This paper gives a polynomial-time algorithm for graph matching and argues that polynomial-time is a reasonable stand in for efficient computation.

Alan Cobham, The Intrinsic Computational Difficulty of Functions

Cobham gave a similar argument for polynomial time.

## Monday, August 21, 2017

### Day 1

Guest lecture by Venkat.

Covered basics of Turing Machines, Complexity Classes and Polynomial Time.

Reminder that Assignment 0 is due Friday. Download and submit on T-Square.

Covered basics of Turing Machines, Complexity Classes and Polynomial Time.

Reminder that Assignment 0 is due Friday. Download and submit on T-Square.

## Friday, June 9, 2017

### Course Overview

CS 6520 Computational Complexity

Fall 2017

Instructor: Lance Fortnow

Time: MWF 9:05-9:55

**Room:**Whitaker Biomedical Engineering 1103

Description: This course will give an overview of advanced topics in computational
complexity including the P versus NP problem, the structure of NP, the
polynomial-time hierarchy, circuit complexity, randomness, counting,
interactive and probabilistically checkable proofs.

Detailed list of topics

Detailed list of topics

Prerequisites: A strong mathematical background and a basic knowledge of Turing machines and the P v NP problem at the level of CS 4510. This is a course meant for advanced students with a strong interest in theoretical computer science--if you just want to fulfill the graduate theory requirement you should take CS 6505.

Textbook: None. Computational Complexity by Arora and Barak cover much of the material from the course but we won't be following them.

Coursework: Assignments roughly every other week. This is a theoretical course and assignments will be problem solving and will not involve any programming. There are no exams.

**Course Website:**gtcc17.blogspot.com

Subscribe to:
Posts (Atom)