Information flows, graphs and their guessing numbers (Q2372888): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Added link to MaRDI item.
links / mardi / namelinks / mardi / name
 

Revision as of 18:10, 2 February 2024

scientific article
Language Label Description Also known as
English
Information flows, graphs and their guessing numbers
scientific article

    Statements

    Information flows, graphs and their guessing numbers (English)
    0 references
    0 references
    16 July 2007
    0 references
    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.
    0 references
    cyclic shifts
    0 references
    communication
    0 references
    network coding
    0 references
    information
    0 references
    circuit complexity
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references