New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity
From MaRDI portal
Publication:5090948
DOI10.4230/LIPICS.FSTTCS.2018.13OpenAlexW2907788305MaRDI QIDQ5090948FDOQ5090948
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
Recommendations
Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)
Cites Work
- Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
- On the degree of Boolean functions as real polynomials
- Sensitivity vs. block sensitivity of Boolean functions
- CREW PRAM<scp>s</scp> and Decision Trees
- Complexity measures and decision tree complexity: a survey.
- Polynomial degree vs. quantum query complexity
- Sensitivity versus block sensitivity of Boolean functions
- Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions
- A tight ω(loglog n)-bound on the time for parallel RAM's to compute nondegenerated boolean functions
- Sensitivity versus certificate complexity of Boolean functions
- Composition limits and separating examples for some Boolean function complexity measures
- Tighter relations between sensitivity and other complexity measures
- Properties and applications of Boolean function composition
- Title not available (Why is that?)
- A tight lower bound on certificate complexity in terms of block sensitivity and sensitivity
Cited In (2)
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)
