Talks
Fall 2016

A Finite Alternation Result for Reversible Boolean Circuits
Tuesday, November 8th, 2016, 2:30 pm–3:00 pm
Speaker:
Location:
Calvin Lab Auditorium
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.