The influence lower bound via query elimination

DOI10.4086/TOC.2011.V007A010zbMATH Open1247.68101OpenAlexW2141660808MaRDI QIDQ2913796FDOQ2913796

Shengyu Zhang, Rahul Jain

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

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

zbMATH Keywords

influence of variablesrandomized query complexity

Mathematics Subject Classification ID

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

Cited In (2)

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

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)