Finding Needles in Exponential Haystacks