For every Boolean f, bounded-error quantum and classical deterministic communication complexity of f ∘ AND₂ are polynomially related up to polylog n, both characterized by log of De Morgan sparsity of f.
Complexity measures and decision tree complexity: a survey
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
representative citing papers
The 2D HLF problem lies in QNC^0 but not in AC^0, with an exponential average-case correlation lower bound against AC^0 circuits.
Exposition of the result that Boolean degree one functions on J_q(n,k) are trivial when min(k,n-k) >= 2 and n is large enough.
citing papers explorer
-
Quantum-Classical Equivalence for AND-Functions
For every Boolean f, bounded-error quantum and classical deterministic communication complexity of f ∘ AND₂ are polynomially related up to polylog n, both characterized by log of De Morgan sparsity of f.
-
Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
The 2D HLF problem lies in QNC^0 but not in AC^0, with an exponential average-case correlation lower bound against AC^0 circuits.
-
Boolean degree one functions on the Grassmann scheme
Exposition of the result that Boolean degree one functions on J_q(n,k) are trivial when min(k,n-k) >= 2 and n is large enough.