Questions tagged [interactive-proofs]
The interactive-proofs tag has no usage guidance.
1
vote
0answers
55 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 ...
1
vote
0answers
90 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 ...
3
votes
0answers
142 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 ...
8
votes
0answers
129 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 ...
0
votes
1answer
90 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 ...
7
votes
0answers
146 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 ...
2
votes
1answer
259 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 ...
8
votes
0answers
116 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
vote
0answers
154 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.
6
votes
0answers
192 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 ...
7
votes
1answer
293 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 ...
2
votes
0answers
64 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 ...
6
votes
0answers
135 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.
...
4
votes
0answers
121 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 ...
3
votes
0answers
71 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 ...
4
votes
0answers
72 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....
0
votes
0answers
76 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
vote
0answers
128 views
Learning theory vs. Interactive Proofs
Is there any connection between Interactive proofs and learning theory?
2
votes
1answer
134 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}(...
1
vote
1answer
166 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.
...
2
votes
0answers
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 ...
3
votes
1answer
454 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
995 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: ...
4
votes
3answers
458 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 ...
6
votes
2answers
191 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,...
15
votes
3answers
440 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 ...
10
votes
1answer
406 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
139 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 ...
14
votes
2answers
677 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
181 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
299 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 ...
14
votes
0answers
208 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 ...
18
votes
1answer
830 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}...
13
votes
1answer
205 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
642 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
360 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
299 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
539 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
1k 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
509 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
506 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 ...
11
votes
2answers
568 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 ...
8
votes
1answer
774 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
784 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 ...
33
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 ...
13
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
226 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 ...
17
votes
2answers
593 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 ...
