9
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ the model you are mentioning is called "Simultaneous Message Passing" $\endgroup$ – Marcos Villagra Dec 7 '11 at 0:02
  • 2
    $\begingroup$ check this paper (arxiv.org/abs/quant-ph/0102001) and its references. In particular, check the papers by Ambainis, and Newman and Szegedy. $\endgroup$ – Marcos Villagra Dec 7 '11 at 0:11
  • 2
    $\begingroup$ here is a more recent paper by Raoul Jahin ieeexplore.ieee.org/xpl/… $\endgroup$ – Marcos Villagra Dec 7 '11 at 0:13
  • 1
    $\begingroup$ @MarcosVillagra: SMP is the same of Kaveh's Note 1, isn't it? $\endgroup$ – Alessandro Cosentino Dec 7 '11 at 13:41
  • $\begingroup$ @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. $\endgroup$ – Kaveh Dec 7 '11 at 19:23
7
$\begingroup$

I'm sure you know the following paper, but I put a link to it because other readers may be interested: Interpolation by Games

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.

$\endgroup$
  • $\begingroup$ 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. :) $\endgroup$ – Kaveh Dec 7 '11 at 19:29
  • 2
    $\begingroup$ Yes, I thought that. But other readers of this forum may be interested and may get interested to proof complexity. $\endgroup$ – MassimoLauria Dec 7 '11 at 19:42
5
$\begingroup$

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) 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.

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Kaveh Dec 7 '11 at 19:14
  • $\begingroup$ 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). $\endgroup$ – Kaveh Dec 7 '11 at 19:17
  • $\begingroup$ @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. $\endgroup$ – Stasys Dec 7 '11 at 19:53
  • $\begingroup$ 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. $\endgroup$ – Kaveh Dec 7 '11 at 20:03
  • 1
    $\begingroup$ @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. $\endgroup$ – Stasys Dec 7 '11 at 20:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.