**Description: **We are studying problems where a machine learning system sees examples and produces hypotheses which are represented by logical formulae. This generic framework fits many applications from learning moves for Chess to identifying whether molecules will work well as drugs. Our theoretical work aims to characterize the computational complexity of these problems, i.e. how easy or hard they are to solve. Our work includes developing algorithms which are provably correct and efficient, and proving lower bounds that show limitations on the efficiency of any algorithm for such problems.

This work is partly supported by NSF grant IIS-0099446.

**Members:**

**Publications:**

- M. Arias, R. Khardon and J. Maloberti, Learning Horn Expressions with LogAn-H,
*Journal of Machine Learning Research*, Vol 8, pp549--587 , 2007 [+]

**Authors:**M. Arias, R. Khardon and J. MalobertiJournal of Machine Learning Research

Vol 8, pp549--587**Year:**2007**Url:**http://www.cs.tufts.edu/~roni/PUB/loganh-JMLR.pdf**Associated Research Topics:****Affiliated Tufts Members:****Tufts / Purdue Alumni:** - Arias, M. and Khardon, R., Complexity parameters for first order structures,
*Machine Learning*, Volume 64, pages 121-144, 2006 [+]

**Authors:**Arias, M. and Khardon, R.Machine Learning

Volume 64, pages 121-144**Year:**2006**Url:**http://www.cs.tufts.edu/~roni/PUB/FOVCD-MLJ.pdf**Associated Research Topics:****Affiliated Tufts Members:****Tufts / Purdue Alumni:** - M. Arias and R. Khardon, The Subsumption Lattice and Query Learning,
*Journal of Computer and System Sciences*, Volume 72, Issue 1, Pages 72-94, 2006 [+]

**Authors:**M. Arias and R. KhardonJournal of Computer and System Sciences

Volume 72, Issue 1, Pages 72-94**Year:**2006**Url:**http://www.cs.tufts.edu/~roni/PUB/JCSS-subsumption.ps**Associated Research Topics:****Affiliated Tufts Members:****Tufts / Purdue Alumni:** - M. Arias and R. Khardon, The Subsumption Lattice and Query Learning,
*In the Proceedings of the International Conference on Algorithmic Learning Theory*, 2004 [+]

**Authors:**M. Arias and R. KhardonIn the Proceedings of the International Conference on Algorithmic Learning Theory

**Year:**2004**Associated Research Topics:****Affiliated Tufts Members:****Tufts / Purdue Alumni:** - Arias, M. and Khardon, R., Complexity Parameters for First Order Classes,
*International conference on Inductive Logic Programming*, pp. 22-37 , 2003 [+]

**Authors:**Arias, M. and Khardon, R.International conference on Inductive Logic Programming

pp. 22-37**Year:**2003**Associated Research Topics:****Affiliated Tufts Members:****Tufts / Purdue Alumni:** - Arias, M. and Khardon, R., Learning closed Horn expressions,
*Information and Computation*, vol. 178, pp. 214-240 , 2002 [+]

**Authors:**Arias, M. and Khardon, R.Information and Computation

vol. 178, pp. 214-240**Year:**2002**Url:**http://www.cs.tufts.edu/~roni/PUB/ClosedHorn.ps**Associated Research Topics:****Affiliated Tufts Members:****Tufts / Purdue Alumni:** - Khardon, R., Recent Progress in Learning Horn Expressions with Queries,
*Workshop Notes. Machine Intelligence 17*, 2000 [+]

**Authors:**Khardon, R.Workshop Notes. Machine Intelligence 17

**Year:**2000**Url:**http://www.cs.tufts.edu/~roni/PUB/MI17.ps**Associated Research Topics:****Affiliated Tufts Members:****Tufts / Purdue Alumni:**None - Khardon, R., Learning Horn Expressions with LogAn-H,
*Proceedings of the International Conference on Machine Learning*, pp. 471-478, 2000 [+]

**Authors:**Khardon, R.Proceedings of the International Conference on Machine Learning

pp. 471-478**Year:**2000**Associated Research Topics:****Affiliated Tufts Members:****Tufts / Purdue Alumni:**None - Arias, M. and Khardon, R., A new algorithm for learning range restricted Horn expressions,
*International conference on Inductive Logic Programming*, Springer LNAI, pages 21-39., 2000 [+]

**Authors:**Arias, M. and Khardon, R.International conference on Inductive Logic Programming

Springer LNAI, pages 21-39.**Year:**2000**Url:**http://www.eecs.tufts.edu/~roni/PUB/ILP2K.us.pdf**Associated Research Topics:****Affiliated Tufts Members:****Tufts / Purdue Alumni:** - Khardon, R., D. Roth, L. G. Valiant, Relational Learning for NLP using Linear Threshold Elements,
*Proceedings of the International Joint Conference of Artificial Intelligence*, pp. 911-917 , 1999 [+]

**Authors:**Khardon, R., D. Roth, L. G. ValiantProceedings of the International Joint Conference of Artificial Intelligence

pp. 911-917**Year:**1999**Url:**http://www.cs.tufts.edu/~roni/PUB/rel-ijcai99.us.ps**Associated Research Topics:****Affiliated Tufts Members:****Tufts / Purdue Alumni:**None - Khardon, R., Learning Function Free Horn Expressions,
*Machine Learning*, vol. 37, 1999 [+]

**Authors:**Khardon, R.Machine Learning

vol. 37**Year:**1999**Url:**http://www.cs.tufts.edu/~roni/PUB/FFHorn.ps**Associated Research Topics:****Affiliated Tufts Members:****Tufts / Purdue Alumni:**None - Khardon, R., Learning Range-Restricted Horn Expressions,
*Proceedings of the Fourth European Conference on Computational Learning Theory*, pp. 111-125 , 1999 [+]

**Authors:**Khardon, R.Proceedings of the Fourth European Conference on Computational Learning Theory

pp. 111-125**Year:**1999**Url:**http://www.cs.tufts.edu/~roni/PUB/ec99post.ps**Associated Research Topics:****Affiliated Tufts Members:****Tufts / Purdue Alumni:**None - Khardon, R., Learning First Order Universal Horn Expressions,
*International conference on Computational Learning Theory*, pp. 154-165 1998 , 1998 [+]

**Authors:**Khardon, R.International conference on Computational Learning Theory

pp. 154-165 1998**Year:**1998**Associated Research Topics:****Affiliated Tufts Members:****Tufts / Purdue Alumni:**None