Princeton University Library Catalog

Short-Circuit Error Resilience in Boolean Formulas

Author/​Artist:
Yitayew, Michael [Browse]
Format:
Senior thesis
Language:
English
Advisor(s):
Braverman, Mark [Browse]
Department:
Princeton University. Department of Computer Science [Browse]
Class year:
2016
Description:
20 pages
Summary note:
We investigate the problem of computing on boolean formulas in the presence of short circuit errors; these are errors that replace the output value of a gate by one of its input values. We show that any boolean formula F that computes a function f can be converted into a formula E that computes f even if up to ( 1 3 - ) of E's gates on each input to output path are short-circuited, for any > 0. The short-circuited gates and the exact errors may be chosen adversarily and may depend on input with no restriction. The size of E will be polynomial in the size of F, with dependence on . We also show that there is a function f such that no formula can compute f and tolerate 1 3 of its gates per input-to-output path being corrupted. This answers the question posed by Kalai et al[1] of nding the maximum constant fraction of short-circuit errors that can be tolerated per path in a formula, and improves their resilience factor of ( 1 10 - ). We obtain these results by showing a tight, error resilient version of the Karchmer-Wigderson connection between formulas and communication protocols, and applying this connection to recent results from interactive communication. 2