New perspectives on the complexity of computational learning, and other problems in theoretical computer science.

摘要

In this thesis we present the following results.;1. Learning theory, and in particular PAC learning, was introduced by Valiant [CACM 1984] and has since become a major area of research in theoretical and applied computer science. One natural question that was posed at the very inception of the field is whether there are classes of functions that are hard to learn.;PAC learning is hard under widely held conjectures such as the existence of one-way functions, and on the other hand it is known that if PAC learning is hard then P ≠ NP. We further study sufficient and necessary conditions for PAC learning to be hard, and we prove that: (1) ZK ≠ BPP implies that PAC learning is hard. (2) It is unlikely using standard techniques that one can prove that PAC learning is hard implies that ZK ≠ BPP. (3) It is unlikely using standard techniques that one can prove that P ≠ NP implies that ZK ≠ BPP.;Here, "standard techniques" refers to various classes of efficient reductions. Together, these results imply that the hardness of PAC learning lies between the non-triviality of ZK on the one hand and the hardness of NP on the other hand. Furthermore, the hardness of PAC learning lies "strictly" between the two, in the sense that most standard techniques cannot prove equivalence with either ZK ≠ BPP or NP ≠ P.;In proving these results, we show new connections between PAC learning and auxiliary-input one-way functions, which were defined by Ostrovsky and Wigderson [ISTCS 1993] to better understand ZK. We also define new problems related to PAC learning that we believe of are independent interest, and may be useful in future studies of the complexity of PAC learning.;2. A secure failure-localization (FL) protocol allows a sender to localize faulty links on a single path through a network to a receiver, even when intermediate nodes on the path behave adversarially. Such protocols were proposed as tools that enable Internet service providers to select high-performance paths through the Internet, or to enforce contractual obligations. We give the first formal definitions of security for FL protocols and prove that for such protocols, security requires each intermediate node on the path to have some shared secret information ( e.g. keys), and that every black-box construction of a secure FL protocol from a random oracle requires each intermediate node to invoke the random oracle. This suggests that achieving this kind of security is unrealistic as intermediate nodes have little incentive to participate in the real world.;3. 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 a construction of Alon and Roichman [RSA 1994] to efficiently construct 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 semi-definite covering problems, thus giving a deterministic algorithm for the quantum hypergraph cover problem of Ahslwede and Winter.