# Questions tagged [interactive-proofs]

The tag has no usage guidance.

69 questions
Filter by
Sorted by
Tagged with
105 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 ...
• 576
1 vote
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 ...
• 111
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 ...
125 views

• 143
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 ...
• 51
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,...
787 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 ...
• 725
558 views

• 3,707
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 ...
• 12.6k