文章基本信息

标题：When Is Amplification Necessary for Composition in Randomized Query Complexity?
本地全文：下载
作者：Shalev Ben-David ; Mika G{"o}{"o}s ; Robin Kothari 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：176
页码：28:1-28:16
DOI：10.4230/LIPIcs.APPROX/RANDOM.2020.28
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Suppose we have randomized decision trees for an outer function f and an inner function g. The natural approach for obtaining a randomized decision tree for the composed function (fâ^~ gâ¿)(xÂ¹,â¦,xâ¿) = f(g(xÂ¹),â¦,g(xâ¿)) involves amplifying the success probability of the decision tree for g, so that a union bound can be used to bound the error probability over all the coordinates. The amplification introduces a logarithmic factor cost overhead. We study the question: When is this log factor necessary? We show that when the outer function is parity or majority, the log factor can be necessary, even for models that are more powerful than plain randomized decision trees. Our results are related to, but qualitatively strengthen in various ways, known results about decision trees with noisy inputs.
关键词：Amplification; composition; query complexity