Modern pipelined microprocessors consult branch predictors to speculatively fetch and execute instructions beyond conditional branches. We present two new branch prediction methods that address different aspects of the branch prediction problem. The key idea is to replace the commonly used two-bit counter with another mechanism. The first method uses the perceptron, one of the simplest possible neural networks. Perceptrons provide better predictive capabilities than counters and allow our predictor to consider longer branch histories. The hardware resources needed for our method scale linearly with the history length, in contrast with other purely dynamic schemes that require exponential memory. Using a hierarchical organization, this complex multi-cycle predictor can be used as a component of a fast delay sensitive predictor. The second method uses a succint encoding of Boolean functions known as read-once monotone Boolean formulas. By replacing a large branch predictor component with a tiny circuit, we maintain accuracy while decreasing branch predictor access delay and power consumption.