Under the auspices of the Computational Complexity Foundation (CCF)
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