Computability in Europe 2006
Logical Approaches to Computational Barriers

Special Session Talk:
Lower bounds using Kolmogorov complexity

Speaker: Sophie Laplante
Author(s): Sophie Laplante


In this paper, we survey a few recent applications of Kolmogorov complexity to
lower bounds in several models of computation.  We consider KI complexity of
Boolean functions, which gives the complexity of finding a bit where inputs
differ, for pairs of inputs that map to different function values.  This measure
and variants thereof were shown to imply lower bounds for quantum and randomized
decision tree complexity (or query complexity).  We give a similar result for
deterministic decision trees as well.  It was later shown that KI complexity
gives lower bounds for circuit depth.  We review those results here, emphasizing
simple proofs using Kolmogorov complexity, instead of strongest possible lower

We also present a Kolmogorov complexity alternative to Yao's min-max
principle.  As an example, this is applied to randomized one-way communication

websites: Arnold Beckmann 2006-04-24