We introduce a new model of membership query (MQ) learning, where the learning algorithm is restricted to query points that are _close_ to random examples drawn from the underlying distribution. The learning model is intermediate between the PAC model (Valiant, 1984) and the PAC+MQ model (where the queries are allowed to be arbitrary points). Membership query algorithms are not popular among...