BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:William Hoza (UT Austin) DTSTART:20210217T180000Z DTEND:20210217T190000Z DTSTAMP:20260423T021014Z UID:TCSPlus/20 DESCRIPTION:Title: Fooling Constant-Depth Threshold Circuits\nby William Hoza (UT Austin ) as part of TCS+\n\n\nAbstract\nWe present the first non-trivial pseudora ndom generator (PRG) for linear threshold (LTF) circuits of arbitrary cons tant depth and super-linear size. This PRG fools circuits with depth $d$ a nd $n^{1 + \\delta}$ wires\, where $\\delta = \\exp(-O(d))$\, using seed l ength $O(n^{1 - \\delta})$ and with error $\\exp(-n^{\\delta})$. This tigh tly matches the best known lower bounds for this circuit class. As a conse quence of our result\, all the known hardness for LTF circuits has now eff ectively been translated into pseudorandomness. This brings the extensive effort in the last decade to construct PRGs and deterministic circuit-anal ysis algorithms for this class to the point where any subsequent improveme nt would yield breakthrough lower bounds.\n\nA key ingredient in our const ruction is a pseudorandom restriction procedure that has tiny failure prob ability\, but simplifies the function to a non-natural "hybrid computation al model" that combines decision trees and LTFs. As part of our proof we a lso construct an "extremely low-error" PRG for the class of functions comp utable by an arbitrary function of s linear threshold functions that can h andle even the extreme setting of parameters $s = n/\\mathrm{polylog}(n)$ and $\\epsilon = \\exp(-n/\\mathrm{polylog}(n))$.\n\nJoint work with Pooya Hatami\, Avishay Tal\, and Roei Tell.\n LOCATION:https://researchseminars.org/talk/TCSPlus/20/ END:VEVENT END:VCALENDAR