BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Shuichi Hirahara (NII (Japan))
DTSTART:20220323T220000Z
DTEND:20220323T230000Z
DTSTAMP:20260423T021014Z
UID:TCSPlus/37
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/TCSPlus/37/"
 >Excluding PH Pessiland</a>\nby Shuichi Hirahara (NII (Japan)) as part of 
 TCS+\n\n\nAbstract\nPessiland is the worst of Impagliazzo's five possible 
 worlds: it is a world where NP is hard on average and pseudorandom generat
 ors do not exist. Excluding Pessiland (i.e.\, showing the equivalence betw
 een average-case hardness of NP and the existence of pseudorandom generato
 rs) is one of the most important open questions in theoretical computer sc
 ience.\n\nIn this talk\, we propose to consider PH (Polynomial Hierarchy) 
 variants of Impagliazzo's five possible worlds.  Our main result is to unc
 onditionally rule out PH variants of Pessiland. I will also mention recent
  progress on excluding PH Heuristica: average-case hardness of PH follows 
 from exponential worst-case hardness of PH.\n\nBased on joint works with R
 ahul Santhanam.\n
LOCATION:https://researchseminars.org/talk/TCSPlus/37/
END:VEVENT
END:VCALENDAR