On the Composition of Randomized Query Complexity and Approximate Degree
- 20 August 2026
- journal article
- research article
- Published by Springer Nature in computational complexity
- Vol. 35 (2) , 10
Abstract
No abstract availableKeywords
All Related Versions
This publication has 37 references indexed in Scilit:
- Conflict complexity is lower bounded by block sensitivityTheoretical Computer Science, 2021
- Composition limits and separating examples for some boolean function complexity measuresCombinatorica, 2016
- Improved bounds for the randomized decision tree Complexity of recursive majorityRandom Structures & Algorithms, 2015
- Quantum Algorithms for Learning Symmetric Juntas via the Adversary Boundcomputational complexity, 2015
- Dual Lower Bounds for Approximate Degree and Markov-Bernstein InequalitiesLecture Notes in Computer Science, 2013
- Block sensitivity of minterm-transitive functionsTheoretical Computer Science, 2011
- Block sensitivity of weakly symmetric functionsTheoretical Computer Science, 2007
- Robust Polynomials and Quantum AlgorithmsTheory of Computing Systems, 2007
- Sensitivity vs. block sensitivity of Boolean functionsCombinatorica, 1995
- On the degree of boolean functions as real polynomialscomputational complexity, 1994