The influence lower bound via query elimination

DOI10.4086/TOC.2011.V007A010MaRDI QIDQ2913796zbMATHOpenAlexFDO

Authors Rahul Jain, Shengyu Zhang

Publication date 27 September 2012

Published in Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.4086/toc.2011.v007a010

zbMATH Keywords

influence of variablesrandomized query complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity
• Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity
• Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables
• The Zero-Error Randomized Query Complexity of the Pointer Function
• A lower bound on the quantum query complexity of read-once functions

Cited in

(2)

• Properly learning decision trees in almost polynomial time
• Influences of Fourier completely bounded polynomials and classical simulation of quantum algorithms

This page was built for publication: The influence lower bound via query elimination

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2913796)