Questions tagged [interactive-proofs]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
7 votes
0 answers
104 views

Why is showing lower bounds for AM communication complexity difficult?

One of the major open problems in communication complexity is to show interesting lower bounds for the Arthur-Merlin (AM) communication complexity of some natural problems (i.e., lower bounds of the ...
Naysh's user avatar
  • 576
1 vote
0 answers
74 views

Testing positivity of a function by an IP system?

We are given a polynomial function $f:\{0,1\}^n\to\mathbb{R}$ with $\text{deg}(f)\leq d$ ($d$ is constant), and $\epsilon>0$; $f$ here is presented by its coefficients (the degree is constant, so ...
qmww987's user avatar
  • 111
-1 votes
1 answer
83 views

Notation problem

The following problem arises when I try to define a new notation. I have a function f : A -> A -> A -> A -> Type Then I want special notation for the ...
coqbeginner's user avatar
2 votes
0 answers
125 views

Property testing for membership in span of vectors

Notation Let $\mathbb{F}$ be a finite field, and $m, n$ be natural numbers. An algorithm $A$ is said to have oracle access to a vector $v \in \mathbb{F}^n$ if it can query $v$ with input an index $i \...
Pratyush Mishra's user avatar
1 vote
0 answers
50 views

AM-protocol when Merlin does not know the input

In classical interactive protocols we assume that Merlin knows Arthur's input $x$. However we can consider a model where it is not a case. I think that this model is more powerful than classical. The ...
Alexey Milovanov's user avatar
1 vote
1 answer
86 views

Under what circumstances can a Prover in an Interactive Proof System simply simulate the Verifier?

I have read Arora, and Sipser chapters discussing IP, but have not seen mention of such a possibility. Given that a Prover is computationally unbounded is it not possible under certain circumstance ...
Ben Jenney's user avatar
7 votes
0 answers
159 views

MIP with bounded communication between provers

Are there any known results on the complexity class that is MIP except with independence of provers loosened to allow "limited classical communication" between provers: where total message ...
1110101001's user avatar
2 votes
0 answers
95 views

Non-interactive proof showing the multiplication of an encrypted matrix with a public vector is as claimed

Consider a "fantasy sports" setting where $m$ contestants each pick $k$ players from a set of $n$ players before a game. The state can be represented by a Boolean matrix $\mathbf{A}$ of size ...
Madhav Jha's user avatar
0 votes
0 answers
72 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-...
Alexey Milovanov's user avatar
1 vote
1 answer
171 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, ...
Emilio Ferrucci's user avatar
1 vote
0 answers
217 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 ...
Avi Tal's user avatar
  • 1,596
1 vote
1 answer
135 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 ...
Geoffrey Irving's user avatar
5 votes
0 answers
232 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 ...
lacker's user avatar
  • 256
11 votes
0 answers
291 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?
Geoffrey Irving's user avatar
7 votes
0 answers
123 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 ...
Areaperson's user avatar
  • 1,439
8 votes
1 answer
647 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 ...
Geoffrey Irving's user avatar
2 votes
2 answers
710 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, ...
user777's user avatar
  • 171
6 votes
1 answer
162 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.)?
wfawwer's user avatar
  • 63
2 votes
1 answer
71 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/...
Avi Tal's user avatar
  • 1,596
11 votes
0 answers
184 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 ...
domotorp's user avatar
  • 13.9k
2 votes
0 answers
97 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 ...
Mark S's user avatar
  • 1,063
1 vote
0 answers
111 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 ...
Alexey Milovanov's user avatar
3 votes
0 answers
302 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 ...
Mark S's user avatar
  • 1,063
8 votes
0 answers
160 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 ...
David Monniaux's user avatar
0 votes
1 answer
145 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 ...
picolo's user avatar
  • 101
6 votes
0 answers
173 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 ...
Burak's user avatar
  • 161
4 votes
1 answer
727 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 ...
permanganate's user avatar
7 votes
0 answers
124 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$ ...
Alexey Milovanov's user avatar
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.
Sefi Erlich's user avatar
5 votes
0 answers
203 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 ...
Vanessa's user avatar
  • 2,151
6 votes
1 answer
430 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 ...
Alexey Milovanov's user avatar
2 votes
0 answers
79 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 ...
user avatar
5 votes
0 answers
138 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. ...
Phylliida's user avatar
  • 1,132
4 votes
0 answers
127 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 ...
SorcererofDM's user avatar
3 votes
0 answers
75 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 ...
Suresh Venkat's user avatar
4 votes
0 answers
105 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....
amm's user avatar
  • 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 ...
huna's user avatar
  • 1
1 vote
0 answers
144 views

Learning theory vs. Interactive Proofs

Is there any connection between Interactive proofs and learning theory?
Arnab's user avatar
  • 476
2 votes
1 answer
177 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}(...
user avatar
1 vote
1 answer
218 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. ...
user avatar
3 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 ...
Omar Shehab's user avatar
3 votes
1 answer
501 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 ...
Omar Shehab's user avatar
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: ...
Johannes's user avatar
  • 143
4 votes
3 answers
532 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 ...
Yair's user avatar
  • 51
6 votes
2 answers
203 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,...
user avatar
20 votes
3 answers
782 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 ...
Belle's user avatar
  • 725
10 votes
1 answer
556 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 \...
Arnab's user avatar
  • 476
6 votes
0 answers
209 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 ...
Abuzer Yakaryilmaz's user avatar
14 votes
2 answers
824 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 ...
Vijay D's user avatar
  • 12.6k
11 votes
0 answers
190 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 ...
Noam Zeilberger's user avatar