Low-end uniform hardness vs. randomness tradeoffs for AM
Ronen Shaltiel, Christopher Umans · 2007
In 1998, Impagliazzo and Wigderson [18] proved a hardnessvs. randomness tradeoff for BPP in the uniform setting,which was subsequently extended to give optimal tradeoffs for thefull range of possible hardness assumptions by Trevisan and Vadhan [29] (in a slightly weaker setting). In 2003, Gutfreund,Shaltiel and Ta-Shma [11] proved a uniform hardness vs. randomness tradeoff for AM, but that result only worked on the "high-end" of possible hardness assumptions.