Unconditional derandomization of Arthur-Merlin games

Recomm. for undergrads: no
Posted by: ormeir
on: July 16th, 2007

\begin{problem} Prove \emph{unconditionally} that \Def[$\mathcal{AM}$]{Arthur-Merlin_protocol} $\subseteq$ \Def[$\Sigma_2$]{Polynomial_hierarchy}. \end{problem}

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{http://www.research.att.com/~njas/sequences/}

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 \emph{unconditionally} that $\mathcal{AM} \subseteq \Sigma_2$.

Bibliography

% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)

*[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 \href[web site]{http://cs.haifa.ac.il/~ronen/online_papers/online_papers.html}.

[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 \href[web site]{http://www.cse.unl.edu/~vinod/papers/index.html}.

[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 \href[web site]{http://cs.haifa.ac.il/~ronen/online_papers/online_papers.html}.

[SU07] Ronen Shaltiel and Christopher Umans, Low-end uniform hardness vs. randomness tradeoffs for AM, STOC 2007. Can be downloaded from Ronen Shaltiel's \href[web site]{http://cs.haifa.ac.il/~ronen/online_papers/online_papers.html}.


* indicates original appearance(s) of problem.