Information flows, graphs and their guessing numbers
Summary: Valiant's shift problem asks whether all \(n\) cyclic shifts on \(n\) bits can be realized if \(n^{(1+\varepsilon)}\) input output pairs (\(\varepsilon < 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^{\varepsilon})/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 establishes an interesting link between circuit complexity and network coding, a new direction of research in multiuser information theory.
- Information flows on hypergraphs
- Information flow on directed acyclic graphs
- Information Flows in Complex Networks
- scientific article; zbMATH DE number 5158914
- Graph Guessing Games and Non-Shannon Information Inequalities
- Quantitative information flow, with a view
- Extended Pawlak’s Flow Graphs and Information Theory
- Publication:4206742
- scientific article; zbMATH DE number 5785643
- On the guessing number of shift graphs
- Positive and negative cycles in Boolean networks
- On the rank and periodic rank of finite dynamical systems
- Guessing numbers and extremal graph theory
- Hat guessing numbers of degenerate graphs
- On the stability and instability of finite dynamical systems with prescribed interaction graphs
- Fixed points in conjunctive networks and maximal independent sets in graph contractions
- Max-flow min-cut theorems on dispersion and entropy measures for communication networks
- The linear guessing number of undirected graphs
- Bears with hats and independence polynomials
- Guessing games on triangle-free graphs
- A numbers-on-foreheads game
- Fixed points of Boolean networks, guessing graphs, and coding theory
- Finite dynamical systems, hat games, and coding theory
- The minrank of random graphs
- On minrank and the Lovász theta-function
- On minrank and forbidden subgraphs
- Lower Bounds for Multiplication via Network Coding
- The three colour hat guessing game on cycle graphs
- Guessing numbers of odd cycles
- New constructions and bounds for Winkler's hat game
- Number of fixed points and disjoint cycles in monotone Boolean networks
- On the influence of the interaction graph on a finite dynamical system
- Complexity of limit cycles with block-sequential update schedules in conjunctive networks
- Bears with hats and independence polynomials
- Storage codes and recoverable systems on lines and grids
- Kernelization for orthogonality dimension
- Bounds on guessing numbers and secret sharing combining information theory methods.
- Kernelization for orthogonality dimension
- Creation of fixed points in block-parallel Boolean automata networks
- Kernelization for H-coloring
- The hat guessing number of graphs
This page was built for publication: Information flows, graphs and their guessing numbers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2372888)
