![[Search]](/static/images/search.gif){kind=small}
![[A-Z Index]](/static/images/az.gif){kind=small}
![[Contact]](/static/images/contact.gif){kind=small}
![[University of Cambridge]](/static/images/identifier2.gif){kind=small}
![[Talks.cam]](/static/images/talkslogosmall.gif)
Wednesday 15 January 2020, 19:00-20:00
Proofs: From a Complexity Theoretic Perspective
- đ¤ Speaker: Jasper Lee ( Brown University)
- đ Date & Time: Wednesday 15 January 2020, 19:00 - 20:00
- đ Venue: Wolfson Hall, Churchill College
Abstract
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.
Series This talk is part of the Churchill CompSci Talks series.
Included in Lists
Note: Ex-directory lists are not shown.