ECCC-Report TR03-009https://eccc.weizmann.ac.il/report/2003/009Comments and Revisions published for TR03-009en-usTue, 15 Jul 2003 00:00:00 +0300
Revision 1
| |
Markus Bläser,
Andreas Jakoby,
Maciej Liskiewicz,
Bodo Manthey
https://eccc.weizmann.ac.il/report/2003/009#revision1Tue, 15 Jul 2003 00:00:00 +0300https://eccc.weizmann.ac.il/report/2003/009#revision1
Paper TR03-009
| Private Computation --- $k$-connected versus $1$-connected Networks |
Markus Bläser,
Andreas Jakoby,
Maciej Liskiewicz,
Bodo Manthey
https://eccc.weizmann.ac.il/report/2003/009We 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.
Mon, 17 Feb 2003 16:23:51 +0200https://eccc.weizmann.ac.il/report/2003/009