[Colloquium] TTI-C Talk: Rishi Saket (Georgia Tech)

[Julia MacGlashan]

When:              TOMORROW: Thursday, February 19 @ 11:00am (lunch will be
provided after talk)

Where:            TTI-C Conference Room #526, 6045 S Kenwood Ave, 5th Floor

Who:                Rishi Saket (Georgia Tech)

Title:                 Hardness of learning common concept classes


We study the inapproximability of accurately learning some common concept
classes in the Probably Approximately Correct (PAC) model. In particular we
show
the following results:

1. Intersection of two halfspaces is hard to PAC-learn beyond an accuracy of
1/2
+ \eps by an intersection of constantly many halfspaces. This improves the
previous NP-hardness result [ABFKP04] to an optimal inapproximability
factor.

2. Noisy parity (linear function) over GF(2) is hard to PAC-learn beyond an
accuracy of 1 - 2^{-d} + \eps by a degree d polynomial. This extends the
previous inapproximability for learning noisy parity by a parity given by
Hastad's 3-bit PCP [Hastad01].  

3. A two term DNF is hard to PAC-learn beyond an accuracy of 1/2 + \eps by a
constant term DNF. This improves the previous NP-hardness result [ABFKP04]
to an
optimal inapproximability factor. We also show the same inapproximability
for
learning a noisy AND by a CNF with constant clause size which extends and
simplifies previous results [FGKP06].  

4. Given the truth table of a boolean function f over d variables, it is
hard to
find an equivalent DNF formula for f with minimum number of terms to within
d^{1-\eps} of the optimal, for any \eps > 0. This improves the previous best
d^{\gamma} (\gamma bounded away from 1) inapproximability
[Feldman06][AHMPS06]
to an essentially optimal factor as the greedy Set-Cover algorithm gives an
O(d)
approximation.

The talk will define the PAC-learning framework, give an overview of the
techniques used for proving these results and sketch the reductions for some
of
them.

This is based on joint works with Subhash Khot and Parikshit Gopalan.

Contact:          Julia Chuzhoy, TTI-C		cjulia at tti-c.org
834-2490


-------------- next part --------------
A non-text attachment was scrubbed...
Name: winmail.dat
Type: application/ms-tnef
Size: 8022 bytes
Desc: not available
Url : http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20090218/f7e3df1f/attachment.bin