<p>In 1988 Karchmer and Wigderson established a nice characterization of the circuit
depth $d$ (DeMorgan circuits) of a Boolean function $f \colon \{0,1\}^n\rightarrow\{0,1\}$: $d$ is exactly the number of bits that Alice and Bob need to communicate in order to find
an index $i$ such that $a_i \neq b_i$, where Alice knows $a \in f^{-1}(0)$ and Bob knows $b \in f^{-1}(1)$.</p>

<p>What is known about upper bounds proved for such games? I've only
managed to find the following three results:</p>

<p>1) $2\log n$  upper bound for Parity function (binary search).</p>

<p>2) Chin proved $2.88\log n$ upper bound for $MOD_3$, $3.47\log n$ for
$MOD_5$, $4.93\log n$ for $MOD_{11}$ (http://unclaw.com/chin/scholarship/countingfunctions.pdf).</p>

<p>3) Brodal and Husfeldt proved an $O(\log n)$ upper bound for all symmetric functions (http://www.brics.dk/RS/96/1/BRICS-RS-96-1.pdf).</p>

<p>Are these the only known (non-straightforward) protocols?</p>

CC BY-SA 3.0
2011-12-14T22:05:37.980Z
I don't understand. Since the communication complexity is an exact characterization of circuit depth, you get a non-trivial upper bound from any non-trivial circuit. Take your favourite problem in NC^1: that gives you a O(\log n) upper bound.
slimton
CC BY-SA 3.0
2011-12-15T13:39:00.997Z
Yes, and the proof of equality of DeMorgan circuit's depth and communication complexity of Karchmer-Wigderson game is constructive proof. So, we can obtain Karchmer-Wigderson protocol from any DeMorgan circuit. But protocols will be very complicated. I'm looking for ideas that can be used in Karchmer-Wigderson games. For example, the idea of Chin algorithm is divide and conquer (no division into equal parts, but division into parts, which require equal communication). Do we know other ideas for Karchmer-Wigderson game?
Alex Golovnev
CC BY-SA 3.0
2011-12-15T18:00:50.243Z
@Alex: I second "slimton". KW games is just another language for the same thing - the depth. But if so, it could be perhaps interesting to translate the following result into this language: if $f$ has an $AC^0$ formula of depth $d$ and $S$ leaves, then $KW(f)\leq d+\log S$. Note: a trivial upper bound is only $O(d\log S)$ if we replace each ``big'' gate by a fanin-2 circuit. Paper [Lozhkin (1981) in Problemy Kibernetiki 38, 269–271]
Stasys
CC BY-SA 3.0
2011-12-15T18:05:51.287Z
@Alex: P.S. If you are interested in **upper** bounds on KW games, you could try the following ``sinless'' one. We have a bipartite $n\times n$ graph $G$. Alice gets a subset $A$ of left vertices, Bob gets a subset $B$ of right vertices such that $|A|+|B|>\alpha(G)$. The goal is to find an edge between $A$ and $B$. Can this be **always** done with $O(\log^2 n)$ bits of communication (for **every** graph $G$)?
Stasys
CC BY-SA 3.0
2011-12-16T12:42:56.283Z
Prof. Jukna, thank you very much! Do you know how can I find Lozhkin's paper in the Internet? About the problem. I think that we can solve this problem in $O(\log n)$ bits, if G has a perfect matching. But I don't know how to solve it in $O(\log^2 n)$ bits. Is it open problem? What is the trivial bound? The problem seems to be very interesting and I will try to solve it, but, unfortunatelly, I don't see connection with boolean functions complexity. Does the connection exist? Thank you again for your responses.
Alex Golovnev
CC BY-SA 3.0
2011-12-16T15:32:04.433Z
@Alex: Unfortunately, Проблемы кибернетики can be only found in a library (and I do not have a copy right now). Motivation for the "find an edge" game can be found [here](http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/index.html) as Problem 19.12. A trivial bound is $\geq \log n$ (the edge must be known to both players). How can you get $O(\log n)$ for **any** graph $G$ containing a perfect matching? (Unless $G$ itself is a $PM$, or almost $PM$.) Note that, in general, $|A|+|B|\ll n$. If your claim held, this would be quite surprising.
Stasys
CC BY-SA 3.0
2011-12-16T16:19:59.333Z
Prof. Julkna, thank you for the explanation of a game! Also, I will try to find a book in a library. About the game. The problem, stated in the book, is about general graphs, and $|A|+|B|$ usually $\ll n$. But the problem, stated in the previous comment, is about bipartite $n \times n$ graphs. I think it means that $|A|+|B|>\alpha \ge n$. Please correct me.
Alex Golovnev
CC BY-SA 3.0
2011-12-16T16:21:23.480Z
Then we can use the following algorithm: 1) $|A|=a, |B|=b$, $A'$ - neignbours of $A$. 2)$|A'|\ge |A|$ by Hall's theorem. 3)$|A'|+|B|\ge |A|+|B|>n$, $|A'|\neq n-|B|$. 4)We have two strings of length n. The first string is Bob vertices, the second is Bob's vertices, which Alice is looking for. The number of ones in the first string is $|B|$, in the second string -$|A'|$. 5)Invert all bits of the first string and use O(\log n) protocol for symmetric boolean functions. We can use it because $|A'|\neq n-|B|$.
Alex Golovnev
CC BY-SA 3.0
2011-12-16T17:18:20.503Z
@Alex: I am sorry for being not exact (comments length is restricted). In the case of **bipartite** graphs, $\alpha(G)$ is understood as the largest number $a+b$ such that there are no edges between some $a$-subset of vertices on the left and some $b$-subset on the right (that is, the bipartite complement of $G$ contains $K_{a,b}$) So, you **cannot** assume that $\alpha(G)>n$, and hence, that the characteristic vectors must intersect.
Stasys
CC BY-SA 3.0
2011-12-16T20:45:13.837Z
Prof. Jukna, thank you! I see. I have no ideas now, but I will try to solve this problem.
Alex Golovnev
CC BY-SA 3.0
2012-03-09T13:20:45.880Z
@Alex: Although your argument (using Hall's theorem) does not work for graphs with $\alpha(G)<n$,  $O(\log n)$ bits of communication are indeed enough for every graph. See the [solution]http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/comment1.html. Something similar should also work for non-bipartite graphs.
Stasys
CC BY-SA 3.0
2012-03-18T20:29:23.443Z
Prof. Jukna, I see it works. I really like this solution. Do you know any open problem like this? By the way, I got Lozhkin's paper. I can send you a copy if you need.
Alex Golovnev
CC BY-SA 3.0
2012-03-20T10:13:30.883Z
@Alex: Yes, I would be happy to see Lozhkin's paper (if you have an electronic copy). B.t.w. I think that your reduction to symmetric functions (even for graphs with $\alpha(G)>n$) does not quite work: the found vertex may lie outside $A'$ or outside $B$ (we only find an element in symmetric difference, not in $A'\cap B$). A similar (hard but not completely intractable) open problem is Problem 4.14 in my book (clique vs. indep. set game) with "exhibit" replaced by "prove the existence".
Stasys
CC BY-SA 3.0
2012-03-20T18:30:29.887Z
Prof. Jukna, yes, it's a mistake (an element can lie in symmetric difference of $\neg B$ and $A'$). I sent you a paper (in Russian) by email.
Alex Golovnev
<cc.complexity-theory><circuit-complexity><communication-complexity><upper-bounds>
Known upper bounds on the communication complexity of Karchmer-Wigderson games
Alex Golovnev
# Known upper bounds on the communication complexity of Karchmer-Wigderson games

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

In 1988 Karchmer and Wigderson established a nice characterization of the circuit
depth $d$ (DeMorgan circuits) of a Boolean function $f \colon \{0,1\}^n\rightarrow\{0,1\}$: $d$ is exactly the number of bits that Alice and Bob need to communicate in order to find
an index $i$ such that $a\_i \neq b\_i$, where Alice knows $a \in f^{-1}(0)$ and Bob knows $b \in f^{-1}(1)$.

What is known about upper bounds proved for such games? I've only
managed to find the following three results:

1) $2\log n$ upper bound for Parity function (binary search).

