Computation Complexity and Computational Learning share many aspects and goals. We both analyze and compare different models of computation either to understand what they can compute or how to find the appropriate model to fit some data. No surprise that many of the tools developed in one area have use in the other. This month's paper exemplifies the connection; it uses tools in complexity to get a nice learning theory result which in turn has very nice implications in complexity theory.

Nader Bshouty, Richard Cleve, Ricard Gavaldà, Sampath Kannan and Christino Tamon

The main result shows how to learn circuits probabilistically with equivalence queries and an NP oracle. An equivalence query given a circuit C trying to learn a language L, either says C is correct or gives an input where it fails. The proof uses a clever divide and conquer argument built upon Jerrum, Valiant and Vazirani's technique for random sampling with an NP oracle.

Kobler and Watanabe observe that if SAT has small circuits we can
answer equivalence queries to SAT with an NP oracle. Applying Bshouty
et. al. they show that
if SAT has polynomial-size circuits than the polynomial-time hierarchy
collapses to ZPP^{NP}.

Sengupta noticed that old results give a consequence of PH in
S_{2}^{p} if SAT has small circuits. This strengthens
Kobler and Watanabe because of
Jin-Yi Cai's result showing
that S_{2}^{p} is contained in
ZPP^{NP}. Cai's paper uses many techniques similar to Bshouty
et. al. Shaltiel and Umans have a recent result
giving weaker
assumptions for derandomizing S_{2}^{p} by
derandomizing random sampling.

If SAT does not small circuits, the Bshouty et. al. algorithm produces a small set of inputs that give a co-NP proof of this fact. Pavan, Sengupta and myself applied this fact to the two queries problem.

## No comments:

## Post a Comment