<p>Just few remarks. First, I cannot quite see why we need a referee at all. 
If his/her function is known for the players, why then they cannot just simulate the
referee? Alice sends $m_A$ to Bob, he (without seeing $m_A$) computes 
$m_B$, after that he computes $f(m_A,m_B)$ and tells the result
to Alice. Perhaps you assume that $f_A$ is <em>not</em> known to Bob, and $f_B$ to Alice?
<p></p>

<p>Second, protocols related to linear inequalities are indeed interesting in
the context of cutting plane proofs. In this case, it is even enough to consider 
protocols, where the <b>form</b> of messages is <strong>very restricted</strong>: just values of
some linear combinations of input variables can be communicated. 
<p></p>

<p>To be a bit more precise, suppose we are
given a system of linear inequalities with integer coefficients. We know that
the system has no $0$-$1$ solution.  The variables are somehow split among the players
(in fifty-fifty manner); this is the "worst partition" scenario: the adversary can choose
the "worst" partition.
 Given a $0$-$1$ string, the goal of the players is to
find an unsatisfied inequality. That is, the answer is now not a single bit, but the
name of one inequality of our system. (This is a Karchmer-Wigderson type 
communication game.)</p>

<p><p>
Now consider the following restricted protocols for such a game:
(i) the referees function
if just $f(\alpha,\beta)=1$ iff $\alpha \leq \beta$, (ii) the messages
of players are restricted to <b>linear</b> ones: in each round, Alice
must send the message of the form $m_A(\vec{x})=\vec{c}\cdot \vec{x}$, and Bob
the message of the form  $m_B(\vec{y})=\vec{d}\cdot \vec{y}$. </p>

<p><p>
<a href="http://www.cs.toronto.edu/~toni/publications.html" rel="nofollow">Impagliazzo,  Pitassi and Urquhart (1994)</a> observed the following:
If all coefficients used in the cutting plane proofs 
are polynomial in the number of variables, and if this game needs $t$ bits of
communication, then every tree-like  proof of the unsatisfiability of the given system
must produce $\exp(t/\log n)$ inequalities. They then used known lower bounds
on communication complexity to give an explicit system requiring proofs of
exponential size. The disadvantage of this result is that the system 
is very <b>artificial</b>,
it corresponds to no "real" optimization problem. It is therefore an interesting
question to come up with a lower bound for a "real" optimization problems.
<p>
One of such problems is the Independent Set problem for graphs. Given a graph
$G=(V,E)$ we can associate with each vertex $u$ a variable $x_u$ and 
consider the system of inequalities consisting of the inequality
$\sum_{v\in V}x_v&gt;\alpha(G)$, and all inequalities $x_u+x_v\leq 1$ for all
edges $uv$ of $G$. Since every $0$-$1$ solution for the subsystem of these latter
inequalities gives an independent set in $G$, the entire system has no zero-one 
solutions. What is the communication 
complexity of the games for such systems?<br>
<p>
If our graph $=(L\cup R,E)$ 
is bipartite, then it is natural (for the adversary)
to split the variables according to its parts.
In this case, Alice gets a subset $A\subseteq L$, Bob a subset $B\subseteq R$
with the promise that $|A\cup B|&gt;\alpha(G)$. The goal is to find an edge between
$A$ and $B$. Here $\alpha(G)$ is the "bipartite" independence number: maximum size of an 
independent set not lying entirely in $L$ or in $R$.  One of my favorite problems is: 
Prove that $n\times n$ graphs requiring $\omega(\log^2 n)$ bits of communication <b>exist</b>. 
<p>
@Kaveh: Sorry for "answering" your question with questions.</p>

