|Kokkuvõte||The following network communications scenario is studied: source nodes generate random messages, and a receiver node computes a target function. The goal is to maximize “computing capacity”, i.e. the average number of times the function can be computed per network usage. The min-cut in the graph (with respect to the network computing problem) plays a pivotal role in analyzing the computing capacity. The min-cut is a known upper bound on the maximum achievable rate and it is a tight bound for computing any target function in multi-edge tree networks.
In this project, we will study more general scenarios for function computations in the network. We will aim at understanding fundamental limits on computing capacity for more general network topologies and functions, and at developing efficient algorithms for doing so.