The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
0answers
92 views

Learning theory vs. Interactive Proofs

Is there any connection between Interactive proofs and learning theory?
1
vote
0answers
59 views

Is there a version of MIP=NEXP with relatively efficient provers?

(My question is not a duplicate of this question.) Fix a good coding of non-deterministic random-access machines. For non-negative integers $m$ that code such a machine, let ...
2
votes
1answer
76 views

Is there a constructive parallel repetition theorem for nice MIP protocols?

Theorem 1.1 of Ran Raz's paper is a non-constructive upper bound on the soundness error of parallel repetitions of a 2-prover minimally minimally interactive proof system with perfect completeness. ...
1
vote
0answers
214 views

From CHSH inequality to CHSH game

I have been going through Certifiable quantum dice: or, true random number generation secure against quantum adversaries by Umesh Vazirani and Thomas Vidick. They have used entangled particles as ...
3
votes
1answer
330 views

Is the D-Wave architecture a close implementation of quantum interactive proof?

A very high level architecture is, as mentioned here, shown in this picture. The component on the left is classical while the one on the right is the D-Wave box. I understand that in QIP, Arthur is ...
4
votes
3answers
439 views

NIZK proofs: Why is the prove function necessary?

In NIZK proofs, the prover can generate its proof for statement $y$ and witness $w$ using $$\pi \gets \mathrm{Prove}(\sigma,y,w)\text{,}$$ where $\sigma$ is the common reference string. Source: ...
3
votes
2answers
216 views

On definition of IP class

I'm a little bit lost with the actual definition of IP, some sources define as interaction between algorithms starting with Verifier, another one does not any put restriction on who send the first ...
7
votes
2answers
162 views

Delegating all of the work to the prover in $\mathcal{MA}$ protocols

An $\mathcal{MA}$ communication complexity protocol is communication complexity protocol that starts with an omniscient prover that sends a proof (that depends on the the specific input of the ...
15
votes
3answers
377 views

$\mathcal{MA}$ in terms of $\mathcal{PCP}$

The probabilistic proof system $\mathcal{PCP}[f(n),g(n)]$ is commonly referred to as a restriction of $\mathcal{MA}$, where Arthur can only use $f(n)$ random bits and can only examine $g(n)$ bits of ...
9
votes
1answer
310 views

One-sided errors in probablistic proof systems

In most probabilistic proof systems ( PCP theorem, for instance), the error-probabilities are usually defined on the side of the false-positives, i.e., a typical definition could look like : if $x ...
6
votes
0answers
119 views

The relation between NP and IP(2pfa)

As far as I know, it is not known whether $ \mathsf{NP} \subseteq \mathsf{IP(2pfa)} $, where $ \mathsf{IP(2pfa)} $ is the class of languages having interactive proof systems with some two-way ...
12
votes
2answers
523 views

Landscape of interactive proof systems

My first question is whether an interactive proof system characterisation is known for all the classic complexity classes. I would call P, NP, PSPACE, EXP, NEXP,EXPSPACE, recursive and recursively ...
11
votes
0answers
161 views

generalizing Ben-Or et al's two-prover bit commitment scheme beyond bits

In "Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions" by Ben-Or, Goldwasser, Kilian, and Wigderson, the authors introduce a bit commitment protocol as a subroutine to their ...
13
votes
0answers
284 views

Is there any known nontrivial result on QIP systems having a space-bounded verifier?

Is there any known nontrivial result on quantum interactive proof (QIP) systems having a space-bounded verifier? The only paper I know is An application of quantum finite automata to interactive ...
11
votes
0answers
180 views

Does requiring uniqueness of valid answers for Merlin limit the power of Arthur-Merlin protocols?

Preamble. The complexity class AM are those problems which can be solved by a two-round interactive proof system between a prover "Merlin" and a verifier "Arthur". A problem — which tests some ...
15
votes
1answer
465 views

What's the “real” reason that IP=PSPACE is non-relativizing?

IP=PSPACE is listed as the canonical example of a non-relativizing result, and the proof for this is that there exists an oracle $O$ such that ${\sf coNP}^O \not\subseteq {\sf IP}^O$, while ${\sf ...
12
votes
1answer
180 views

Is there a continuous version of parallel repetition theorem

Raz's Parallel pretition theorem is an important result in PCP, inapproximation, etc. The theorem is fomalized as follows. A game $G=(\mathcal{S},\mathcal{T},\mathcal{A},\mathcal{B},\pi, V)$, where ...
14
votes
1answer
415 views

What is known about multi-prover interactive proofs with short messages?

Beigi, Shor and Watrous have a very nice paper on the power of quantum interactive proofs with short messages. They consider three variants of 'short messages', and the specific one I care about is ...
2
votes
1answer
254 views

Arthur-Merlin protocol with BQP power

Context: Aaronson raised the following question: Let f be a black-box function, which is promised either to satisfy the Simon promise or to be one-to-one. Can a prover with the power of BQP ...
11
votes
1answer
215 views

The Equivalency of Two Definitions of Completeness & Soundness in Interactive Proof Systems

The completeness and soundness in interactive proof systems are informally defined as: Completeness: If a statement is true, the honest prover can convince the honest verifier of this fact w.h.p. ...
9
votes
3answers
480 views

Interactive Proofs via Postselection?

Define the computational model MPostBQP to be identical to PostBQP except we allow polynomially many qubit measurements before the post-selection and final measurement. Can we give any evidence ...
11
votes
3answers
725 views

Can Merlin convince Arthur about a certain sum?

Merlin, who has unbounded computational resources, wants to convince Arthur that $$m|\sum_{p\le N,\ p\text{ prime}}p^k$$ for $(N,m,k)$ with $k=O(\log N)$ and $m=O(N).$ Computing this sum in the ...
10
votes
1answer
389 views

Interactive Proof for HORN-SAT?

Is there a way that a prover can convince a verifier that some HORN-SAT expression is satisfiable? Of course this might seem silly, since there are linear time algorithms for HORN-SAT. On the other ...
7
votes
3answers
478 views

How are proofs verified probabilistically in interactive proof systems?

I'm having a hard time understanding the way Arthur verifies proofs probabilistically with coin tosses in an intuitive manner. Suppose Arthur is a logician equipped with paper, a pencil and an ...
10
votes
2answers
423 views

What is the Relationship between QMA and AM?

I read in S. P. Jordan, D. Gosset, P. J. Love's "$QMA$-complete problems for stoquastic Hamiltonians and Markov matrices" that it is unlikely that $QMA \subseteq AM$. I was surprised about this ...
4
votes
1answer
561 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 ...
17
votes
4answers
646 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 ...
30
votes
4answers
928 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 ...
30
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 ...
8
votes
1answer
2k 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. ...
8
votes
1answer
211 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 ...
14
votes
2answers
459 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 ...