Learning Boolean Halfspaces with Small Weights from Membership Queries
  We consider the problem of proper learning a Boolean Halfspace with integer
weights $\{0,1,\ldots,t\}$ from membership queries only. The best known
algorithm for this problem is an adaptive algorithm that asks $n^{O(t^5)}$
membership queries where the best lower bound for the number of membership
queries is $n^t$ [Learning Threshold Functions with Small Weights Using
Membership Queries. COLT 1999]
  In this paper we close this gap and give an adaptive proper learning
algorithm with two rounds that asks $n^{O(t)}$ membership queries. We also give
a non-adaptive proper learning algorithm that asks $n^{O(t^3)}$ membership
queries.
