@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
},
}