A syntactic read-k times branching program has the restriction that no variable occurs more than k times on any path (whether or not consistent). We exhibit an explicit Boolean function f which cannot be computed by nondeterministic syntactic read-k times branching programs of size less than exp(\sqrt{n}}k^{-2k}), although its complement ... more >>>

We consider the problem of estimating the average of a huge set of values. That is, given oracle access to an arbitrary function $f:\{0,1\}^n\mapsto[0,1]$, we need to estimate $2^{-n} \sum_{x\in\{0,1\}^n} f(x)$ upto an additive error of $\epsilon$. We are allowed to employ a randomized algorithm which may err with probability ... more >>>

We survey some upper and lower bounds established recently on the sizes of randomized branching programs computing explicit boolean functions. In particular, we display boolean functions on which randomized read-once ordered branching programs are exponentially more powerful than deterministic or nondeterministic read-$k$-times branching programs for any $k=o(n/\!\log n)$. We investigate ... more >>>

We consider the problem of scheduling permanent jobs on related machines in an on-line fashion. We design a new algorithm that achieves the competitive ratio of $3+\sqrt{8}\approx 5.828$ for the deterministic version, and $3.31/\ln 2.155 \approx 4.311$ for its randomized variant, improving the previous competitive ratios of 8 and $2e\approx ... more >>>

We present a new efficient sampling method for approximating r-dimensional Maximum Constraint Satisfaction Problems, MAX-rCSP, on n variables up to an additive error \epsilon n^r.We prove a new general paradigm in that it suffices, for a given set of constraints, to pick a small uniformly random subset of its variables, ... more >>>

In this paper we propose the study of a new model of restricted branching programs which we call incremental branching programs. This is in line with the program proposed by Cook in 1974 as an approach for separating the class of problems solvable in logarithmic space from problems solvable in ... more >>>