Excluding PH Pessiland
summary
Proves unconditionally that PH Pessiland excluded by showing PH-average hardness is equivalent to existence of a PH-confutable pseudorandom generator (PH-PRG) and then refuting that equivalence, giving both uniform and nonuniform versions. Shows MinKT^PH is average-case complete for PH, gives a PH-PRG that extends seed by one bit (and derives polylog stretch in the uniform case or else a hard tally language), and reduces error-prone average-hardness to explicit pseudorandomness constructions.
AI-written summary · about