For hazard-free extensions of Boolean functions, u-sensitivity, u-block sensitivity, u-certificate complexity and u-query complexity are linearly equivalent, yielding Du = O(Ru^2) and Du = O(Qu^4).
Quantum Lower Bounds by Quantum Arguments
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
fields
cs.CC 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Sensitivity and Query Complexity under Uncertainty
For hazard-free extensions of Boolean functions, u-sensitivity, u-block sensitivity, u-certificate complexity and u-query complexity are linearly equivalent, yielding Du = O(Ru^2) and Du = O(Qu^4).