Proofs: From a Complexity Theoretic Perspective

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

• Jasper Lee ( Brown University)
• Wednesday 15 January 2020, 19:00-20:00
• Wolfson Hall, Churchill College.

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.

This talk is included in these lists:

• Churchill CompSci Talks
• Wolfson Hall, Churchill College
• computer science
• se393's list

Note that ex-directory lists are not shown.