You are currently browsing the monthly archive for April 2010.

Today we prove the Valiant-Vazirani theorem.

Theorem 1 (Valiant-Vazirani) Suppose there is a polynomial time algorithm that on input a CNF formula having exactly one satisfying assignment finds that assignment. (We make no assumption on the behaviour of the algorithm on other inputs.) Then ${{\bf NP}={\bf RP}}$.

In this lecture we prove the Karp-Lipton theorem that if all NP problems have polynomial size circuits then the polynomial hierarchy collapses. A nice application is a theorem of Kannan, showing that, for every ${k}$, there are languages in ${\Sigma_2}$ requiring circuits of size ${\Omega(n^k)}$. The next result we wish to prove is that all approximate combinatorial counting problem can be solved within the polynomial hierarchy. Before introducing counting problems and the hashing techniques that will yield this result, we prove the Valiant-Vazirani theorem that solving SAT on instances with exactly one satisfying assignment is as hard as solving SAT in general.

Last revised 4/29/2010

In this lecture, we first continue to talk about polynomial hierarchy. Then we prove the Gács-Sipser-Lautemann theorem that BPP is contained in the second level of the hierarchy.

Today we show how to reduce the error probability of probabilistic algorithms, prove Adleman’s theorem that polynomial time probabilistic algorithms can be simulated by polynomial size circuits, and we give the definition of the polynomial hierarchy

In this lecture we introduce the computational model of boolean circuits and prove that polynomial size circuits can simulate all polynomial time computations. We also begin to talk about randomized algorithms.

Last revised 4/29/2010

In this lecture we define ${{\bf NP}}$, we state the ${{\bf P}}$ versus ${{\bf NP}}$ problem, we prove that its formulation for search problems is equivalent to its formulation for decision problems, and we prove the time hierarchy theorem, which remains essentially the only known theorem which allows to show that certain problems are not in ${{\bf P}}$.

Last revised 4/29/2010

This course assumes CS154, or an equivalent course on automata, computability and computational complexity, as a prerequisite. We will assume that the reader is familiar with the notions of algorithm, running time, and of polynomial time reduction, as well as with basic notions of discrete math and probability. We will occasionally refer to Turing machines.

In this lecture we give an (incomplete) overview of the field of Computational Complexity and of the topics covered by this course.

Ten minutes to go and only 262 submissions.

CS254, the new Stanford graduate course on computational complexity started this week.

It is a condensed version of my Berkeley course in only 17 lectures (plus two lectures on quantum complexity theory). Watch this space for the lecture notes.

The submission server for FOCS 2010 is now open for business at https://secure.iacr.org/websubrev/focs2010/submit/.

You have until Wednesday, April 7, 8pm PST San Francisco time.