Questions tagged [interactive-proofs]
The interactive-proofs tag has no usage guidance.
62
questions
0
votes
0
answers
67
views
Interactive proofs with computation bounded Merlin
Consider usual interactive proofs (Arthur is polynomial-time bounded and can use random bits)
where computation power of Merlin is bounded by polynomial-size circuits.
For example, every unary NP-...
- 1,695
0
votes
0
answers
35
views
Using error-correcting codes in multi-player games
There is a connection between any two from error-correcting codes, interactive schemes, and PCP. For quantum works, I found papers such as JV15 & Ji15. And there are classical examples about 20 ...
- 193
1
vote
1
answer
159
views
Graph associated to a mathematical statement (for the purpose of zero-knowledge proofs)
I'll preface this question by saying I have very little (zero!) knowledge of theoretical computer science, and this post is a genuine attempt to understand something, even if at an intuitive level, ...
1
vote
0
answers
198
views
IP, MIP and MIP* with super-polynomial verifier
Regarding each of the above classes, what are the currently known upper bounds when the verifier is given more than polynomial power?
Specifically, when do we reach ALL in each of the above classes ...
- 1,526
1
vote
1
answer
124
views
Quantum complexity of TQBF with an untrusted oracle
This is a follow up to Quantum complexity of TQBF, trying to model the situation where we have good heuristics.
Let $L$ be the language of true, fully alternating totally quantified boolean formulas ...
- 3,221
5
votes
0
answers
190
views
Why can MIP be restricted to just two provers?
In several places I see it referred to that the MIP class can be assumed to be two interactive provers that don't communicate with each other, rather than any polynomial number of provers. Why are ...
- 256
11
votes
0
answers
275
views
Does MIP* = RE algebrize?
Does the MIP* = RE result algebrize? (It doesn’t relativize, as noted here.)
If it doesn’t algebrize, is there a more complicated similar notion that it does satisfy?
- 3,221
7
votes
0
answers
117
views
Is finding square roots as hard as factoring, when coins are *public* and the square root oracle is adversarial?
Background: There is a well known argument (due to Rabin) that demonstrates that if one has access to an machine that computes square roots of elements in $\mathbb{Z}_n$, with $n = pq$, then $n$ can ...
- 1,429
8
votes
1
answer
606
views
Does the MIP* = RE proof work for limited provers?
MIP* = RE shows that two arbitrarily strong entangled provers can convince a verifier of instances of the halting problem. Now assume that we have two entangled provers that are only capable of ...
- 3,221
2
votes
2
answers
578
views
If $P=BPP$, then Is it correct that $IP=NP$?
This is my first question in this site. I ask this question since I got no comment and no answer for one year and two months in cs.stackexchange and it was automatically deleted by the system. So, ...
- 171
6
votes
1
answer
133
views
Separation of AM and SZK
Are any results on the separation of AM from SZK known (e.g. relativized separation, or a separation assuming one-way functions exist, etc.)?
- 63
2
votes
1
answer
69
views
QPIP minimal client quantum capabilities
It is conjectured that classical (BPP) client blind quantum computing is implausible according to Aaronson et al:
https://www.researchgate.net/publication/...
- 1,526
11
votes
0
answers
176
views
$\exists \mathbb R$ and IP
We know NP$\subseteq$ $\exists \mathbb R$$\subseteq$ PSPACE=IP, but is there some more direct proof for $\exists \mathbb R\subseteq$ IP?
What about the other direction, are there some Arthur-Merlin ...
- 13.7k
2
votes
0
answers
88
views
What is the computational complexity of determining the mixing time of a Cayley graph?
Bayer and Diaconis famously proved that a deck of fifty-two cards will be mixed after only seven dovetail shuffles. Numberphile has a nice series of videos of Diaconis explaining the proof.
I ...
- 852
1
vote
0
answers
107
views
An explicit hard function for P/poly
It is known that $\textbf{MA}_{\textbf{EXP}} \not\subset \textbf{P/poly}$. Is it known any explicit language from $\textbf{MA}_{\textbf{EXP}}$ that does not belongs to $\textbf{P/poly}$?
(An example ...
- 1,695
3
votes
0
answers
297
views
On "The Power of the Prover" in Arora and Barak
In section 8.4 of Arora and Barak, after describing the public coin protocol for $\mathsf{GNI}$ and $\mathrm{IP=PSPACE}$, the authors state:
A curious feature of many known interactive proof systems ...
- 852
8
votes
0
answers
150
views
Practical interactive proof schemes for NP-hard problems
Model-checking (in the sense of reachability in a succinct graph) is PSPACE-complete. SAT is NP-complete. Both problems are considered intractable, yet there exist tools capable of solving them on ...
- 1,112
0
votes
1
answer
133
views
is Zero knowledge Proof same as commitment schemes? [closed]
I am studying about the zero knowledge proofs and I am looking for a practical (example based) approach to undrestand its process. I have studied the theory a little bit and I find it interesting yet ...
- 101
6
votes
0
answers
170
views
Is $IP$ only interesting because of the equality to $PSPACE$?
I try to understand the advantages of using a probabilistic polynomial-time verifier instead of an determininistic one. I use as literature "Arora, Barak: Computational Complexity", in which the class ...
- 161
4
votes
1
answer
677
views
Simulating quantum measurements by unitaries
I have seen many papers in which quantum measurements are assumed to be replaced by unitaries. See this quotation from [KW00] for instance:
Often we will describe quantum circuits in a high-level ...
- 293
7
votes
0
answers
123
views
What can we say about AM[log n]?
It is known that $\textbf{AM}[O(1)] = \textbf{AM}$.
Since $\textbf{IP}=\textbf{PSPACE}$ we have $\textbf{AM}[poly(n)] = \textbf{PSPACE}$.
Can we say something about $\textbf{AM}[ f(n)]$, where $f$ ...
- 1,695
1
vote
0
answers
159
views
Examples of problems in $\mathsf{IP}$
What are some examples problems with a direct proof that they are in $\mathsf{IP}$, other than Graph Non-Isomphism?
I have been looking for a while, but no luck so far.
- 11
5
votes
0
answers
201
views
Easy interactive proofs for easy problems?
Motivation
Consider some $L \subseteq \{0,1\}^*$. Suppose Alice gives Bob a machine or oracle $M$ that purportedly decides $L$. If Bob has only polynomial time in their disposal, then they cannot ...
- 2,161
6
votes
1
answer
370
views
Parity P and AM
What is known about non-trivial inclusions of $\oplus\mathsf{P}$ in other classes?
In particular, is it known whether $\oplus\mathsf{P}$ is contained in $\mathsf{AM}$?
The same questions apply to the ...
- 1,695
2
votes
0
answers
76
views
Are there non-trivial MIP protocols with initially-independent verifiers?
My impression is that for standard constructions of MIP ("Multiple Independent Prover") protocols, the verifiers must have shared randomness. What happens if the verifiers are
also independent ...
user6973
6
votes
0
answers
137
views
Does it matter who begins communication in $IP(f(x))$?
Consider $IP(f(x))$, in other words, the class of languages that admit a private coin protocol $(P, V)$ running in $f(x)$ rounds (often in terms of the size of $x$), satisfying standard constraints.
...
- 1,102
4
votes
0
answers
126
views
major applied focuses of different proof assistants
Currently, what are the major applied focuses (if any applications can be deserved such a distinction) of different proof assistants, such as the following? If there are significant differences ...
- 523
3
votes
0
answers
72
views
Resource tradeoffs in interactive proofs
In an interactive proof, there are a number of resources that can be traded off against each other. For example, verifier time, verifier space (as per this question), amount of randomness used, number ...
- 31.8k
4
votes
0
answers
104
views
Is perfect zero knowledge sequentially composable without auxiliary input?
It is known that plain and computational zero knowledge proof systems are not sequentially composable without auxiliary input (see for example http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1....
- 41
0
votes
0
answers
84
views
Understanding MA protocol as a variant of TM for small space setting
MA protocol is one of the most basic models of interactive proofs.
Merlin is a prover sending a witness $w$ for given input string $x$, and Arthur is a verifier who verifies if $w$ is a positive ...
- 1
1
vote
0
answers
138
views
Learning theory vs. Interactive Proofs
Is there any connection between Interactive proofs and learning theory?
- 476
2
votes
1
answer
165
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
$\operatorname{states}(...
user6973
1
vote
1
answer
209
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.
...
user6973
2
votes
1
answer
1k
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 ...
- 697
3
votes
1
answer
491
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 ...
- 697
4
votes
3
answers
1k
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: ...
- 143
4
votes
3
answers
517
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 ...
- 51
6
votes
2
answers
201
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 players,...
user887
18
votes
3
answers
555
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 ...
- 705
10
votes
1
answer
512
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 \...
- 476
6
votes
0
answers
193
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 ...
- 3,647
14
votes
2
answers
788
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 ...
- 12.4k
11
votes
0
answers
189
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 ...
- 4,319
13
votes
0
answers
302
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 ...
- 3,647
15
votes
1
answer
295
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 ...
- 8,841
21
votes
1
answer
1k
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 coNP}...
- 3,708
13
votes
1
answer
237
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 $\...
- 415
13
votes
1
answer
841
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 ...
- 13.5k
2
votes
1
answer
436
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
...
- 185
11
votes
1
answer
338
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.
...
- 463