<p>Yes, information theory is useful for proving lower bounds on the query complexity of problems in Computer Science.</p>

<p>Alexander Golynski gave a good example in his ground breaking paper titled "Cell probe lower bounds for succinct data structures", presented at SODA 2009. He uses information theory to prove a lower bound on query complexity, which in turns yields a lower bound in the bit-probe model for (succinct) data structures. You can download the paper from <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.154.3540" rel="nofollow">citeseer's cache</a> or from <a href="http://dl.acm.org/ft_gateway.cfm?id=1496839" rel="nofollow">ACM's repository</a>. There does not seem to be a journal version of the article.</p>

<p>You might be interested also in the following articles from his bibliography, which also relate communication complexity with information theory:</p>

<ul>
<li>Peter Bro Miltersen, Noam Nisan, Shmuel Safra, and
Avi Wigderson. On data structures and asymmetric
communication complexity. Journal of Computer and
System Sciences, 57(1):37–49, 1998. <a href="http://www.cs.au.dk/~bromille/Papers/asym.pdf" rel="nofollow">[link]</a></li>
<li>Anna Gal and Peter Bro Miltersen. The cell probe
complexity of succinct data structures. In International
Colloquium on Automata, Languages and Programming,
pages 332–344, 2003. <a href="ftp://ftp.daimi.au.dk/pub/BRICS/RS/03/44/BRICS-RS-03-44.pdf" rel="nofollow">[link]</a></li>
</ul>

CC BY-SA 3.0
2015-04-14T12:58:45.840Z
2015-04-15T09:05:58.570Z
2015-04-15T09:05:58.570Z
J.y B.y
<p>Information complexity has been a very useful tool in communication complexity, mainly used to lower bound the communication complexity of distributed problems. </p>

<p>Is there an analogue of information complexity for query complexity? There are many parallels between query complexity and communication complexity; oftentimes (but not always!) a lower bound in one model gets translated to a lower bound in the other model. Sometimes this translation is quite nontrivial.</p>

<p>Is there a notion of information complexity that is useful for lower bounding the query complexity of problems? </p>

<p>A first pass seems to indicate that information complexity is not very useful; for example, the query complexity of computing the OR of $N$ bits is $\Omega(N)$ for randomized algorithms and $\Omega(\sqrt{N})$ for quantum algorithms, whereas the most straightforward adaption of the notion of information complexity indicates that the information learned by any query algorithm is at most $O(\log N)$ (because the algorithm stops when it sees the first $1$ in the input). </p>

<it.information-theory><communication-complexity><query-complexity>
Information complexity of query algorithms?
Henry Yuen
# Information complexity of query algorithms?

(Asked by: username_0 on 2015-04-03)

Information complexity has been a very useful tool in communication complexity, mainly used to lower bound the communication complexity of distributed problems.

Is there an analogue of information complexity for query complexity? There are many parallels between query complexity and communication complexity; oftentimes (but not always!) a lower bound in one model gets translated to a lower bound in the other model. Sometimes this translation is quite nontrivial.

Is there a notion of information complexity that is useful for lower bounding the query complexity of problems?

A first pass seems to indicate that information complexity is not very useful; for example, the query complexity of computing the OR of $N$ bits is $\Omega(N)$ for randomized algorithms and $\Omega(\sqrt{N})$ for quantum algorithms, whereas the most straightforward adaption of the notion of information complexity indicates that the information learned by any query algorithm is at most $O(\log N)$ (because the algorithm stops when it sees the first $1$ in the input).

**Tags:** it.information-theory, communication-complexity, query-complexity

---

## 1 answers

### Answer by username_1 on 2015-04-14. Score: 5

Yes, information theory is useful for proving lower bounds on the query complexity of problems in Computer Science.

Alexander Golynski gave a good example in his ground breaking paper titled "Cell probe lower bounds for succinct data structures", presented at SODA 2009. He uses information theory to prove a lower bound on query complexity, which in turns yields a lower bound in the bit-probe model for (succinct) data structures. You can download the paper from [citeseer's cache](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.154.3540) or from [ACM's repository](http://dl.acm.org/ft_gateway.cfm?id=1496839). There does not seem to be a journal version of the article.

You might be interested also in the following articles from his bibliography, which also relate communication complexity with information theory:

* Peter Bro Miltersen, Noam Nisan, Shmuel Safra, and
  Avi Wigderson. On data structures and asymmetric
  communication complexity. Journal of Computer and
  System Sciences, 57(1):37–49, 1998. [[link]](http://www.cs.au.dk/~bromille/Papers/asym.pdf)
* Anna Gal and Peter Bro Miltersen. The cell probe
  complexity of succinct data structures. In International
  Colloquium on Automata, Languages and Programming,
  pages 332–344, 2003. [[link]](ftp://ftp.daimi.au.dk/pub/BRICS/RS/03/44/BRICS-RS-03-44.pdf)


---

