Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications
Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications
复制标题
使用悲观估计器和应用程序对 Ahlswede-Winter 矩阵值切尔诺夫界限进行去随机化
作者：
Avi Wigderson;David Xiao
Ahlswede和Winter（IEEE Trans. Inf. Th. 2002）引入了矩阵值随机变量的一个界，它是实值随机变量的一个界的非平凡推广。我们提出了一个有效的去随机化他们的界限使用悲观估计的方法（见Raghavan（JCSS 1988））。因此，我们去随机化了Alon和Roichman（RSA 1994）在任何（可能非阿贝尔）群上的对数度扩展Cayley图的有效构造。这给出了Shpilka和Wigderson（STOC 2004）的同态测试问题的最优解。我们还将这些悲观估计应用到半定覆盖问题的求解中，从而给出了Ahslwede和Winter量子超图覆盖问题的一个确定性算法。
Ahlswede and Winter (IEEE Trans. Inf. Th. 2002) introduced a Chernoff bound for matrix-valued random variables, which is a non-trivial generalization of the usual Chernoff bound for real-valued random variables. We present an efficient derandomization of their bound using the method of pessimistic estimators (see Raghavan (JCSS 1988)). As a consequence, we derandomize an efficient construction by Alon and Roichman (RSA 1994) of an expanding Cayley graph of logarithmic degree on any (possibly non-abelian) group. This gives an optimal solution to the homomorphism testing problem of Shpilka and Wigderson (STOC 2004). We also apply these pessimistic estimators to the problem of solving semidefinite covering problems, thus giving a deterministic algorithm for the quantum hypergraph cover problem of Ahslwede and Winter.