Math 583 Probabilistic and Interactive Proofs
University of Michigan, Winter, 2015
Description
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:
Update:
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.
Content
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.
Textbook
None. Readings and handouts provided.
Expected work
Students will transcribe lecture notes and present papers.
Contact Martin Strauss, martinjs, with questions.