首页 | 官方网站   微博 | 高级检索  
     


On the sum of the L1 influences of bounded functions
Authors:Yuval Filmus  Hamed Hatami  Nathan Keller  Noam Lifshitz
Abstract:Let f: {-1, 1}n → -1, 1] have degree d as a multilinear polynomial. It is well-known that the total influence of f is at most d. Aaronson and Ambainis asked whether the total L1 influence of f can also be bounded as a function of d. Ba?kurs and Bavarian answered this question in the affirmative, providing a bound of O(d3) for general functions and O(d2) for homogeneous functions. We improve on their results by providing a bound of d2 for general functions and O(d log d) for homogeneous functions. In addition, we prove a bound of d/(2p) + o(d) for monotone functions, and provide a matching example.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司    京ICP备09084417号-23

京公网安备 11010802026262号