Query Complexity in Expectation
Query Complexity in Expectation
复制标题
DOI：
10.1007/978-3-662-47672-7_62
复制
发表时间：
2014-11
期刊：
影响因子：
--
通讯作者：
Jędrzej Kaniewski;Troy Lee;R. D. Wolf
中科院分区：
文献类型：
--
作者：
Jędrzej Kaniewski;Troy Lee;R. D. Wolf
我们研究了计算期望函数的查询复杂度。这就要求算法在输入时输出一个期望值等于的非负随机变量，并尽可能少地使用对输入的查询。我们分别用两个多项式的非负文字度和平方和度来刻画随机化和量子查询的复杂性。我们观察到，量子复杂性可以无限小于经典复杂性的一些功能，但可以在最多多项式小于布尔函数。这些查询复杂性与多面体的扩展复杂性有关（并且由多面体的扩展复杂性激发）。多面体的线性扩张复杂性是用期望中松弛矩阵的随机化通信复杂性来刻画的，而半定扩张复杂性是用类似的量子模型来刻画的。由于查询复杂度可以作为相关函数的通信复杂度的上界，因此我们可以通过构造有效的量子查询算法来得到psd扩展复杂度的上界。作为一个例子，我们给出了一个指数封闭的逐项近似的松弛矩阵的完美匹配多面体与psd秩。最后，我们表明随机和量子查询复杂性的预期对应的Sherali-Adams和拉瑟尔层次，分别。
We study the query complexity of computing a functionin expectation. This requires the algorithm on inputto output a nonnegative random variable whose expectation equals, using as few queries to the inputas possible. We exactly characterize both the randomized and the quantum query complexity by two polynomial degrees, the nonnegative literal degree and the sum-of-squares degree, respectively. We observe that the quantum complexity can be unboundedly smaller than the classical complexity for some functions, but can be at most polynomially smaller for Boolean functions. These query complexities relate to (and are motivated by) the extension complexity of polytopes. Thelinearextension complexity of a polytope is characterized by the randomizedcommunicationcomplexity of computing its slack matrix in expectation, and thesemidefinite(psd) extension complexity is characterized by the analogous quantum model. Since query complexity can be used to upper bound communication complexity of related functions, we can derive some upper bounds on psd extension complexity by constructing efficient quantum query algorithms. As an example we give an exponentially-close entrywise approximation of the slack matrix of the perfect matching polytope with psd-rank only. Finally, we show randomized and quantum query complexity in expectation corresponds to the Sherali-Adams and Lasserre hierarchies, respectively.