@InProceedings{GRS89, author = { Sally A. Goldman and Ronald L. Rivest and Robert E. Schapire }, title = { Learning Binary Relations and Total Orders }, pages = { 46--51 }, doi = { 10.1109/SFCS.1989.63454 }, booktitle = { Proceedings Thirtieth IEEE Annual Symposium on Foundations of Computer Science }, date = { 1989 }, publisher = { IEEE }, OPTeditor = {}, OPTyear = { 1989 }, OPTmonth = { October }, eventtitle = { FOCS '89 }, eventdate = { 1989-10-30/1989-11-01 }, venue = { Research Triangle Park, North Carolina }, keywords = { adversary, binary matrix, binary relations, distinct row types, helpful teacher, instance space, learner, learning, online model, polynomial prediction algorithms, predicate, probability distribution, total orders, computational complexity, learning systems, matrix algebra }, abstract = { The problem of designing polynomial prediction algorithms for learning binary relations is studied for an online model in which the instances are drawn by the learner, by a helpful teacher, by an adversary, or according to a probability distribution on the instance space. The relation is represented as an $n\times m$ binary matrix, and results are presented when the matrix is restricted to have at most $k$ distinct row types, and when it is constrained by requiring that the predicate form a total order }, }