2) Chin proved $2.88\log n$ upper bound for $MOD\_3$, $3.47\log n$ for
$MOD\_5$, $4.93\log n$ for $MOD\_{11}$ (http://unclaw.com/chin/scholarship/countingfunctions.pdf).

3) Brodal and Husfeldt proved an $O(\log n)$ upper bound for all symmetric functions (http://www.brics.dk/RS/96/1/BRICS-RS-96-1.pdf).

Are these the only known (non-straightforward) protocols?

**Tags:** cc.complexity-theory, circuit-complexity, communication-complexity, upper-bounds

> **Comments:**
> **username_1**: I don't understand. Since the communication complexity is an exact characterization of circuit depth, you get a non-trivial upper bound from any non-trivial circuit. Take your favourite problem in NC^1: that gives you a O(\log n) upper bound.  
> **username_0**: Yes, and the proof of equality of DeMorgan circuit's depth and communication complexity of Karchmer-Wigderson game is constructive proof. So, we can obtain Karchmer-Wigderson protocol from any DeMorgan circuit. But protocols will be very complicated. I'm looking for ideas that can be used in Karchmer-Wigderson games. For example, the idea of Chin algorithm is divide and conquer (no division into equal parts, but division into parts, which require equal communication). Do we know other ideas for Karchmer-Wigderson game?  
> **username_2**: @Alex: I second "username_1". KW games is just another language for the same thing - the depth. But if so, it could be perhaps interesting to translate the following result into this language: if $f$ has an $AC^0$ formula of depth $d$ and $S$ leaves, then $KW(f)\leq d+\log S$. Note: a trivial upper bound is only $O(d\log S)$ if we replace each ``big'' gate by a fanin-2 circuit. Paper [Lozhkin (1981) in Problemy Kibernetiki 38, 269–271]  
> **username_2**: @Alex: P.S. If you are interested in **upper** bounds on KW games, you could try the following ``sinless'' one. We have a bipartite $n\times n$ graph $G$. Alice gets a subset $A$ of left vertices, Bob gets a subset $B$ of right vertices such that $|A|+|B|>\alpha(G)$. The goal is to find an edge between $A$ and $B$. Can this be **always** done with $O(\log^2 n)$ bits of communication (for **every** graph $G$)?  
> **username_0**: Prof. Jukna, thank you very much! Do you know how can I find Lozhkin's paper in the Internet? About the problem. I think that we can solve this problem in $O(\log n)$ bits, if G has a perfect matching. But I don't know how to solve it in $O(\log^2 n)$ bits. Is it open problem? What is the trivial bound? The problem seems to be very interesting and I will try to solve it, but, unfortunatelly, I don't see connection with boolean functions complexity. Does the connection exist? Thank you again for your responses.  
> **username_2**: @Alex: Unfortunately, Проблемы кибернетики can be only found in a library (and I do not have a copy right now). Motivation for the "find an edge" game can be found [here](http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/index.html) as Problem 19.12. A trivial bound is $\geq \log n$ (the edge must be known to both players). How can you get $O(\log n)$ for **any** graph $G$ containing a perfect matching? (Unless $G$ itself is a $PM$, or almost $PM$.) Note that, in general, $|A|+|B|\ll n$. If your claim held, this would be quite surprising.  
> **username_0**: Prof. Julkna, thank you for the explanation of a game! Also, I will try to find a book in a library. About the game. The problem, stated in the book, is about general graphs, and $|A|+|B|$ usually $\ll n$. But the problem, stated in the previous comment, is about bipartite $n \times n$ graphs. I think it means that $|A|+|B|>\alpha \ge n$. Please correct me.  
> **username_0**: Then we can use the following algorithm: 1) $|A|=a, |B|=b$, $A'$ - neignbours of $A$. 2)$|A'|\ge |A|$ by Hall's theorem. 3)$|A'|+|B|\ge |A|+|B|>n$, $|A'|\neq n-|B|$. 4)We have two strings of length n. The first string is Bob vertices, the second is Bob's vertices, which Alice is looking for. The number of ones in the first string is $|B|$, in the second string -$|A'|$. 5)Invert all bits of the first string and use O(\log n) protocol for symmetric boolean functions. We can use it because $|A'|\neq n-|B|$.  
> **username_2**: @Alex: I am sorry for being not exact (comments length is restricted). In the case of **bipartite** graphs, $\alpha(G)$ is understood as the largest number $a+b$ such that there are no edges between some $a$-subset of vertices on the left and some $b$-subset on the right (that is, the bipartite complement of $G$ contains $K_{a,b}$) So, you **cannot** assume that $\alpha(G)>n$, and hence, that the characteristic vectors must intersect.  
> **username_0**: Prof. Jukna, thank you! I see. I have no ideas now, but I will try to solve this problem.  
> **username_2**: @Alex: Although your argument (using Hall's theorem) does not work for graphs with $\alpha(G)<n$,  $O(\log n)$ bits of communication are indeed enough for every graph. See the [solution]http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/comment1.html. Something similar should also work for non-bipartite graphs.  
> **username_0**: Prof. Jukna, I see it works. I really like this solution. Do you know any open problem like this? By the way, I got Lozhkin's paper. I can send you a copy if you need.  
> **username_2**: @Alex: Yes, I would be happy to see Lozhkin's paper (if you have an electronic copy). B.t.w. I think that your reduction to symmetric functions (even for graphs with $\alpha(G)>n$) does not quite work: the found vertex may lie outside $A'$ or outside $B$ (we only find an element in symmetric difference, not in $A'\cap B$). A similar (hard but not completely intractable) open problem is Problem 4.14 in my book (clique vs. indep. set game) with "exhibit" replaced by "prove the existence".  
> **username_0**: Prof. Jukna, yes, it's a mistake (an element can lie in symmetric difference of $\neg B$ and $A'$). I sent you a paper (in Russian) by email.  

---

## 0 answers

