We show that for any reasonable semantic model of computation and for
any positive integer $a$ and rationals $1 \leq c < d$, there exists a language
computable in time $n^d$ with $a$ bits of advice but not in time $n^c$
with $a$ bits of advice. A semantic ... more >>>

We study the round complexity of two-party protocols for
generating a random $n$-bit string such that the output is
guaranteed to have bounded bias (according to some measure) even
if one of the two parties deviates from the protocol (even using
unlimited computational resources). Specifically, we require that
the output's ... more >>>

An $(n,k)$-bit-fixing source is a distribution $X$ over $\B^n$ such that
there is a subset of $k$ variables in $X_1,\ldots,X_n$ which are uniformly
distributed and independent of each other, and the remaining $n-k$ variables
are fixed. A deterministic bit-fixing source extractor is a function $E:\B^n
\ar \B^m$ which on ... more >>>