Published on *Computer Science Department at Princeton University* (https://www.cs.princeton.edu)

Report ID:

TR-866-09

Authors:

Xiao, David [1]

Date:

July 2009

Pages:

158

Download Formats:

[PDF [2]]

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

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.• 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.

**Links**

[1] https://www.cs.princeton.edu/research/techreps/author/359

[2] ftp://ftp.cs.princeton.edu/techreports/2009/866.pdf