Information complexity of query algorithms?

Question

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

Answer 1

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 or from ACM's repository. 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]
• 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]