Lower bound for computing fixed points

Prelegent(ci)

Paweł Parys

Afiliacja

Uniwersytet Warszawski

Termin

25 marca 2009 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

We consider the following problem: There is given a monotone K-argument function f defined on N-bit sequences {0,1}^N. There is also given the following simpliest possible mu-calculus expression: mi(x1).ni(x2).mi(x3).ni(x4)...mi(xK).f(x1,...,xK). The function is given as a black-box: we can only query it for given arguments. The question is how many queries are necessary to calculate the value of the expression? The goal would be to show an exponential (in N and K) lower bound. I will show that for K=2 almost N^2 queries are needed.

---