Lower bound for computing fixed points

Speaker(s)

Paweł Parys

Affiliation

Uniwersytet Warszawski

Date

March 25, 2009, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

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.

---