New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity

DOI10.4230/LIPICS.FSTTCS.2018.13MaRDI QIDQ5090948zbMATH OpenOpenAlexFDO

Authors Siddhesh Chaubal, Anna Gál

Publication date 21 July 2022

Full work available at URL https://doi.org/10.4230/LIPIcs.FSTTCS.2018.13

zbMATH Keywords

complexity measuresBoolean functionssensitivity conjecture

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Recommendations

• Sensitivity vs. block sensitivity of Boolean functions
• Sensitivity versus block sensitivity of Boolean functions
• On the sensitivity conjecture
• On block sensitivity and fractional block sensitivity
• Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions

Cites work

• scientific article; zbMATH DE number 6789278 (Why is no real title available?)
• A tight lower bound on certificate complexity in terms of block sensitivity and sensitivity
• A tight ω(loglog n)-bound on the time for parallel RAM's to compute nondegenerated boolean functions
• CREW PRAM<scp>s</scp> and Decision Trees
• Complexity measures and decision tree complexity: a survey.
• Composition limits and separating examples for some Boolean function complexity measures
• On the degree of Boolean functions as real polynomials
• Polynomial degree vs. quantum query complexity
• Properties and applications of Boolean function composition
• Sensitivity versus block sensitivity of Boolean functions
• Sensitivity versus certificate complexity of Boolean functions
• Sensitivity vs. block sensitivity of Boolean functions
• Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions
• Tighter relations between sensitivity and other complexity measures
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes

Cited in

(2)

• Tight bounds on sensitivity and block sensitivity of some classes of transitive functions
• On block sensitivity and fractional block sensitivity

This page was built for publication: New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090948)