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?

  • 3
    $\begingroup$ 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. $\endgroup$ – slimton Dec 14 '11 at 22:05
  • 5
    $\begingroup$ @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] $\endgroup$ – Stasys Dec 15 '11 at 18:00
  • 5
    $\begingroup$ @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$)? $\endgroup$ – Stasys Dec 15 '11 at 18:05
  • 2
    $\begingroup$ @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 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. $\endgroup$ – Stasys Dec 16 '11 at 15:32
  • 2
    $\begingroup$ @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. $\endgroup$ – Stasys Dec 16 '11 at 17:18

Your Answer

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

Browse other questions tagged or ask your own question.