Rustam Mubarakzjanov

Restricted branching programs are considered by the investigation

of relationships between complexity classes of Boolean functions.

Read-once ordered branching programs (or OBDDs) form the most restricted class

of this computation model.

Since the problem of proving exponential lower bounds on the complexity

for general probabilistic OBDDs is open so ...
more >>>

Philippe Moser

We extend Lutz's measure to probabilistic classes, and obtain notions of measure on probabilistic complexity classes

C

such as BPP , BPE and BPEXP. Unlike former attempts,

all our measure notions satisfy all three Lutz's measure axioms, that is

every singleton {L} has measure zero ...
more >>>

Bruno Bauwens, Marius Zimand

A $c$-short program for a string $x$ is a description of $x$ of length at most $C(x) + c$, where $C(x)$ is the Kolmogorov complexity of $x$. We show that there exists a randomized algorithm that constructs a list of $n$ elements that contains a $O(\log n)$-short program for $x$. ... more >>>

Siddharth Bhandari, Prahladh Harsha, Tulasimohan Molli, Srikanth Srinivasan

We study the probabilistic degree over reals of the OR function on $n$ variables. For an error parameter $\epsilon$ in (0,1/3), the $\epsilon$-error probabilistic degree of any Boolean function $f$ over reals is the smallest non-negative integer $d$ such that the following holds: there exists a distribution $D$ of polynomials ... more >>>