Influence in Completely Bounded Block-multilinear Forms and Classical Simulation of Quantum Algorithms

Nikhil Bansal, Makrand Sinha, Ronald de Wolf

The Aaronson-Ambainis conjecture (Theory of Computing '14) says that every low-degree bounded polynomial on the Boolean hypercube has an influential variable. This conjecture, if t…