Richard Strong Bowen
Thesis
Minimal Circuits for Very Incompletely Specified Boolean Functions
- Advisor
- Nicholas Pippenger
- Second Reader(s)
- Ran Liebeskind-Hadas (CS)
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.
Proposal
Minimal Circuits for Very Incompletely Specified Boolean Functions
