...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>LIPIcs : Leibniz International Proceedings in Informatics >A Lifting Theorem with Applications to Symmetric Functions
【24h】

A Lifting Theorem with Applications to Symmetric Functions

机译：提升定理及其在对称函数中的应用

获取原文
   

获取外文期刊封面封底 >>

       
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We use a technique of "lifting" functions introduced by Krause and Pudlak [Theor. Comput. Sci., 1997], to amplify degree-hardness measures of a function to corresponding monomial-hardness properties of the lifted function. We then show that any symmetric function F projects onto a "lift" of another suitable symmetric function f . These two key results enable us to prove several results on the complexity of symmetric functions in various models, as given below: 1. We provide a characterization of the approximate spectral norm of symmetric functions in terms of the spectrum of the underlying predicate, affirming a conjecture of Ada et al. [APPROX-RANDOM, 2012] which has several consequences. 2. We characterize symmetric functions computable by quasi-polynomial sized Threshold of Parity circuits. 3. We show that the approximate spectral norm of a symmetric function f characterizes the (quantum and classical) bounded error communication complexity of f o XOR. 4. Finally, we characterize the weakly-unbounded error communication complexity of symmetric XOR functions, resolving a weak form of a conjecture by Shi and Zhang [Quantum Information & Computation, 2009]
机译：我们使用Krause和Pudlak [理论。计算（Sci。，1997），以将功能的度数硬度量度放大为提升功能的相应单项硬度性质。然后，我们证明任何对称函数F投射到另一个合适的对称函数f的“提升”上。这两个关键结果使我们能够证明各种模型中对称函数的复杂性的几个结果，如下所示：1.我们根据基础谓词的频谱对对称函数的近似谱范数进行了表征，确认了阿达等人的猜想。 [APPROX-RANDOM，2012]，这会带来多种后果。 2.我们描述了可通过准多项式大小的奇偶校验阈值计算的对称函数。 3.我们表明，对称函数f的近似谱范数表征了f o XOR的（量子和经典）有界误差通信复杂度。 4.最后，我们描述了对称XOR函数的弱无穷错误通信复杂性，解决了Shi和Zhang的一个弱形式的猜想[Quantum Information＆Computation，2009]

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号