In this paper we consider several problems related to the robust stability of polynomials whose coefficients depend on real parameters. We first show that if these parameters appear linearly in the coefficients, the computation of the largest stability hypercube with a fixed centre does not require a frequency ‘sweep’. Its size can be determined by considering a finite set of frequencies. We also demonstrate that for some polynomials where the coefficients themselves are polynomials in the parameters, the determination of stability can be made in a manner that involves a single frequency sweep and where at each frequency a finite number of simple tests are carried out. The methods are based on the Nyquist theorem and ‘value set’ ideas, and the approach provides analytical solutions.