Speaker: Avi Wigderson
Institute for Advanced Study
Title: Restriction Access
We introduce a notion of non-black-box access to computational devices (such as circuits, formulas, decision trees, and so forth) that we call restriction access. It interpolates the gray scale between complete, clear-box access to the inner workings of the computational device and the black-box access which allows viewing only its functionality, namely input-output pairs. Restriction access allows viewing the device after some subset of its inputs have been set.
This model is very general. Different variants of restriction access, in which the values to restricted variables, the subset of free (unassigned) variables, and the restricted device are generated deterministically or randomly, in friendly or adversarial fashions, may naturally suit a variety of situations motivating this study, in computational learning, computational biology, automated proofs, cryptography and complexity theory.
Focusing on learning theory, we show that restriction access provides a setting in which one can obtain positive results for problems that have resisted attack in the black-box access model. We introduce a PAC-learning version of restriction access, and show that one can efficiently learn both decision trees and DNF formulas in this model. These two classes are not known to be learnable in the PAC model with black-box access.
Our DNF learning algorithm is obtained by a reduction to a general learning problem we call population recovery, in which random samples from an unknown distribution become available only after a random part of each was erased. More specifically, assume that every member of an unknown population is described by a vector of values (to some fixed set of attributes). The algorithm has access to random samples, each of which is a random member of the population, whose values are given only for a random subset of the attributes! From such lossy samples it must recover the population, namely all these vectors as well as the approximate probability of each.
Our algorithm to fully recover the unknown population calls for understanding another basic problem of independent interest: "robust local inversion" of matrices. The population recovery algorithm and construction of robust local inverses for some families of matrices are the main technical contributions of the paper.
Joint work with Zeev Dvir, Anup Rao and Amir Yehudayoff