Near-optimal lower bounds on the threshold degree and sign-rank of AC <sup>0</sup> (Q5212781)

From MaRDI portal
Revision as of 19:17, 5 March 2024 by Import240304020342 (talk | contribs) (Set profile property.)
scientific article; zbMATH DE number 7160519
Language Label Description Also known as
English
Near-optimal lower bounds on the threshold degree and sign-rank of AC <sup>0</sup>
scientific article; zbMATH DE number 7160519

    Statements

    Near-optimal lower bounds on the threshold degree and sign-rank of AC <sup>0</sup> (English)
    0 references
    0 references
    0 references
    30 January 2020
    0 references
    communication complexity
    0 references
    constant-depth circuits
    0 references
    sign-rank
    0 references
    sign-representation by polynomials
    0 references
    threshold degree
    0 references
    unbounded-error communication
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references