# Questions tagged [interactive-proofs]

The tag has no usage guidance.

69 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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

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 ...
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,... 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 ...
556 views