New Perspectives on the Complexity of Computational Learning, and Other Problems in Theoretical Computer Science (thesis)
In this thesis we present the following results.
• 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
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.
• 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.
• 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.