Information flows, graphs and their guessing numbers

Søren Riis

The electronic journal of combinatorics, Tome 14 (2007)

Résumé

Valiant's shift problem asks whether all $n$ cyclic shifts on $n$ bits can be realized if $n^{(1+\epsilon)}$ input output pairs ($\epsilon < 1$) are directly connected and there are additionally $m$ common bits available that can be arbitrary functions of all the inputs. If it could be shown that this is not realizable with $m = O({n\over \log \log n})$ common bits then a significant breakthrough in Boolean circuit complexity would follow. In this paper it is shown that in certain cases all cyclic shifts are realizable with $m=(n- n^{\epsilon})/2$ common bits. Previously, no solution with $m < n - o(n)$ was known, and Valiant had conjectured that $m < n/2$ was not achievable. The construction therefore establishes a novel way of realizing communication in the manner of Network Coding for the shift problem, but leaves the viability of the common information approach to proving lower bounds in Circuit Complexity open. The construction uses the graph-theoretic notion of guessing number. As a by-product the paper also establish an interesting link between Circuit Complexity and Network Coding, a new direction of research in multiuser information theory.

Détail

DOI : 10.37236/962

Classification : 05C20, 68Q17, 68R10, 94A24
Mots-clés : cyclic shifts, communication, network coding, information, circuit complexity