Let $d \geq d_0$ be a sufficiently large constant. A $(n,d,c
\sqrt{d})$ graph $G$ is a $d$ regular graph over $n$ vertices whose
second largest eigenvalue (in absolute value) is at most $c
\sqrt{d}$. For any $0 < p < 1, ~G_p$ is the graph induced by
retaining each edge ... more >>>

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 >>>