In the first half of the class, we showed that, assuming that the RSA public-key cryptosystem is hard to break, boolean formulas and log-depth circuits are not PAC predictable. The lecture was based on Kearns and Valiant's paper Cryptographic Limitations on Learning Boolean Formulae and Finite Automata.
In the second half of the class, we saw an example of a PAC reduction, namely, we showed how DNF formulas PAC-reduce to monotone DNF formulas. Formal definitions and proofs are left for the next lecture.
No comments:
Post a Comment