Abstract
We investigate active learning with access to two distinct oracles: L ABEL (which is standard) and S EARCH (which is not). The S EARCH oracle models the situation where a human searches a database to seed or counterexample an existing solution. S EARCH is stronger than L ABEL while being natural to implement in many situations. We show that an algorithm using both oracles can provide exponentially large problem-dependent improvements over L ABEL alone.