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

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)