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.

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ the model you are mentioning is called "Simultaneous Message Passing" $\endgroup$
    – Marcos Villagra
    Dec 7, 2011 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, 2011 at 0:11
  • 2
    $\begingroup$ here is a more recent paper by Raoul Jahin ieeexplore.ieee.org/xpl/… $\endgroup$
    – Marcos Villagra
    Dec 7, 2011 at 0:13
  • 1
    $\begingroup$ @MarcosVillagra: SMP is the same of Kaveh's Note 1, isn't it? $\endgroup$
    – Alessandro Cosentino
    Dec 7, 2011 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, 2011 at 19:23

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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, 2011 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, 2011 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.

Improve this answer
$\endgroup$
7
  • $\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, 2011 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, 2011 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, 2011 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, 2011 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, 2011 at 20:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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