Information flows, graphs and their guessing numbers

We provide a counter example to a conjecture by Leslie Valiant. Most interestingly the counter example was found by introducing guessing numbers - a new graph theoretical concept. We show that solvability of information flow problems of a quite general type is closely related to problems concerning guessing numbers. We reduce a few other conjectures by Valiant, to a general problem about guessing numbers. Valiant’s conjectures have been shown to be linked to the long standing open question of proving non-linear size, non-logarithmic depth lower bounds on unrestricted circuits in Circuit Complexity. As a by-product we establish (by use of results by Valiant) an interesting link between Circuit Complexity and Network Coding, a new direction of research in multiuser information theory.