[Colloquium] TTIC Talk: Homin Lee, U of Texas at Austin

[Julia MacGlashan]

When:             *Wednesday, Jan 20 @ 11:00am*, light lunch will follow

Where:           * TTI-C Conference Room #526*, 6045 S Kenwood Ave


Who:               *Homin Lee*, University of Texas at Austin


Title:          *      **On the Learnability of Monotone Functions*



 A longstanding lacuna in the field of computational learning theory is the
learnability of succinctly representable monotone Boolean functions, i.e.,
functions that preserve the given order of the input. We show that Boolean
functions computed by polynomial-size monotone circuits are hard to learn
assuming the existence of one-way functions. Having shown the hardness of
learning general polynomial-size monotone circuits, we show that the class
of Boolean functions computed by polynomial-size depth-3 monotone circuits
are hard to learn using statistical queries. As a counterpoint, we give a
statistical query learning algorithm that can learn random polynomial-size
depth-2 monotone circuits (i.e., monotone DNF formulas).

* Host:              Julia Chuzhoy, cjulia at ttic.edu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20100119/e71f09b2/attachment-0001.htm