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

文章基本信息

  • 标题:An Optimal Lower Bound for Monotonicity Testing over Hypergrids
  • 本地全文:下载
  • 作者:Deeparnab Chakrabarty ; C. Seshadhri
  • 期刊名称:Theory of Computing
  • 印刷版ISSN:1557-2862
  • 电子版ISSN:1557-2862
  • 出版年度:2014
  • 卷号:10
  • 页码:453-464
  • 出版社:University of Chicago
  • 摘要:$ \newcommand{\eps}{\varepsilon} \newcommand{\NN}{\mathbb{N}} $

    For positive integers $n, d$, the hypergrid $[n]^d$ is equipped with the coordinatewise product partial ordering denoted by $\prec$. A function $f: [n]^d \to \NN$ is monotone if $\forall x \prec y$, $f(x) \leq f(y)$. A function $f$ is $\eps$-far from monotone if at least an $\eps$ fraction of values must be changed to make $f$ monotone. Given a parameter $\eps$, a monotonicity tester must distinguish with high probability a monotone function from one that is $\eps$-far.

    We prove that any (adaptive, two-sided) monotonicity tester for functions $f:[n]^d \to \NN$ must make $\Omega(\eps^{-1}d\log n - \eps^{-1}\log \eps^{-1})$ queries. Recent upper bounds show the existence of $O(\eps^{-1}d \log n)$ query monotonicity testers for hypergrids. This closes the question of monotonicity testing for hypergrids over arbitrary ranges. The previous best lower bound for general hypergrids was a non-adaptive bound of $\Omega(d \log n)$.

  • 关键词:lower bounds; property testing; monotonicity testing
国家哲学社会科学文献中心版权所有