Aryeh Kontorovich
Senior Academic
Lower bounds on learning random structures with statistical queries
We show that random DNF formulas, random log-depth decision trees and random deterministic finite acceptors cannot be weakly learned with a polynomial number of statistical queries with respect to an arbitrary distribution on examples.
| Publication language | English |
| Pages | 194-208 |
| Publication status | Published - 19.11.2010 |
ASJC Scopus subject areas
Theoretical Computer Science
General Computer Science
