Speaker: Eric Allender

Rutgers University

Title: Avoiding Simplicity is Complex

Abstract:
It is a trivial observation that every decidable set has strings of

length n with Kolmogorov complexity log n + O(1) if it has any strings of

length n at all. Things become much more interesting when one asks

whether a similar property holds when one considers

***resource-bounded*** Kolmogorov complexity. This is the question considered in this talk:

Can a feasible set A avoid accepting strings of low resource-bounded

Kolmogorov complexity, while still accepting some (or many) strings of

length n?

More specifically, this paper deals with two notions of resource-bounded

Kolmogorov complexity: Kt and KNt. The measure Kt was defined by Levin

more than three decades ago and has been studied extensively since then.

The measure KNt is a nondeterministic analog of Kt. For all strings x,

Kt(x)>= KNt(x); the two measures are polynomially related if and only if

NEXP is a subset of EXP/poly.

Many longstanding open questions in complexity theory boil down to the

question of whether there are sets in P that avoid all strings of low Kt

complexity. As one example, note that the output of a hitting-set

generator is (necessarily) a set of strings having low resource-bounded

Kolmogorov complexity, and thus secure hitting set generators exist if

any "dense" set in P/poly contains strings of small Kt complexity.

As another example, the EXP vs ZPP question is equivalent to (one

version of) the question of whether avoiding simple strings is

difficult: EXP = ZPP if and only if there exist epsilon>0 and a ``dense''

set in

P having no strings x with Kt(x)<=

`|x|`

^epsilon .

Surprisingly, we are able to show

***unconditionally*** that avoiding simple

strings (in the sense of KNt complexity) is difficult. Every dense set

in NP intersect coNP contains infinitely many strings x such that

KNt(x)<=

`|x|`

^epsilon

for some epsilon.

The proof does not relativize. As an application, we are able to show

that if E = NE, then accepting paths for nondeterministic exponential

time machines can be found somewhat more quickly than the brute-force

upper bound, if there are many accepting paths. I think that there

should be more interesting applications; perhaps you can find some!

The paper is available here:

http://ftp.cs.rutgers.edu/pub/allender/simplicity.pdf