We consider the problem of finding a maximum independent set in a
random graph. The random graph $G$ is modelled as follows. Every
edge is included independently with probability $\frac{d}{n}$, where
$d$ is some sufficiently large constant. Thereafter, for some
constant $\alpha$, a subset $I$ of $\alpha n$ vertices is ... more >>>

We consider the problem of computing the Hamming weight of an n-bit vector using a circuit with gates for GF2 addition and multiplication only. We show the number of multiplications necessary and sufficient to build such a circuit is n - |n| where |n| is the Hamming weight of the ... more >>>

We present constant-round concurrently secure (sound) resettable
zero-knowledge (rZK-CS) arguments in the bare public-key (BPK)
model. Our constructions deal with general NP ZK-arguments as well
as with highly efficient ZK-arguments for number-theoretic
languages, most relevant to identification scenarios. These are the
first constant-round protocols of ... more >>>