This paper1 proposes a novel methodology for improving the leakage yield of digital circuits in the presence of process variations and under probabilistic timing constraints. The leakage minimization problem is formulated as a discrete optimization problem, where a suitable configuration for each gate in the circuit is selected from a standard-cell library consisting of different implementations of each type of gate. A function of mean and variance of the circuit leakage is minimized with constraint on ?-percentile of the delay using physical delay models. Since the leakage is a strong function of the threshold voltage and gate length, considering them as design variables in addition to gate sizes can provide significant power savings. We propose efficient techniques for computing delay and leakage power gradients which form the basis of the optimization algorithm. Results on various trade-offs such as between leakage and delay, and mean and variance of the leakage are discussed.