@InProceedings{GoldmanRivestSchapire-1989-FOCS-BinaryRelations,
  author = 	 { Sally A. Goldman and Ronald L. Rivest and Robert E. Schapire },
  title = 	 { Learning Binary Relations and Total Orders },
  booktitle =    { Proceedings Thirtieth IEEE Annual Symposium on Foundations of Computer Science },
  publisher =    { IEEE },
  pages = 	 { 46--51 },
  doi =          { 10.1109/SFCS.1989.63454 }, 
  date =         { 1989 },                  
  OPTyear = 	 { 1989 },
  OPTmonth = 	 { October },
  eventtitle =   { FOCS '89 },
  eventdate =    { 1989-10-30/1989-11-01 },                  
  venue =        { Research Triangle Park, North Carolina },                   
  OPTcrossref =  {},
  OPTkey = 	 {},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTorganization = {},
  OPTnote = 	 {},
  OPTannote = 	 {},
  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
                   }, 
}