BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/291
DTSTAMP:20230914T125918Z
SUMMARY:Recovering from Adversarial Error in Boolean Circuits
DESCRIPTION:Speaker: Anup Rao (Department of Computer Science and Engineeri
ng\nUniversity of Washington\nSeattle\, WA 98195-2350\nUnited States of Am
erica\n )\n\nAbstract: \nWe consider two different models for adversarial
errors and show how to design circuits that can recover from such errors.
\nIn the first work\, we show how to efficiently convert any boolean for
mula $F$ into a boolean formula $E$ that is resilient to short-circuit err
ors (as introduced by Kleitman et al.). A gate has a short-circuit error w
hen the value it computes is replaced by the value of one of its inputs.\n
We guarantee that $E$ computes the same function as $F$\, as long as at mo
st $(1/10 - \\epsilon)$ of the gates on each path from the output to an in
put have been corrupted in $E$. The corruptions may be chosen adversariall
y\, and may depend on the formula $E$ and even on the input. We obtain our
result by extending the Karchmer-Wigderson connection between formulas an
d communication protocols to the setting of adversarial error. This enable
s us to obtain error-resilient formulas from error-resilient communication
protocols.\nIn the second work\, we assume that the input has been encode
d using a suitable error correcting code $C$. We show that given any boole
an circuit $F$\, one can design a layered circuit $E$ such that $E$ applie
d to the encoded input produces an output that is close to the error corre
cted version of the output of $F$\, as long as at most a constant fraction
of the gates in each layer of the circuit are corrupted (the corruptions
may be arbitrary).\nThe first result is joint work with Yael Kalai and All
ison Lewko. The second is joint work with Aram Harrow and Matthew Hastings
.\n
URL:https://www.tcs.tifr.res.in/web/events/291
DTSTART;TZID=Asia/Kolkata:20120718T160000
DTEND;TZID=Asia/Kolkata:20120718T170000
LOCATION:AG-69
END:VEVENT
END:VCALENDAR