By now it is known that several problems in the robustness analysis and synthesis of control systems are NP-complete or NP-hard. These negative results force us to modify our notion of "solving" a given problem. An approach that is recently gaining popularity is that of using randomized algorithms, which can be used to solve a problem approximately, most of the time. We begin with the premise that many problems in robustness analysis and synthesis can be formulated as the minimization of an objective function with respect to the controller parameters. It is argued that, in order to assess the performance of a controller as the plant varies over a prespecified family, it is better to use the average performance of the controller as the objective function to be minimized, rather than its worst-case performance, as the worst-case objective function usually leads to rather conservative designs. Then it is shown that a property from statistical learning theory known as uniform convergence of empirical means (UCEM) plays an important role in allowing us to construct efficient randomized algorithms for a wide variety of controller synthesis problems. In particular, whenever the UCEM property holds, there exists an efficient (i.e., polynomial-time) randomized algorithm. Using very recent results in statistical learning theory, it is shown that the UCEM property holds in any problem in which the satisfaction of a performance constraint can be expressed in terms of a finite number of polynomial inequalities, In particular, several problems such as robust stabilization and weighted H-2/H-infinity-norm minimization are amenable to the randomized approach.