@inproceedings{gopalan2008agnostically,
author = {Gopalan, Parikshit and Kalai, Adam Tauman and Klivans, Adam R.},
title = {Agnostically Learning Decision Trees},
booktitle = {Proceedings of the thirty-ninth annual ACM symposium on Theory of computing (STOC), 2008},
year = {2008},
month = {May},
abstract = {We consider the problem of learning a decision tree in the presence of arbitrary noise. More formally, we are given black-box access (a type of active learning) to an arbitrary binary function on n bits, and our output is a function whose accuracy is almost as good as that of the best size-s decision tree, where accuracy is measured over the uniform distribution on inputs.},
publisher = {ACM Press},
url = {http://approjects.co.za/?big=en-us/research/publication/agnostically-learning-decision-trees/},
pages = {527-536},
isbn = {978-1-60558-047-0},
edition = {Proceedings of the thirty-ninth annual ACM symposium on Theory of computing (STOC), 2008},
}