CC BY-SA 3.0
2011-12-07T19:14:05.497Z
I am more interested in the general cc framework than its known applications in proof complexity. The functions used by referee are known (they are fixed as I said). There are a number of issues why I am interested in this model but the main point is about how we are going to measure the amount of communication. If we are interested in total number of bits communicated then it is possible to simulate the protocol as you said. But if we want to consider some other measures of complexity like the number of rounds then I think it is different. For example, in one case that has been used in
Kaveh
CC BY-SA 3.0
2011-12-07T19:17:47.953Z
proof complexity each player sends a real number to the referee. A real number can encode infinitely many bits, so if you want to simulate this we have to send an infinite number of bits, and if we are allowing that then we can just send the whole input, so it becomes uninteresting. But counting the number of rounds in the framework with a referee we get a different measure that can be useful (as in Pavel Pudlak's proof).
Kaveh
CC BY-SA 3.0
2011-12-07T19:53:24.507Z
@Kaveh: Yes, it is sensible to what communication we count. But in the frame of cutting planes, we don't need to care about sending *real* numbers. Just assume that all coefficient are **integers** of $O(\log n)$ binary size ($n$ is the number of variables). Even **this** (restricted)  case is not clear, when wanting to get something for "real" optimization problems (like Independent Set). I am not a fun of getting lower bounds for "monster problems". People in proof complexity are usually satisfied by "monsters". But people in optimization theory would like to see "real" lower bounds.
Stasys
CC BY-SA 3.0
2011-12-07T20:03:05.160Z
these are a side issues, as I said I want to find out more about the kind of communication complexity I described in the question and intentionally avoided linking it to proof complexity and interpolations. There is nothing related to proof complexity in the statement of my question.
Kaveh
CC BY-SA 3.0
2011-12-07T20:32:31.637Z
@Kaveh: If referee's function **is** known to the players, I don't see the difference between these "referee protocols" and "no referee protocols" (if, as I said, numbers are small). The difference could occur if we would have just one round: players send their messages to the referee, and he makes a final decision. B.t.w. in the case of $k>2$ players, this is known as "simultaneous messages communication". About "monster problems". Here I think not about circuit complexity, but rather about problems which Optimization Theory is faced with.
Stasys
CC BY-SA 3.0
2011-12-07T22:22:01.167Z
let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/1936/discussion-between-kaveh-and-stasys-jukna)
Kaveh
CC BY-SA 3.0
2012-01-23T04:05:42.573Z
Can @StasysJukna or Kaveh post an update resulted from your chat, if there is any? I'm still confused on the type of measure Kaveh want and the difference between the models with and without referee (as why the referee cannot be simulated when you use the same measure on both models).
Dan
CC BY-SA 3.0
2011-12-07T18:16:54.753Z
2011-12-07T20:02:58.093Z
2011-12-07T20:02:58.093Z
Stasys
<p>I'm sure you know the following paper, but I put a link to it because other readers may be interested: <a href="http://www.karlin.mff.cuni.cz/~krajicek/game.ps">Interpolation by Games</a></p>

<p>This paper is an attempt to use the communication complexity framework to show lower bounds for cutting planes.  The protocol is used to produce an interpolant circuit for unsatisfiable CNF: 
$$
A(x,y)\lor B(x,z).
$$</p>

<p>Player $A$ gets input $a$ and $y^a$, player $B$ gets $b$ and $z^b$.  If there is a shallow tree-like proof in cutting planes then the two players have a communication protocol such that </p>

<ul>
<li>any communication is mediated by the referee, which helps in evaluating the inequalities in the proof;</li>
<li>the amount of communication is small (the tree is shallow);</li>
<li>the two players either decide which of $A$ or $B$ is falsified;</li>
<li>they find a position $i$ in which $a_i \not= b_i$.</li>
</ul>

<p>The referee is turned into a probabilistic protocol for inequalities.  In this way it is possible to turn lower bound for tree-like probabilistic protocols in the communication complexity framework into lower bound for tree-like cutting planes proofs.  </p>

<p>If we had lower bound for communication protocol of the form of a PLS, then we would get lower bound for dag-like cutting planes proofs.</p>

<p>Notice that this technique does not depend on the actual inference rules of cutting planes. If we assume the inference rules to be (1) positive combination (2) integer division with floor we can build the monotone interpolant circuit using Pavel Pudlák <a href="http://www.math.cas.cz/~pudlak/interpol.ps">argument</a>.</p>

