We study the question of whether the class DisNP of
disjoint pairs (A, B) of NP-sets contains a complete pair.
The question relates to the question of whether optimal
proof systems exist, and we relate it to the previously
studied question of whether there exists ... more >>>

The satisfiability problem of Boolean Formulae in 3-CNF (3-SAT)
is a well known NP-complete problem and the development of faster
(moderately exponential time) algorithms has received much interest
in recent years. We show that the 3-SAT problem can be solved by a
probabilistic algorithm in expected time O(1,3290^n).
more >>>

We study the role of connectivity of communication networks in private
computations under information theoretic settings. It will be shown that
some functions can be computed by private protocols even if the
underlying network is 1-connected but not 2-connected. Then we give a
complete characterisation of non-degenerate functions that can ... more >>>