Math 583 Probabilistic and Interactive Proofs

University of Michigan, Winter, 2015


Can we be convinced that a proof is correct, even if we only check it in three places? Can a proof convince us that a statement is true, while giving us no aid in convincing anyone else that the statement is true? The answer to both is affirmative. How? Using randomness and interaction, two elements missing from traditional deductive proofs. Why? Checking a proof in just a few places is useful for checking computer-generated proofs that are too long to read (an example bigdata algorithm); there are also surprising connections to showing that certain functions cannot be computed or even approximated efficiently. A "zero-knowledge proof" might be used, for example, for a customer to prove to a merchant that the customer is the rightful owner of a credit card, without giving the merchant any ability to prove (fraudulently) that the merchant is the owner of that credit card.

Other topics

We will also look at IP=PSPACE: converting a game, G, to another, G', such that if Peggy beats any expert in G, then she beats any expert in G'; if Peggy loses to an expert in G, she loses to a random (non-expert) player in G'. Thus the prover Peggy can convince a non-expert verifier Victor that she wins G, even though the game tree is too big for Victor to read. We will also look at Multi-prover Interactive Proof systems and show that they are more powerful than single-prover systems, answering the question posed so eloquently by Professor Click and the late Professor Clack: Do two people who don't know what they are talking about know more or less than one person who doesn't know what he's talking about?

Student Body

Graduate students and advanced undergraduates in Math, Computer Science, and Philosophy. Students should have an interest in theoretical computer science, logic, randomized algorithms and graphs, and/or proofs and knowledge.

Note for CS Majors:

It turns out that this course is unlikely to be approved for ULCS credit, for a variety of reasons. But it may still count toward the 26 hours of Flexible Technical electives required of CoE-CS majors. I'm now investigating that.

I am investigating offering this as a 4-credit class that counts toward 16 points of Upper Level CS required for the major. Tentatively, if you choose this option, you would be expected (in addition to other requirments) to attend office hours for one hour per week on average and to do an extra project or assignment of some sort, proportional to the extra credit hour.

So far, I have not sought approval for this. Please contact me if you are interested and I'll do the approval process on behalf of the lot of you.


Probabilistically-checkable proofs, zero-knowledge proofs, and interactive proofs are studied and their computational, cryptographic, and other advantages discussed. The course will include, as modules, a presentation of the necessary background material, which (it turns out) are important tools for many other topics in discrete math and theoretical computer science. These modules include the Chernoff tail bound and other topics from probability theory, error-correcting codes, expander graphs, and randomized computation. Motivations and applications in other fields, such as secure computation and the philosophical nature of proof and knowledge, are briefly discussed.


None. Readings and handouts provided.

Expected work

Students will transcribe lecture notes and present papers.

Contact Martin Strauss, martinjs, with questions.