On the Sum of L1 Influences
2014pp. 132–143
Citations Over TimeTop 13% of 2014 papers
Abstract
For a function f over the discrete cube, the total L1 influence of f is defined as the sum of the L1 norm of the discrete derivatives of f in all n directions. In this work, we show that in the case of bounded functions this quantity can be upper bounded by a polynomial in the degree of f (independently of dimension n), resolving affirmatively an open problem of Aaronson and Ambainis (ITCS 2011). We also give an application of our theorem to graph theory, and discuss the connection between the study of bounded functions over the cube and the quantum query complexity of partial functions where Aaronson and Ambainis encountered this question.
Related Papers
- → Verification of the Effectiveness of P-CUBE at an Early Stage of Program Learning(2015)3 cited
- → Mathematical Lens: Math of Steel for Supermath(2014)
- RELATIONSHIP BETWEEN CUBE AND CYLINDER STRENGTHS FORHIGH STRENGTH CONCRETE(2008)
- Comparative study of methods for solving the Rubik’s Cube / Nur Syahirah Shuhaimi & Noor Fazlini Mustari(2019)
- → Solving Rubiks Cube Using Open CV(2022)