Questions tagged [interactive-proofs]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
13
votes
2answers
992 views

An Interactive Proof of God's Number?

I've been learning about interactive proofs lately and I've been wondering if the whole thing was nothing more than a theoretical curiosity, or if it had any practical applications. I thought I'd ...
18
votes
4answers
841 views

If P = BQP, does this imply that PSPACE (= IP) = AM?

Recently, Watrous et al proved that QIP(3) = PSPACE a remarkable result. This was a surprising result to myself to say the least and it set me off thinking... I wondered what if Quantum Computers ...
35
votes
4answers
1k views

Interactive proofs for levels of the polynomial hierarchy

We know that if you have a PSPACE machine, it's powerful enough to give an interactive proof of any level the polynomial hierarchy. (And if I remember right, all you need is #P.) But suppose you want ...
31
votes
1answer
1k views

Refereed games with uncorrelated semi-private coins

I was (and still am) really interested in the answer to this question, because this is an interesting variation on the complexity of games which hasn't been resolved, so I offered a bounty. I thought ...
14
votes
1answer
5k views

How to define a function inductively on two arguments in Coq?

How can I convince Coq that the recursive function given below terminates? The function takes two inductive arguments. Intuitively, the recursion terminates because either argument is decomposed. ...
9
votes
1answer
245 views

closure properties of IP(2pfa) and AM(2pfa)

IP(2pfa) and AM(2pfa) are the classes of languages recognized with bounded error by private and public coin versions, respectively, of interactive proof systems with verifiers that are probabilistic ...
19
votes
2answers
663 views

MIP with efficient provers

It is well-known that the set of languages having two-prover interactive proof systems, in which the verifier runs in polynomial-time (MIP), is NEXP. But are there bounds known on the power of such ...

1
2