
PreviousNext
A regular $(1,+k)$-branching program ($(1,+k)$-ReBP) is an
ordinary branching program with the following restrictions: (i)
along every consistent path at most $k$ variables are tested more
than once, (ii) for each node $v$ on all paths from the source to
$v$ the same set $X(v)\subseteq X$ of variables is ...
more >>>
We prove hardness results for approximating set splitting problems and
also instances of satisfiability problems which have no ``mixed'' clauses,
i.e all clauses have either all their literals unnegated or all of them
negated. Recent results of Hastad imply tight hardness results for set
splitting when all sets ...
more >>>
We introduce the notion of Resettable Zero-Knowledge (rZK),
a new security measure for cryptographic protocols
which strengthens the classical notion of zero-knowledge.
In essence, an rZK protocol is one that remains zero knowledge
even if an adeversary can interact with the prover many times, each
time ...
more >>>
PreviousNext