论文标题
用于认证单调功能的最佳算法
An Optimal Algorithm for Certifying Monotone Functions
论文作者
论文摘要
给定查询访问单调函数$ f \ colon \ {0,1 \}^n \ to \ {0,1 \} $带有证书复杂性$ C（f）$和一个输入$ x^{\ star} $ $ f（x^{\ star}）$。我们的算法使$ o（c（f）\ cdot \ log n）$查询到$ f $，它与此问题的信息理论下限相匹配，并解决了在Blanc，Koch，Koch，Lange和Tan [BKLT22的STOC '22 Paper of STOC '22 Paper上提出的具体问题。 我们将此结果扩展到一种算法，该算法找到了带有$ O（c（f）\ cdot \ log n）$ QUERIES的实价单调函数的尺寸-2C（F）$证书。我们还以硬度结果补充算法，在其中，我们表明在$ x^{\ star} $中找到最短的证书可能需要$ω\ left（\ binom {n} {c（f）} \ right）$ queries $在最坏的情况下。
Given query access to a monotone function $f\colon\{0,1\}^n\to\{0,1\}$ with certificate complexity $C(f)$ and an input $x^{\star}$, we design an algorithm that outputs a size-$C(f)$ subset of $x^{\star}$ certifying the value of $f(x^{\star})$. Our algorithm makes $O(C(f) \cdot \log n)$ queries to $f$, which matches the information-theoretic lower bound for this problem and resolves the concrete open question posed in the STOC '22 paper of Blanc, Koch, Lange, and Tan [BKLT22]. We extend this result to an algorithm that finds a size-$2C(f)$ certificate for a real-valued monotone function with $O(C(f) \cdot \log n)$ queries. We also complement our algorithms with a hardness result, in which we show that finding the shortest possible certificate in $x^{\star}$ may require $Ω\left(\binom{n}{C(f)}\right)$ queries in the worst case.
