Learning Halfspaces with the Zero-One Loss: Time-Accuracy Tradeoffs Aharon Birnbaum and Shai Shalev-Shwartz School of Computer Science and Engineering The Hebrew University Jerusalem, Israel