Fall 2016

A Finite Alternation Result for Reversible Boolean Circuits

Tuesday, November 8th, 2016 2:30 pm3:00 pm

Add to Calendar

We say that a reversible boolean function on n bits has alternation depth d if it can be written as the sequential composition of d reversible boolean functions, each of which acts only on the top n-1 bits or on the bottom n-1 bits. We show that every reversible boolean function of n >= 4 bits has alternation depth 9.