This paper deals with the class of polynomially uncertain continuous-time linear time-invariant (LTI) systems whose uncertainties belong to a semi-algebraic set. The objective is to determine the minimum of the smallest singular value of the controllability or observability Gramian over the uncertainty region. This provides a quantitative measure for the robust controllability or observability degree of the system. To this end, it is shown that the problem can be recast as a sum-of-squares (SOS) problem. In the special case when the uncertainty region is polytopic, the corresponding SOS formulation can be simplified significantly. One can apply the proposed method to any large-scale interconnected system in order to identify those inputs and outputs that are more effective in controlling the system, in a robust manner. This enables the designer to simplify the control structure by ignoring those inputs and outputs whose contribution to the overall control operation is relatively weak. A numerical example is presented to demonstrate the efficacy of the results. (C) 2009 Elsevier Ltd. All rights reserved.