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