Based on experimental results N. Duffield, C. Lund and M. Thorup \cite{dlt2} conjectured
that the variance of their highly successful priority sampling procedure
is not larger than the variance of the threshold sampling procedure with sample size one smaller.
The conjecture's significance is that the latter procedure is provably optimal ... more >>>

In this paper we study the complexity of Bounded Color
Multiplicity Graph Isomorphism (BCGI): the input is a pair of
vertex-colored graphs such that the number of vertices of a given
color in an input graph is bounded by $b$. We show that BCGI is in the
#L hierarchy ... more >>>

Alice and Bob want to know if two strings of length $n$ are
almost equal. That is, do they differ on at most $a$ bits?
Let $0\le a\le n-1$.
We show that any deterministic protocol, as well as any
error-free quantum protocol ($C^*$ version), for this problem
requires at ... more >>>