Please use this identifier to cite or link to this item:
|Title:||Short-Circuit Error Resilience in Boolean Formulas|
|Abstract:||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 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|
|Type of Material:||Princeton University Senior Theses|
|Appears in Collections:||Computer Science, 1988-2016|
Files in This Item:
|Yitayew_Michael_2016_Thesis.pdf||243.5 kB||Adobe PDF||Request a copy|
Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.