A tighter relation between sensitivity complexity and certificate complexity (Q5915958): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
Normalize DOI.
 
(5 intermediate revisions by 5 users not shown)
Property / DOI
 
Property / DOI: 10.1016/j.tcs.2018.08.025 / rank
Normal rank
 
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2889257031 / rank
 
Normal rank
Property / arXiv ID
 
Property / arXiv ID: 1609.04342 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Tighter Relations between Sensitivity and Other Complexity Measures / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity / rank
 
Normal rank
Property / cites work
 
Property / cites work: Sensitivity Versus Certificate Complexity of Boolean Functions / rank
 
Normal rank
Property / cites work
 
Property / cites work: Size of Sets with Small Sensitivity: A Generalization of Simon’s Lemma / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4608575 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Low-Sensitivity Functions from Unambiguous Certificates. / rank
 
Normal rank
Property / cites work
 
Property / cites work: Complexity measures and decision tree complexity: a survey. / rank
 
Normal rank
Property / cites work
 
Property / cites work: Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes / rank
 
Normal rank
Property / cites work
 
Property / cites work: A New Approach to the Sensitivity Conjecture / rank
 
Normal rank
Property / cites work
 
Property / cites work: Smooth Boolean Functions are Easy / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5368747 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the Sensitivity Conjecture for Disjunctive Normal Forms / rank
 
Normal rank
Property / cites work
 
Property / cites work: Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the Sensitivity Complexity of k-Uniform Hypergraph Properties / rank
 
Normal rank
Property / cites work
 
Property / cites work: Sensitivity Conjecture and Log-rank Conjecture for functions with small alternating numbers / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4608008 / rank
 
Normal rank
Property / cites work
 
Property / cites work: CREW PRAM<scp>s</scp> and Decision Trees / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the degree of Boolean functions as real polynomials / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the Sensitivity Conjecture / rank
 
Normal rank
Property / cites work
 
Property / cites work: The critical complexity of graph properties / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5781249 / rank
 
Normal rank
Property / Wikidata QID
 
Property / Wikidata QID: Q129318015 / rank
 
Normal rank
Property / DOI
 
Property / DOI: 10.1016/J.TCS.2018.08.025 / rank
 
Normal rank

Latest revision as of 06:20, 11 December 2024

scientific article; zbMATH DE number 7030853
Language Label Description Also known as
English
A tighter relation between sensitivity complexity and certificate complexity
scientific article; zbMATH DE number 7030853

    Statements

    A tighter relation between sensitivity complexity and certificate complexity (English)
    0 references
    0 references
    0 references
    0 references
    28 February 2019
    0 references
    sensitivity conjecture
    0 references
    sensitivity
    0 references
    block sensitivity
    0 references
    certificate complexity
    0 references
    Boolean functions
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references