We give an algorithm for finding an \epsilon-fixed point of a contraction map f:[0,1]^k\rightarrow [0,1]^k under the \ell_\infty-norm with query complexity O (k^2\log (1/\epsilon ) ).

We study the problem of finding a Tarski fixed point over the k-dimensional grid [n]^k. We give a black-box reduction from the Tarski problem to the same problem with an additional promise that the input function has a unique fixed point. It implies that the Tarski problem and the unique ... more >>>

A graph G has an \emph{S-factor} if there exists a spanning subgraph F of G such that for all v \in V: \deg_F(v) \in S.
The simplest example of such factor is a 1-factor, which corresponds to a perfect matching in a graph. In this paper we study the computational ... more >>>

The following two decision problems capture the complexity of
comparing integers or rationals that are succinctly represented in
product-of-exponentials notation, or equivalently, via arithmetic
circuits using only multiplication and division gates, and integer
inputs:

Input instance: four lists of positive integers:

$a_1, \ldots , a_n; \ b_1, \ldots ,b_n; \ ... more >>>