Hope for a Type-Theoretic Understanding of Zero-Knowledge
Noam Zeilberger
IMDEA Software Institute; Member, School of Mathematics
October 4, 2012
We discuss a quantum counterpart, in the sense of the Berezin-Toeplitz quantization, of certain constraints on Poisson brackets coming from "hard" symplectic geometry. It turns out that they can be interpreted in terms of the quantum noise of observables in operational quantum mechanics.
I will give an introduction to the problem of parallel repetition of two-prover games and its applications and related results in theoretical computer science (the PCP theorem, hardness of approximation), mathematics (the geometry of foams, tiling the space R^n) and, if time allows, physics (Bell inequalities, the EPR paradox).