Home » Subject » Theoretical Comp. Sci. » Complexity » Derandomization

Unconditional derandomization of Arthur-Merlin games

Importance: High ✭✭✭
Author(s): Shaltiel, Ronen
Umans, Christopher
Subject: Theoretical Computer Science
» Complexity
» » Derandomization
Keywords: Arthur-Merlin
Hitting Sets
unconditional
Recomm. for undergrads: no
Posted by: ormeir
on: July 16th, 2007
Problem   Prove unconditionally that $ \mathcal{AM} $ $ \subseteq $ $ \Sigma_2 $.

It is trivial to show that $ \mathcal{AM} \subseteq \Pi_2 $. It is also known that under hardness assumptions $ \mathcal{AM}= \mathcal{NP} $ (See [MV99]). The question is, can we prove unconditionally that $ \mathcal{AM} \subseteq \Sigma_2 $.

Bibliography

*[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.
add new comment