## Constructing Hard Functions from Learning Algorithms

by Adam Klivans, Pravesh Kothari, and Igor Oliviera.

#### Or's comments

The paper shows that designing learning algorithms for a circuit class
C can yield circuit lower bounds against C. This has been shown
before in a paper of Fortnow and Klivans, but the current paper gives a
straightforward and simple proof, which is also much stronger quantitatively.

One nice special case of one of their results is that any non-trivial
learning algorithm for a circuit class C in the exact learning model
(with membership and equivalence queries) separates C from EXP.
By *non-trivial* they mean makes less that $2^n$ queries
(and spends at most exponential time in total).
I see it as a kind of an analogue to Ryan Williams works, with SAT
algorithms replaced with learning. The nice thing here is that it
shows that learning algorithms allow us to separate C from EXP and not
just from NEXP as in Ryan's works.

#### Oded's comments

As far as I can see, the instantiation highlighted by Or does
not appear explicitly in the paper, although it is elluded to in
the concluding section (Sec. VI).
Also, Thm 1 neglectly omits the (crucial) condition $M<2^n$,
which does appear in the formal statements in Sec. III.

I wish to stress that the paper provides an array of results
for various learning models, ranging from exact learning
(mentioned above) to standard PAC and Statistical learning models.

#### The original abstract

See CCC'13 proceedings.

Back to
list of Oded's choices.