The Compilation of Reversible Circuits and a New Optimization Game

Abstract

The focus of this thesis is reversible circuit compilation. We will explore the use of pebble games for circuit analysis. The usefulness of this technique is demonstrated by finding a new space bound for the Karatsuba algorithm and more generally for any similar algorithm based on recurrence relations. A new pebble game based on the reversible pebble game which better captures the use of in-place operations is also presented. We also construct circuit to compute trigonometric functions based on the CORDIC algorithm and analyze it using this game.