Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR03-009 | 15th July 2003 00:00

RSS-Feed




Revision #1
Authors: Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey
Accepted on: 15th July 2003 00:00
Downloads: 3474
Keywords: 


Abstract:


Paper:

TR03-009 | 3rd February 2003 00:00

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





TR03-009
Authors: Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey
Publication: 17th February 2003 16:23
Downloads: 3279
Keywords: 


Abstract:

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 be
computed on non-2-connected networks.

Furthermore, a general technique for simulating private protocols on
arbitrary networks will be presented. Using this technique every private
protocol can be simulated on arbitrary $k$-connected networks using only
a small number of additional random bits.

Finally, we give matching lower and upper bounds for the number of
random bits needed to compute the parity function on $k$-connected
networks.



ISSN 1433-8092 | Imprint