It is shown that there exist network topologies such that congestion can only be avoided if messages are sent using non-linear Boolean functions. The talk highlights a new link between network flow and error correcting codes: there exist networks where the optimal flow is achieved by essentially selecting the worst error-correcting code (rather than the best). The dichotomy between advantages of good and bad error-correcting codes is highlighted in the paper.

The field of network coding seems to be very rich with many open questions. Recently this field has attracted logicians who also seem fascinated by inventing ways of constructing networks with pathological properties.

The topics addressed in the talk will be almost at the level of recreational mathematics!