Improved Direct Product Theorems for Randomized Query Complexity - Computer Science > Computational ComplexityReportar como inadecuado




Improved Direct Product Theorems for Randomized Query Complexity - Computer Science > Computational Complexity - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: The direct product problem is a fundamental question in complexity theorywhich seeks to understand how the difficulty of computing a function on each ofk independent inputs scales with k. We prove the following direct producttheorem DPT for query complexity: if every T-query algorithm has successprobability at most 1 - eps in computing the Boolean function f on inputdistribution Mu, then for alpha <= 1, every alpha eps Tk-query algorithm hassuccess probability at most 2^{alpha eps}1 - eps^k in computing the k-folddirect product f^k correctly on k independent inputs from Mu. In light ofexamples due to Shaltiel, this statement gives an essentially optimal tradeoffbetween the query bound and the error probability. As a corollary, we show thatfor an absolute constant alpha > 0, the worst-case success probability of anyalpha R 2fk-query randomized algorithm for f^k falls exponentially with k.The best previous statement of this type, due to Klauck, Spalek, and de Wolf,required a query bound of Obsfk. The proof involves defining and analyzinga collection of martingales associated with an algorithm attempting to solvef^k. Our method is quite general and yields a new XOR lemma and threshold DPTfor the query model, as well as DPTs for the query complexity of learningtasks, search problems, and tasks involving interaction with dyamic entities.We also give a version of our DPT in which decision tree size is the resourceof interest.



Autor: Andrew Drucker

Fuente: https://arxiv.org/







Documentos relacionados