文章基本信息
- 标题：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
