文章基本信息

标题：The Power of Many Samples in Query Complexity
本地全文：下载
作者：Andrew Bassilakis ; Andrew Drucker ; Mika G{"o}{"o}s 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：168
页码：9:1-9:18
DOI：10.4230/LIPIcs.ICALP.2020.9
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：The randomized query complexity ð-±(f) of a boolean function f: {0,1}â¿ â' {0,1} is famously characterized (via Yaoâs minimax) by the least number of queries needed to distinguish a distribution ð'Yâ, over 0-inputs from a distribution ð'Yâ, over 1-inputs, maximized over all pairs (ð'Yâ,,ð'Yâ,). We ask: Does this task become easier if we allow query access to infinitely many samples from either ð'Yâ, or ð'Yâ,? We show the answer is no: There exists a hard pair (ð'Yâ,,ð'Yâ,) such that distinguishing ð'Yâ,^â^Z from ð'Yâ,^â^Z requires Î~(ð-±(f)) many queries. As an application, we show that for any composed function fâ^~g we have ð-±(fâ^~g) â¥ Î©(fbs(f)ð-±(g)) where fbs denotes fractional block sensitivity.
关键词：Query complexity; Composition theorems