New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity

DOI10.4230/LIPIcs.FSTTCS.2018.13OpenAlexW2907788305MaRDI QIDQ5090948

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

Boolean functionscomplexity measuressensitivity conjecture

Mathematics Subject Classification ID

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

Related Items (1)

Tight bounds on sensitivity and block sensitivity of some classes of transitive functions

Cites Work

• Unnamed Item
• On the degree of Boolean functions as real polynomials
• Composition limits and separating examples for some Boolean function complexity measures
• Complexity measures and decision tree complexity: a survey.
• Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions
• Sensitivity vs. block sensitivity of Boolean functions
• Sensitivity versus block sensitivity of Boolean functions
• Polynomial degree vs. quantum query complexity
• A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity
• Properties and applications of boolean function composition
• A tight ω(loglog n)-bound on the time for parallel RAM's to compute nondegenerated boolean functions
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• CREW PRAM<scp>s</scp> and Decision Trees
• Tighter Relations between Sensitivity and Other Complexity Measures
• Sensitivity Versus Certificate Complexity of Boolean Functions

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