Minimal Circuits for Very Incompletely Specified Boolean Functions

Author

Richard Strong Bowen, Harvey Mudd CollegeFollow

Graduation Year

2010

Document Type

Open Access Senior Thesis

Degree Name

Bachelor of Science

Department

Mathematics

Reader 1

Nicholas Pippenger

Reader 2

Ran Libeskind-Hadas

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

Rights Information

© 2010 Richard Strong Bowen

Abstract

In this report, asymptotic upper and lower bounds are given for the minimum number of gates required to compute a function which is only partially specified and for which we allow a certain amount of error. The upper and lower bounds match. Hence, the behavior of these minimum circuit sizes is completely (asymptotically) determined.

Comments

Previously linked to as: http://ccdl.libraries.claremont.edu/u?/stc,332

Recommended Citation

Bowen, Richard Strong, "Minimal Circuits for Very Incompletely Specified Boolean Functions" (2010). HMC Senior Theses. 18.
https://scholarship.claremont.edu/hmc_theses/18