Skip navigation
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp012f75rb46c
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorBraverman, Mark-
dc.contributor.authorYitayew, Michael-
dc.date.accessioned2016-07-01T14:04:45Z-
dc.date.available2016-07-01T14:04:45Z-
dc.date.created2016-04-29-
dc.date.issued2016-07-01-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/dsp012f75rb46c-
dc.description.abstractWe 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. 2en_US
dc.format.extent20 pages*
dc.language.isoen_USen_US
dc.titleShort-Circuit Error Resilience in Boolean Formulasen_US
dc.typePrinceton University Senior Theses-
pu.date.classyear2016en_US
pu.departmentComputer Scienceen_US
pu.pdf.coverpageSeniorThesisCoverPage-
Appears in Collections:Computer Science, 1987-2023

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.