© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

Computational Complexity

How Low can Approximate Degree and Quantum Query Complexity be for Total Boolean Functions?

Andris Ambainis, Ronald de Wolf

Published May 8, 2014• 8 citations

DOI: 10.1007/s00037-014-0083-2

Related papers

Boolean Functions with a Low Polynomial Degree and Quantum Query Algorithms

Raitis Ozols, Rūsiņš Freivalds, Jevgeņijs Ivanovs +5 more

Lecture notes in computer science•Jan 1, 2005•2 citations

Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity

Dana Ron, Ronitt Rubinfeld, Muli Safra +1 more

Lecture notes in computer science•Jan 1, 2011•2 citations

Approximating the influence of monotone boolean functions in O(√n) query complexity

Dana Ron, Ronitt Rubinfeld, Muli Safra +1 more

International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques•Aug 17, 2011•3 citations

A General Composition Theorem for Approximate Degree

Samruddhi Pednekar, Supartha Podder

A longstanding open question in Boolean function complexity asks whether approximate degree composes multiplicatively under block composition. Although a general multiplicative upper bound is known, matching lower bounds have previously been established only for restricted classes of functions. We resolve this question for all total Boolean functions by proving the matching lower bound. Together with Sherstov's upper bound, our result shows that, for every pair of total Boolean functions $f:\{0,1\}^n\to\{0,1\}$ and $g:\{0,1\}^m\to\{0,1\}$, \[ \widetilde{deg}(f\circ g) = Θ\!\left( \widetilde{deg}(f)\,\widetilde{deg}(g) \right), \] where $\widetilde{deg}$ denotes constant-error approximate degree. We also consider the analogous question for exact quantum query complexity and give a counterexample showing that multiplicative composition fails in this setting.

cs.CCCross-listedarXiv:2609.30139•Sep 25, 2026•0 citations

How Low Can Approximate Degree and Quantum Query Complexity be for Total Boolean Functions?

Andris Ambainis, Ronald de Wolf

It has long been known that any Boolean function that depends on n input variables has both degree and exact quantum query complexity of Omega(log n), and that this bound is achieved for some functions. In this paper we study the case of approximate degree and bounded-error quantum query complexity. We show that for these measures the correct lower bound is Omega(log n / loglog n), and we exhibit quantum algorithms for two functions where this bound is achieved.

arXiv:1206.0717•Jun 4, 2012•0 citations

How Low Can Approximate Degree and Quantum Query Complexity Be for Total Boolean Functions?

Andris Ambainis, Ronald de Wolf

It has long been known that any Boolean function that depends on n input variables has both degree and exact quantum query complexity of Omega(log n), and that this bound is achieved for some functions. In this paper we study the case of approximate degree and bounded-error quantum query complexity. We show that for these measures the correct lower bound is Omega(log n/log log n), and we exhibit quantum algorithms for two functions where this bound is achieved.

IEEE Conference on Computational Complexity (CCC)•Jun 1, 2013•3 citations

Approximating the Influence of Monotone Boolean Functions in

O(\sqrt{n})

Query Complexity

A longstanding open question in Boolean function complexity asks whether approximate degree composes multiplicatively under block composition. Although a general multiplicative upper bound is known, matching lower bounds have previously been established only for restricted classes of functions. We resolve this question for all total Boolean functions by proving the matching lower bound. Together with Sherstov's upper bound, our result shows that, for every pair of total Boolean functions

f:\{0,1\}^n\to\{0,1\}

and

g:\{0,1\}^m\to\{0,1\}

,

\widetilde{deg}(f\circ g) = Θ\!\left( \widetilde{deg}(f)\,\widetilde{deg}(g) \right),

where

\widetilde{deg}

denotes constant-error approximate degree. We also consider the analogous question for exact quantum query complexity and give a counterexample showing that multiplicative composition fails in this setting.