首页    期刊浏览 2024年11月30日 星期六
登录注册

文章基本信息

  • 标题:Rectangles Are Nonnegative Juntas
  • 本地全文:下载
  • 作者:Mika Göös ; Shachar Lovett ; Raghu Meka
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2014
  • 卷号:2014
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We develop a new method to prove communication lower bounds for composed functions of the form f g n where f is any boolean function on n inputs and g is a sufficiently ``hard'' two-party gadget. Our main structure theorem states that each rectangle in the communication matrix of f g n can be simulated by a \emph{nonnegative combination of juntas}. This is the strongest yet formalization for the intuition that each low-communication randomized protocol can only ``query'' few inputs of f as encoded by the gadget g . Consequently, we characterize the communication complexity of f g n in all known one-sided zero-communication models by a corresponding query complexity measure of f . These models in turn capture important lower bound techniques such as corruption, smooth rectangle bound, relaxed partition bound, and extended discrepancy.

国家哲学社会科学文献中心版权所有