Lower Bounds for the Complexity of Learning Half-Spaces with Membership Queries Authors: Valery N. Shevchenko, and Nikolai Yu. Zolotykh Source: Lecture Notes in Artificial Intelligence Vol. 1501, 1998, 61 - 71. Abstract. Exact learning of half-spaces over finite subsets of n from membership queries is considered. We describe the minimum set of labelled examples separating the target concept from all the other ones of the concept class under consideration. For a domain consisting of all integer points of some polytope we give non-trivial lower bounds on the complexity of exact identification of half-spaces. These bounds are near to known upper bounds. ©Copyright 1998 Springer