Skip to Content

Richard Strong Bowen

Picture of Richard Strong Bowen.

Thesis

Minimal Circuits for Very Incompletely Specified Boolean Functions

Advisor
Nicholas Pippenger
Second Reader(s)
Ran Libeskind-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

Additional Materials

Poster