------------------------------------------------------------------------------- B O S T O N U N I V E R S I T Y Computer Science Department S E M I N A R Wednesday October 5, 1994 3:00pm (Coffee served at 2:30pm) Seminar Room / MCS 135 ------------------------------------------------------------------------------- The Bounded Injury Priority Method and The Learnability of Unions of Rectangles Zhixiang Chen Boston University Abstract It is well known that learning unions of rectangles is closely related to other central open problems in computa- tional learning theory: (1)It is a generalization of learn- ing DNF formulas. (2)It is a special case of unions of in- tersections of halfspaces. And (3)unions of pairwise dis- joint rectangles are decision trees over bounded integer domains. We will begin with a brief survey of recent research on learning unions of rectangles. The problem of learning an arbitrary union of rectangles of a fixed dimension using only equivalence queries will be discussed. A learning al- gorithm will be presented which uses a new type of bounded injury priority argument from recursion theory. Applying this method, we give a positive solution to the above open problem and, as well, design efficient algorithms for learn- ing other subclasses of unions of rectangles. This talk is a thesis proposal; it is joint work with Steve Homer and will appear in FOCS'94.