Date of Award
5-30-2010
Document Type
Open Access Senior Thesis
Degree Name
Bachelor of Science
Department
Mathematics
First Thesis Advisor
Nicholas Pippenger
Second Thesis Advisor
Ran Libeskind-Hadas
Rights Information
© 2010 Richard Strong Bowen
Terms of Use & License Information
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.
Recommended Citation
Bowen, Richard Strong, "Minimal Circuits for Very Incompletely Specified Boolean Functions" (2010). HMC Senior Theses. Paper 18.
http://scholarship.claremont.edu/hmc_theses/18
COinS
Comments
Previously linked to as: http://ccdl.libraries.claremont.edu/u?/stc,332