CC BY-SA 3.0
2011-12-07T19:29:48.567Z
Actually I was trying to figure out if something more general than this has been studied in communication complexity, so I didn't mention the proof complexity lowerbounds and feasible interpolation not to bias the answers, but thanks. :)
Kaveh
CC BY-SA 3.0
2011-12-07T19:42:41.727Z
Yes, I thought that. But other readers of this forum may be interested and may get interested to proof complexity.
MassimoLauria
CC BY-SA 3.0
2011-12-06T22:21:02.453Z
2011-12-07T00:05:08.373Z
2011-12-07T00:05:08.373Z
MassimoLauria
<p>Assume a framework in communication complexity where we have two players A(lice) and B(ob) and a R(eferee). A and B don't communicate directly with each other. In each round of communication, each of them sends a message ($m_A$, $m_B$) to the R. R computes two functions $f_A(m_A,m_B)$ and $f_B(m_A,m_B)$ and sends the results to them. The functions are fixed. The idea is that the communication between the players is restricted. Moreover the referee might do some processing on the messages.</p>

<p><strong>Example:</strong></p>

<p>A and B send two (arbitrary large) numbers to R, R checks which of them is greater and informs the players. </p>

<p>In this framework, we can design a simple protocol that easily computes the following function using a single round. A and B send $x$ and $y$ to R, R returns the answer to them, and they output the answer.</p>

<p>$$f(x,y)= \begin{cases}0 &amp; x\leq y\\ 1 &amp; ow \end{cases}$$</p>

<p>Obviously this is not an interesting case, since the function we are computing is the same as the referee functions. A more interesting case is when we have a fixed linear inequality $\vec{a} \cdot \vec{x} \leq \vec{b} \cdot \vec{y}$ and the values for the variables are partitioned between players (A has $\vec{x}$ and B has $\vec{y}$). The task is to decide if the inequality is correct. The protocol in this case is that players compute their part and then send them to the referee. </p>

<p><strong>Question:</strong></p>

<p>Has this kind of communication complexity been studied? If yes where can I find more about this?</p>

<hr>

<p>note 1: on page 49 Kushilevitz and Nisan mention a framework which involves a referee but seems very different from what I am asking. </p>

<p>note 2: I am not sure if calling R a referee is the right thing, please comment if you have a better suggestion.</p>

