{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:33:32Z","timestamp":1787340812841,"version":"build-2736575974"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1993,10]]},"abstract":"<jats:p>The problem of learning a binary relation between two sets of objects or between a set and itself is studied. This paper represents a binary relation between a set of size n and a set of size m as an $n \\times m$ matrix of bits whose $(i,j)$ entry is 1 if and only if the relation holds between the corresponding elements of the two sets. Polynomial prediction algorithms are presented for learning binary relations in an extended on-line learning model, where the examples are drawn by the learner, by a helpful teacher, by an adversary, or according to a uniform probability distribution on the instance space.<\/jats:p>\n                  <jats:p>The first part of this paper presents results for the case in which the matrix of the relation has at most k row types. It presents upper and lower bounds on the number of prediction mistakes any prediction algorithm makes when learning such a matrix under the extended on-line learning model. Furthermore, it describes a technique that simplifies the proof of expected mistake bounds against a randomly chosen query sequence.<\/jats:p>\n                  <jats:p>In the second part of this paper the problem of learning a binary relation that is a total order on a set is considered. A general technique using a fully polynomial randomized approximation scheme (fpras) to implement a randomized version of the halving algorithm is described. This technique is applied to the problem of learning a total order, through the use of an fpras for counting the number of extensions of a partial order, to obtain a polynomial prediction algorithm that with high probability makes at most $n\\lg n + (\\lg e)\\lg n$ mistakes when an adversary selects the query sequence. The case in which a teacher or the learner selects the query sequence is also considered<\/jats:p>","DOI":"10.1137\/0222062","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:38:56Z","timestamp":1109227136000},"page":"1006-1034","source":"Crossref","is-referenced-by-count":35,"title":["Learning Binary Relations and Total Orders"],"prefix":"10.1137","volume":"22","author":[{"given":"Sally A.","family":"Goldman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ronald L.","family":"Rivest","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert E.","family":"Schapire","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(87)90052-6"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022821128753"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90045-X"},{"key":"R4","first-page":"1224","volume":"13","author":"Barzdin J.","year":"1972","journal-title":"Soviet Math. Dok."},{"key":"R5","doi-asserted-by":"crossref","unstructured":"A. Blum,  An  $\\tilde{O}(n^{0.4})$-approximation algorithm for  3-coloring,  Procceedings of the Twenth First Annual ACM Symposium on Theory of Computing,  1989,  535\u2013542","DOI":"10.1145\/73007.73058"},{"key":"R6","volume-title":"Introduction to the Theory of Groups of Finite Order","author":"Carmichael R.","year":"1937"},{"key":"R7","unstructured":"W. Chen,  1991, personal communication"},{"key":"R8","volume-title":"Introduction to algorithms","author":"Cormen Thomas H.","year":"1990"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/0217060"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1145\/102782.102783"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"S. A. Goldman, Ph.D. Thesis,  Learning Binary Relations, Total Orders, and Read-once Formulas, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA,  1990","DOI":"10.21236\/ADA221643"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"S. A. Goldman, M. K. Warmuth,  Learning binary relations with weighted majority voting, Proc. of the Sixth Annual Workshop on Computational Learning Theory, July 1993, to appear","DOI":"10.1145\/168304.168396"},{"key":"R13","volume-title":"Table of integrals, series, and products","author":"Gradshteyn T.","year":"2000"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(91)90042-Z"},{"key":"R15","unstructured":"D. Haussler, N. Littlestone, M. Warmuth,  Expected mistake bounds for on-line learning algorithms,  1988, unpublished manuscript"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/0218077"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1007\/BF00565647"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"N. Linial, U. Vazirani,  Graph products and chromatic numbers,  Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC,  1989,  124\u2013128","DOI":"10.1109\/SFCS.1989.63466"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022869011914"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1009"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970203"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176990349"},{"key":"R23","unstructured":"Ronald L. Rivest, Robert Sloan,  Learning complicated concepts reliably and usefully (extended abstract),  Proceedings of the 1988 Workshop on Computational Learning Theory (Cambridge, MA, 1988), Morgan Kaufmann, San Mateo, CA,  1989,  69\u201379 1 109 724"},{"key":"R24","unstructured":"A. Sinclair, Ph.D. Thesis,  Randomised Algorithms for Counting and Generating Combinatorial Structures, Department of Computer Science, University of Edinburgh, Edinburgh, Scotland, U.K.,  1988"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1137\/0214060"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"R28","unstructured":"P. Winkler,  1989, personal communication"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0222062","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:49:53Z","timestamp":1787338193000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0222062"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,10]]},"references-count":28,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1993,10]]}},"alternative-id":["10.1137\/0222062"],"URL":"https:\/\/doi.org\/10.1137\/0222062","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,10]]}}}