On block sensitivity and fractional block sensitivity

DOI10.1134/S1995080218070041zbMath1400.68079arXiv1810.02393OpenAlexW2892211326MaRDI QIDQ1992105

Andris Ambainis, Jevgēnijs Vihrovs, Krišjānis Prūsis

Publication date: 2 November 2018

Published in: Lobachevskii Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1810.02393

zbMATH Keywords

query complexityblock sensitivity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Unnamed Item
• Composition limits and separating examples for some Boolean function complexity measures
• Complexity measures and decision tree complexity: a survey.
• Quantum certificate complexity
• Properties and applications of boolean function composition
• Separations in query complexity using cheat sheets

This page was built for publication: On block sensitivity and fractional block sensitivity