Line spectrum estimation from analog signal samples is a classic problem with numerous applications. However, sending analog or finely quantized signal sample streams to a fusion center is a burden in distributed sensing scenarios. Instead, it is appealing to estimate the frequency lines from a few randomly filtered broadband power measurement bits taken using a network of cheap sensors. This leads to a new problem: line spectrum estimation from inequalities. Three different techniques are proposed for this estimation task. In the first two, the autocorrelation function is first estimated nonparametrically, then a parametric method is used to estimate the sought frequencies. The third is a direct maximum likelihood (ML) parameter estimation approach that uses coordinate descent. Simulations show that the underlying frequencies can be accurately estimated using the proposed techniques, even from relatively few bits; and that the ML estimates obtained with the third technique can meet the Cramer-Rao lower bound (also derived here), when the number of sensors is sufficiently large.