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

文章基本信息

  • 标题:Lower Bounds for Testing Properties of Functions on Hypergrid Domains
  • 本地全文:下载
  • 作者:Eric Blais ; Sofya Raskhodnikova ; Grigory Yaroslavtsev
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2013
  • 卷号:2013
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We introduce strong, and in many cases optimal, lower bounds for the number of queries required to nonadaptively test three fundamental properties of functions f:[n]dR on the hypergrid: monotonicity, convexity, and the Lipschitz property.Our lower bounds also apply to the more restricted setting of functions f:[n]R on the line (i.e., to hypergrids with d=1), where they give optimal lower bounds for all three properties. The lower bound for testing convexity is the first lower bound for that property, and the lower bound for the Lipschitz property is new for tests with 2-sided error.We obtain our lower bounds via the connection to communication complexity established by Blais, Brody, and Matulef (2012). Our results are the first to apply this method to functions with non- hypercube domains. A key ingredient in this generalization is the set of Walsh functions, an orthonormal basis of the set of functions f:[n]dR.

  • 关键词:hypergrids; Lipschitzness; Monotonicity ; Communication complexity; convexity; Property Testing
国家哲学社会科学文献中心版权所有