Circuit reliability is going to emerge as a critical challenge for designers with continued scaling of digital circuits. A key problem is the lack of efficient techniques that consider reliability in the design process. We address this problem and develop circuit transformations as well as a hybrid method that combines an exact method with a probabilistic approach to estimate reliability. We then use this measure in a rewiring based optimization framework to optimize reliability. Our hybrid approach offers a speedup of 48X when compared to a Monte Carlo simulation based approah with only a 3.5% loss in accuracy. Our optimization framework improves reliability by about 10% accompanied by a 6.9% reduction in circuit area.