Questions tagged [interactive-proof-systems]
The interactive-proof-systems tag has no summary.
62 questions
5
votes
1
answer
219
views
Basic question about parallel repetition in IP protocol
The book Arora and Barak defines class IP (interactive protocol) by making the verifier have private coins. Before proceeding to public coin proofs and showing they are the "same," the book ...
- 3,423
2
votes
1
answer
123
views
Interactive proof for graphs with no non-trivial automorphisms
I am looking for an interactive proof for the language $AUTO^C= \{𝐺∣\text{𝐺 is an undirected graph that has no non-trivial automorphisms}
\}$.
I am interested in a method similar to the interactive ...
- 21
3
votes
0
answers
56
views
Good book on (Quantum) Complexity and Computability Theories to start learning the theorem $MIP^* = RE$ as an operator algebraist
I am looking for some greatest references that could help me understand the theorem $MIP^* = RE$ ($MIP*=RE$) step by step. The paper (The Connes Embedding Problem: A guided tour) covers various ...
2
votes
0
answers
75
views
What's the intuition behind MIP* being bigger than MIP?
It is well-known that $\mathsf{MIP} = \mathsf{NEXPTIME}$, and recently there was a breakthrough stating that $\mathsf{MIP^*} = \mathsf{RE}$.
This was very confusing because it seemed like the (...
- 391
5
votes
1
answer
273
views
Easy proof of IP ⊆ PSPACE for private coins
There is an extremely standard proof that IP⊆PSPACE, used for instance here, here, or here, by the argument that the full protocol is max-avg game tree that can be evaluated in polynomial space. It's ...
- 955
1
vote
1
answer
102
views
GNI public coin interactive proof: why randomize y?
I've read this scribe that provides a public coin interactive proof for graph non-isomorphism.
In the proof, the verifier samples both a pairwise-independent hash function and a target $y$. Then it ...
- 13
0
votes
1
answer
107
views
Sumcheck protocol - how are these 2 polynomials different?
I am going through Justin Thaler's book - https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf - "Proofs, Arguments, and Zero-Knowledge"
He is describing the Sumcheck Protocol on ...
- 125
2
votes
0
answers
187
views
How to prove MIP is in NEXP
I was trying to understand the proof of MIP is inside NEXP. I was referring to Rutger's university scribes (link). They define MIP as a class with exponential proof, but that is not the definition I ...
- 243
1
vote
1
answer
71
views
Exponential sized graph 3-coloring is in MIP
I was watching a talk by Anand Natarajan on $\text{NEEXP} \subseteq \text{MIP*}$, and he uses $\text{3-coloring}$ as an example problem for $\text{NEXP} = \text{MIP}$ (timestamp 3:50). He mentioned ...
- 243
0
votes
1
answer
225
views
How to start with verifying a formal proof programmatically?
I heard the terms "theorem provers" and "proof assistants" tossed around before (which I assumed to be the same up until a couple seconds ago), and also of Coq, Idris, Agda, TLA+ (...
- 105
2
votes
1
answer
101
views
is $IP=BPP^{NP}$
In the class $IP$ we have a probabilistic polytime verifier which interacts with a nondeterministic prover polynomial times and all the messages are of length polynomial of the input. We can think of ...
- 145
5
votes
0
answers
76
views
Interactive proof for PSPACE-hard problems different from QBF
The celebrated proof that IP = PSPACE relies on an interactive proof for the QBF problem.
Is there any other "natural" interactive proof for a PSPACE-hard problem other than QBF?
(of course, ...
2
votes
0
answers
90
views
How does the standard proof that IP is in PSPACE apply to, say, the graph non-isomorphism problem?
I learned years ago that $IP \subseteq PSPACE$ since you could simulate all sets of messages and then determine the probability of success. But lately I’ve been looking at the standard proof of this ...
- 53
1
vote
1
answer
189
views
Are there any known interactive proof protocols for NP-complete problems?
In a 2015 Quanta article talking about a breakthrough in the graph isomorphism problem, it was mentioned that graph isomorphism has a unique property where we have an interactive proof protocol for it....
- 341
1
vote
1
answer
99
views
Are there any NP-complete problems that are also in IP?
I am wondering if anyone knows if there are any NP-complete problems that are also known to be in IP (interactive polynomial time). I know problems like Graph Isomorphism are in IP, but such problems ...
- 341