A property of functions is called location-invariant (or symmetric) if it can be characterized in terms of the frequencies in which each value occurs in the function, regardless of the locations in which each value occurs.
It is known that the (query) complexity of testing location-invariant properties of functions ... more >>>

We address the following fundamental question: is there an efficient deterministic algorithm that, given $1^n$, outputs a string of length $n$ that has polynomial-time bounded Kolmogorov complexity $\tilde{\Omega}(n)$ or even $n - o(n)$?

Under plausible complexity-theoretic assumptions, stating for example that there is an $\epsilon > 0$ for which $TIME[T(n)] ... more >>>

Minimally rigid graphs can be recognized and embedded in the plane efficiently, i.e. in polynomial time. There is also an efficient randomized parallel algorithm, i.e. in RNC. We present NC-algorithms to recognize whether one-crossing-minor-free graphs are minimally rigid. In the special case of $K_{3,3}$-free graphs, we also compute an infinitesimally ... more >>>