Please note: This seminar will take place in M3 4206 and virtually.
Roei Tell, Assistant Professor
Department of Computer and Mathematical Sciences, University of Toronto
Do efficient algorithms believe that NP = PSPACE? Under strong complexity-theoretic assumptions, we prove that every problem in PSPACE can be solved by an NP-type verifier running in polynomial time that looks correct to any efficient observer (i.e., it has computational soundness). For example, the PSPACE-complete problem TQBF can be decided by a polytime NP-type verifier V, interacting with an honest prover whose runtime is T(n) = 2^O(n), such that no adversary running in time poly(T) can find an input and a proof that mislead V (except with probability negligible in T over the adversary’s coins).
The proof uses recent techniques from non-black-box derandomization in order to compile the interactive proof system underlying IP = PSPACE into a deterministic (non-interactive) argument system. This is an instance from a broader set of results applying derandomization-based techniques and assumptions to instantiate (versions of) the Fiat-Shamir heuristic in cryptography, in the plain model and without (or with weak) cryptographic assumptions.
From an upcoming joint work with Lijie Chen and Ron Rothblum.