Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Distributed algorithms:
TR03-009 | 3rd February 2003
Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey

Private Computation --- $k$-connected versus $1$-connected Networks

Revisions: 1

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

TR03-071 | 18th August 2003
Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey

Privacy in Non-Private Environments

Revisions: 1

We study private computations in information-theoretical settings on
networks that are not 2-connected. Non-2-connected networks are
``non-private'' in the sense that most functions cannot privately be
computed on such networks. We relax the notion of privacy by
introducing lossy private protocols, which generalize private
protocols. We measure the information each ... more >>>

ISSN 1433-8092 | Imprint