文章基本信息

标题：The Power of Many Samples in Query Complexity
本地全文：下载
作者：Andrew Bassilakis ; Andrew Drucker ; Mika Göös 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-16
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：The randomized query complexity R(f) of a boolean function f : {0, 1} n → {0, 1} is famously characterized (via Yao’s minimax) by the least number of queries needed to distinguish a distribution D0 over 0-inputs from a distribution D1 over 1-inputs, maximized over all pairs (D0, D1). We ask: Does this task become easier if we allow query access to infinitely many samples from either D0 or D1? We show the answer is no: There exists a hard pair (D0, D1) such that distinguishing D∞ 0 from D∞ 1 requires Θ(R(f)) many queries. As an application, we show that for any composed function f ◦ g we have R(f ◦ g) ≥ Ω(fbs(f)R(g)) where fbs denotes fractional block sensitivity.