CC BY-SA 3.0
2011-12-07T00:02:27.970Z
the model you are mentioning is called "Simultaneous Message Passing"
Marcos Villagra
CC BY-SA 3.0
2011-12-07T00:11:11.527Z
check this paper (http://arxiv.org/abs/quant-ph/0102001) and its references. In particular, check the papers by Ambainis, and Newman and Szegedy.
Marcos Villagra
CC BY-SA 3.0
2011-12-07T00:13:35.970Z
here is a more recent paper by Raoul Jahin http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5231456&abstractAccess=no&userType=inst
Marcos Villagra
CC BY-SA 3.0
2011-12-07T13:41:13.487Z
@MarcosVillagra: SMP is the same of Kaveh's Note 1, isn't it?
Alessandro Cosentino
CC BY-SA 3.0
2011-12-07T19:23:05.057Z
@Marcos, thanks, I will check them, but based on the abstracts it seems to me that SMP is different from what what I am describing. (I will try to come up with a better example to make it clear that the players are using R to communicate which can take several rounds.) ps: I think it would be better if you post these comments as an answer.
Kaveh
CC BY-SA 3.0
2011-12-08T00:37:40.103Z
aah yes indeed, in your model, if you allow only one round interaction, you get the SMP model. But you don't need to send back an asnwer to A and B. The referee can just output the answer. However, if you allow interactions between R and A/B (not between A and B) is very different, something like a "multi-round" SMP protocol. I need to think a little bit more about this.
Marcos Villagra
CC BY-SA 3.0
2011-12-08T00:40:23.390Z
maybe @HartmutKlauck can shed some light
Marcos Villagra
CC BY-SA 3.0
2011-12-08T00:53:23.870Z
maybe you don't need a multi-round protocol, with one round is enough. Just a thought but, I think you can reduce this multi-round protocol to the SMP model if you always keep the restriction where A and B don't interact and assuming as you put it that the functions $f_B$ and $f_A$ are known by A and B. Instead of sending the messages to R, just let A and B compute the functions. Then the referee could receive the answer from A and B and then make a final decision based on another function and output the answer.
Marcos Villagra
CC BY-SA 3.0
2011-12-08T15:15:37.247Z
@Marcos, but they cannot compute the functions because they depend on the messages of both player. The main issue is the measure of communication complexity doesn't need to be the total number of bits but only the number of rounds. I don't see what this would correspond to a lowerbound on the number of rounds in the SMP case, if A sends her input to B then no more communication is needed, but with a referee this can be impossible to do in a single or even $O(1)$ rounds.
Kaveh
<cc.complexity-theory><reference-request><communication-complexity>
Communication complexity with a referee
Kaveh
# Communication complexity with a referee

(Asked by: username_0 on 2011-12-06)

Assume a framework in communication complexity where we have two players A(lice) and B(ob) and a R(eferee). A and B don't communicate directly with each other. In each round of communication, each of them sends a message ($m\_A$, $m\_B$) to the R. R computes two functions $f\_A(m\_A,m\_B)$ and $f\_B(m\_A,m\_B)$ and sends the results to them. The functions are fixed. The idea is that the communication between the players is restricted. Moreover the referee might do some processing on the messages.

**Example:**

A and B send two (arbitrary large) numbers to R, R checks which of them is greater and informs the players.

In this framework, we can design a simple protocol that easily computes the following function using a single round. A and B send $x$ and $y$ to R, R returns the answer to them, and they output the answer.

$$f(x,y)= \begin{cases}0 & x\leq y\\ 1 & ow \end{cases}$$

Obviously this is not an interesting case, since the function we are computing is the same as the referee functions. A more interesting case is when we have a fixed linear inequality $\vec{a} \cdot \vec{x} \leq \vec{b} \cdot \vec{y}$ and the values for the variables are partitioned between players (A has $\vec{x}$ and B has $\vec{y}$). The task is to decide if the inequality is correct. The protocol in this case is that players compute their part and then send them to the referee.

**Question:**

Has this kind of communication complexity been studied? If yes where can I find more about this?

---

note 1: on page 49 Kushilevitz and Nisan mention a framework which involves a referee but seems very different from what I am asking.

note 2: I am not sure if calling R a referee is the right thing, please comment if you have a better suggestion.

**Tags:** cc.complexity-theory, reference-request, communication-complexity

> **Comments:**
> **username_1**: the model you are mentioning is called "Simultaneous Message Passing"  
> **username_1**: check this paper (http://arxiv.org/abs/quant-ph/0102001) and its references. In particular, check the papers by Ambainis, and Newman and Szegedy.  
> **username_1**: here is a more recent paper by Raoul Jahin http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5231456&abstractAccess=no&userType=inst  
> **username_2**: @MarcosVillagra: SMP is the same of username_0's Note 1, isn't it?  
> **username_0**: @Marcos, thanks, I will check them, but based on the abstracts it seems to me that SMP is different from what what I am describing. (I will try to come up with a better example to make it clear that the players are using R to communicate which can take several rounds.) ps: I think it would be better if you post these comments as an answer.  
> **username_1**: aah yes indeed, in your model, if you allow only one round interaction, you get the SMP model. But you don't need to send back an asnwer to A and B. The referee can just output the answer. However, if you allow interactions between R and A/B (not between A and B) is very different, something like a "multi-round" SMP protocol. I need to think a little bit more about this.  
> **username_1**: maybe @HartmutKlauck can shed some light  
> **username_1**: maybe you don't need a multi-round protocol, with one round is enough. Just a thought but, I think you can reduce this multi-round protocol to the SMP model if you always keep the restriction where A and B don't interact and assuming as you put it that the functions $f_B$ and $f_A$ are known by A and B. Instead of sending the messages to R, just let A and B compute the functions. Then the referee could receive the answer from A and B and then make a final decision based on another function and output the answer.  
> **username_0**: @Marcos, but they cannot compute the functions because they depend on the messages of both player. The main issue is the measure of communication complexity doesn't need to be the total number of bits but only the number of rounds. I don't see what this would correspond to a lowerbound on the number of rounds in the SMP case, if A sends her input to B then no more communication is needed, but with a referee this can be impossible to do in a single or even $O(1)$ rounds.  

---

## 2 answers

### Answer by username_5 on 2011-12-06. Score: 7 | Accepted answer

I'm sure you know the following paper, but I put a link to it because other readers may be interested: [Interpolation by Games](http://www.karlin.mff.cuni.cz/~krajicek/game.ps)

This paper is an attempt to use the communication complexity framework to show lower bounds for cutting planes. The protocol is used to produce an interpolant circuit for unsatisfiable CNF:
$$
A(x,y)\lor B(x,z).
$$

Player $A$ gets input $a$ and $y^a$, player $B$ gets $b$ and $z^b$. If there is a shallow tree-like proof in cutting planes then the two players have a communication protocol such that

* any communication is mediated by the referee, which helps in evaluating the inequalities in the proof;
* the amount of communication is small (the tree is shallow);
* the two players either decide which of $A$ or $B$ is falsified;
* they find a position $i$ in which $a\_i \not= b\_i$.

The referee is turned into a probabilistic protocol for inequalities. In this way it is possible to turn lower bound for tree-like probabilistic protocols in the communication complexity framework into lower bound for tree-like cutting planes proofs.

If we had lower bound for communication protocol of the form of a PLS, then we would get lower bound for dag-like cutting planes proofs.

Notice that this technique does not depend on the actual inference rules of cutting planes. If we assume the inference rules to be (1) positive combination (2) integer division with floor we can build the monotone interpolant circuit using Pavel Pudlák [argument](http://www.math.cas.cz/~pudlak/interpol.ps).

> **Comments:**
> **username_0**: Actually I was trying to figure out if something more general than this has been studied in communication complexity, so I didn't mention the proof complexity lowerbounds and feasible interpolation not to bias the answers, but thanks. :)  
> **username_5**: Yes, I thought that. But other readers of this forum may be interested and may get interested to proof complexity.  

---

### Answer by username_3 on 2011-12-07. Score: 5

Just few remarks. First, I cannot quite see why we need a referee at all.
If his/her function is known for the players, why then they cannot just simulate the
referee? Alice sends $m\_A$ to Bob, he (without seeing $m\_A$) computes
$m\_B$, after that he computes $f(m\_A,m\_B)$ and tells the result
to Alice. Perhaps you assume that $f\_A$ is *not* known to Bob, and $f\_B$ to Alice?

Second, protocols related to linear inequalities are indeed interesting in
the context of cutting plane proofs. In this case, it is even enough to consider
protocols, where the **form** of messages is **very restricted**: just values of
some linear combinations of input variables can be communicated.

To be a bit more precise, suppose we are
given a system of linear inequalities with integer coefficients. We know that
the system has no $0$-$1$ solution. The variables are somehow split among the players
(in fifty-fifty manner); this is the "worst partition" scenario: the adversary can choose
the "worst" partition.
Given a $0$-$1$ string, the goal of the players is to
find an unsatisfied inequality. That is, the answer is now not a single bit, but the
name of one inequality of our system. (This is a Karchmer-Wigderson type
communication game.)

Now consider the following restricted protocols for such a game:
(i) the referees function
if just $f(\alpha,\beta)=1$ iff $\alpha \leq \beta$, (ii) the messages
of players are restricted to **linear** ones: in each round, Alice
must send the message of the form $m\_A(\vec{x})=\vec{c}\cdot \vec{x}$, and Bob
the message of the form $m\_B(\vec{y})=\vec{d}\cdot \vec{y}$.

[Impagliazzo, Pitassi and Urquhart (1994)](http://www.cs.toronto.edu/~toni/publications.html) observed the following:
If all coefficients used in the cutting plane proofs
are polynomial in the number of variables, and if this game needs $t$ bits of
communication, then every tree-like proof of the unsatisfiability of the given system
must produce $\exp(t/\log n)$ inequalities. They then used known lower bounds
on communication complexity to give an explicit system requiring proofs of
exponential size. The disadvantage of this result is that the system
is very **artificial**,
it corresponds to no "real" optimization problem. It is therefore an interesting
question to come up with a lower bound for a "real" optimization problems.

One of such problems is the Independent Set problem for graphs. Given a graph
$G=(V,E)$ we can associate with each vertex $u$ a variable $x\_u$ and
consider the system of inequalities consisting of the inequality
$\sum\_{v\in V}x\_v>\alpha(G)$, and all inequalities $x\_u+x\_v\leq 1$ for all
edges $uv$ of $G$. Since every $0$-$1$ solution for the subsystem of these latter
inequalities gives an independent set in $G$, the entire system has no zero-one
solutions. What is the communication
complexity of the games for such systems?  

If our graph $=(L\cup R,E)$
is bipartite, then it is natural (for the adversary)
to split the variables according to its parts.
In this case, Alice gets a subset $A\subseteq L$, Bob a subset $B\subseteq R$
with the promise that $|A\cup B|>\alpha(G)$. The goal is to find an edge between
$A$ and $B$. Here $\alpha(G)$ is the "bipartite" independence number: maximum size of an
independent set not lying entirely in $L$ or in $R$. One of my favorite problems is:
Prove that $n\times n$ graphs requiring $\omega(\log^2 n)$ bits of communication **exist**.

@username_0: Sorry for "answering" your question with questions.

> **Comments:**
> **username_0**: I am more interested in the general cc framework than its known applications in proof complexity. The functions used by referee are known (they are fixed as I said). There are a number of issues why I am interested in this model but the main point is about how we are going to measure the amount of communication. If we are interested in total number of bits communicated then it is possible to simulate the protocol as you said. But if we want to consider some other measures of complexity like the number of rounds then I think it is different. For example, in one case that has been used in  
> **username_0**: proof complexity each player sends a real number to the referee. A real number can encode infinitely many bits, so if you want to simulate this we have to send an infinite number of bits, and if we are allowing that then we can just send the whole input, so it becomes uninteresting. But counting the number of rounds in the framework with a referee we get a different measure that can be useful (as in Pavel Pudlak's proof).  
> **username_3**: @username_0: Yes, it is sensible to what communication we count. But in the frame of cutting planes, we don't need to care about sending *real* numbers. Just assume that all coefficient are **integers** of $O(\log n)$ binary size ($n$ is the number of variables). Even **this** (restricted)  case is not clear, when wanting to get something for "real" optimization problems (like Independent Set). I am not a fun of getting lower bounds for "monster problems". People in proof complexity are usually satisfied by "monsters". But people in optimization theory would like to see "real" lower bounds.  
> **username_0**: these are a side issues, as I said I want to find out more about the kind of communication complexity I described in the question and intentionally avoided linking it to proof complexity and interpolations. There is nothing related to proof complexity in the statement of my question.  
> **username_3**: @username_0: If referee's function **is** known to the players, I don't see the difference between these "referee protocols" and "no referee protocols" (if, as I said, numbers are small). The difference could occur if we would have just one round: players send their messages to the referee, and he makes a final decision. B.t.w. in the case of $k>2$ players, this is known as "simultaneous messages communication". About "monster problems". Here I think not about circuit complexity, but rather about problems which Optimization Theory is faced with.  
> **username_0**: let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/1936/discussion-between-kaveh-and-stasys-jukna)  
> **username_4**: Can @username_3Jukna or username_0 post an update resulted from your chat, if there is any? I'm still confused on the type of measure username_0 want and the difference between the models with and without referee (as why the referee cannot be simulated when you use the same measure on both models).  

---

