BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Computer Science and Engineering - ECPv6.13.0//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://homecse.iitd.ac.in
X-WR-CALDESC:Events for Computer Science and Engineering
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Kolkata
BEGIN:STANDARD
TZOFFSETFROM:+0530
TZOFFSETTO:+0530
TZNAME:IST
DTSTART:20250101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Kolkata:20250217T120000
DTEND;TZID=Asia/Kolkata:20250217T133000
DTSTAMP:20260924T070048
CREATED:20250212T122558Z
LAST-MODIFIED:20250219T003504Z
UID:1331-1739793600-1739799000@homecse.iitd.ac.in
SUMMARY:Polynomial Size\, Short-Circuit Resilient Circuits for NC
DESCRIPTION:Speaker: Raghuvansh Saxena (Tata Institute of Fundamental Research)\n \nWe show how to convert any circuit of poly-logarithmic depth and polynomial size into a functionally equivalent circuit of polynomial size (and polynomial depth) that is resilient to adversarial short-circuit errors. Specifically\, the resulting circuit computes the same function even if up to $epsilon d$ gates on every root-to-leaf path are short-circuited\, i.e.\, their output is replaced with the value of one of its inputs\, where $d$ is the depth of the circuit and $epsilon > 0$ is a fixed constant. \nPreviously\, such a result was known for formulas (Kalai-Lewko-Rao\, FOCS 2012). It was also known how to convert general circuits to error resilient ones whose size is quasi-polynomial in the size of the original circuit (Efremenko et al.~STOC 2022). The reason both these works do not extend to our setting is that there may be many paths from the root to a given gate\, and the resilient circuit needs to “remember” a lot of information about these paths\, which causes it to be large. Our main idea is to reduce the amount of this information at the cost of increasing the depth of the resilient circuit.
URL:https://homecse.iitd.ac.in/event/polynomial-size-short-circuit-resilient-circuits-for-nc/
LOCATION:Bharti 501\, IIT Campus\, Hauz Khas\, New Delhi
CATEGORIES:Seminars
END:VEVENT
END:VCALENDAR