Skip navigation
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp012f75rb46c
Title: Short-Circuit Error Resilience in Boolean Formulas
Authors: Yitayew, Michael
Advisors: Braverman, Mark
Department: Computer Science
Class Year: 2016
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[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
Extent: 20 pages
URI: http://arks.princeton.edu/ark:/88435/dsp012f75rb46c
Type of Material: Princeton University Senior Theses
Language: en_US
Appears in Collections:Computer Science, 1988-2016

Files in This Item:
File SizeFormat 
Yitayew_Michael_2016_Thesis.pdf243.5 kBAdobe PDF    Request a copy


Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.