Unconditional derandomization of Arthur-Merlin games
It is trivial to show that . It is also known that under hardness assumptions (See [MV99]). The question is, can we prove unconditionally that .
*[GSTS03] Danny Gutfreund, Ronen Shaltiel and Amnon Ta-Shma, Uniform hardness vs. randomness for Arthur-Merlin games, Proc. of CCC 2003. Can be downloaded from Ronen Shaltiel's web site.
[MV99] Peter Bro Miltersen and N. Variyam Vinodchandran, "Derandomizing Arthur-Merlin games using hitting sets", STOC 1999, pages 71-80. Can be downloaded from N. Variyam Vinodchandran's web site.
[SU01] Ronen Shaltiel and Christopher Umans, Simple extractor for all min-entropies and new pseudo-random generator, Proc. of FOCS 2001, pages 648-657. Can be downloaded from Ronen Shaltiel's web site.
[SU07] Ronen Shaltiel and Christopher Umans, Low-end uniform hardness vs. randomness tradeoffs for AM, STOC 2007. Can be downloaded from Ronen Shaltiel's web site.
* indicates original appearance(s) of problem.