Learning Disjunctions of Predicates
  Let $F$ be a set of boolean functions. We present an algorithm for learning
$F_\vee := \{\vee_{f\in S} f \mid S \subseteq F\}$ from membership queries. Our
algorithm asks at most $|F| \cdot OPT(F_\vee)$ membership queries where
$OPT(F_\vee)$ is the minimum worst case number of membership queries for
learning $F_\vee$. When $F$ is a set of halfspaces over a constant dimension
space or a set of variable inequalities, our algorithm runs in polynomial time.
  The problem we address has practical importance in the field of program
synthesis, where the goal is to synthesize a program that meets some
requirements. Program synthesis has become popular especially in settings
aiming to help end users. In such settings, the requirements are not provided
upfront and the synthesizer can only learn them by posing membership queries to
the end user. Our work enables such synthesizers to learn the exact
requirements while bounding the number of membership queries.
