On fractional block sensitivity

DOI10.4086/CJTCS.2016.008MaRDI QIDQ3187177zbMATH OpenOpenAlexFDO

Authors Raghav Kulkarni, Avishay Tal

Publication date 16 August 2016

Published in Chicago Journal of Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/cjtcs.2016.008

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• On block sensitivity and fractional block sensitivity
• Quantum certificate complexity
• A tight lower bound on certificate complexity in terms of block sensitivity and sensitivity

Cites work

• A note on quantum black-box complexity of almost all Boolean functions
• Block sensitivity of minterm-transitive functions
• Complexity measures and decision tree complexity: a survey.
• Composition limits and separating examples for some Boolean function complexity measures
• On the sensitivity of cyclically-invariant Boolean functions
• Polynomial degree vs. quantum query complexity
• Properties and applications of Boolean function composition

Cited in

(16)

• On block sensitivity and fractional block sensitivity
• Conflict complexity is lower bounded by block sensitivity
• On derandomized composition of Boolean functions
• Quantum certificate complexity
• All classical adversary methods are equivalent for total functions
• scientific article; zbMATH DE number 6913819 (Why is no real title available?)
• Low-sensitivity functions from unambiguous certificates
• Quantum distinguishing complexity, zero-error algorithms, and statistical zero knowledge
• A composition theorem for randomized query complexity
• Randomized versus deterministic decision tree size
• On query complexity measures and their relations for symmetric functions
• The power of many samples in query complexity
• Separations between combinatorial measures for transitive functions
• Decision tree complexity versus block sensitivity and degree
• Relations between monotone complexity measures based on decision tree complexity
• Quantum sabotage complexity

This page was built for publication: On fractional block sensitivity

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