University of Cambridge > Talks.cam > Churchill CompSci Talks > Proofs: From a Complexity Theoretic Perspective

Proofs: From a Complexity Theoretic Perspective

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Matthew Ireland.

How much effort and communication should it take for a prover to convince an intelligent verifier of the truth of a mathematical fact? Can a verifier be convinced without learning anything about why the statement is true? Orthogonally, can the prover demonstrate not only that the statement is true, but the prover herself knows why?

These are all questions centring around the notion of “proof”, which has been a vibrant research area amongst complexity theorists. In this talk, we discuss what the word “proof” can mean, and survey some of the most important ideas in the area, including 1) Probabilistically Checkable Proofs, 2) Zero-Knowledge Proofs and 3) Proofs of Knowledge.

This talk is part of the Churchill CompSci Talks series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2020 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity