Proof systems are fundamental notions in the theory of computation. How does quantum information impact the power of information-theoretic and cryptographic proofs? On the one hand, quantum adversaries may be able to implement new kinds of attacks, by executing quantum algorithms or leveraging quantum correlations. On the other hand, quantum information may enable efficiently verifying richer classes of languages, in the single-prover setting or in multi-prover setting.
This workshop will discuss the multi-faceted impacts that quantum information (and beyond) has on central notions of proofs studied in complexity and cryptography, including NP proofs, interactive proofs, zero-knowledge proofs, and probabilistically checkable proofs. The goal is to raise awareness about this rich area, through a tutorial day and two days of invited talks on recent research. The material will exemplify the impacts of taking a broad, physical perspective on the notion of proof.
The workshop will consist of three days, each consisting of 2-3 sessions of total length of 2.5 hours. The first day will be a tutorial day. The following two days will focus on cutting-edge results on the cryptographic and complexity-theoretic facets of quantum proofs. The first day of workshop is intended for equipping broad STOC audience with the necessary background, and the following two days will focus on recent research. All of the speakers mentioned below confirmed their participation.
To be announced shortly.