BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Roei Tell (Institute for Advanced Study (IAS)) DTSTART:20220309T180000Z DTEND:20220309T190000Z DTSTAMP:20260423T021017Z UID:TCSPlus/36 DESCRIPTION:Title: Hardness vs Randomness\, Revised: Uniform\, Non-Black-Box\, and Instance- Wise\nby Roei Tell (Institute for Advanced Study (IAS)) as part of TCS +\n\n\nAbstract\nIn this talk I'll show how to revise the classical hardne ss-vs-randomness framework\, so that it can work in a non-black-box fashio n. Specifically\, we will construct derandomization algorithms that don't rely on classical PRGs\, and instead "extract pseudorandomness" from the g iven input on which we want to simulate the probabilistic machine.\n\nUsin g a non-black-box approach allows us to deduce stronger conclusions (or al ternatively rely on weaker hypotheses)\, compared to classical approaches. In one instantiation of the new framework\, we reveal a close connection between the promiseBPP = promiseP conjecture and a new type of uniform low er bounds. In another instantiation\, we simulate probabilistic algorithms with essentially no observable runtime overhead\, under plausible hypothe ses.\n\nBased on a joint work with Lijie Chen.\n LOCATION:https://researchseminars.org/talk/TCSPlus/36/ END:VEVENT END:VCALENDAR