License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2008.1342
URN: urn:nbn:de:0030-drops-13421
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1342/
Go to the corresponding LIPIcs Volume Portal

Chakaravarthy, Venkatesan T. ; Roy, Sambuddha

Finding Irrefutable Certificates for S_2^p via Arthur and Merlin

pdf-format:
22011.ChakaravarthyVenkatesan.Paper.1342.pdf (0.2 MB)

Abstract

We show that $S_2^psubseteq P^{prAM}$, where $S_2^p$ is the
symmetric alternation class and $prAM$ refers to the promise
version of the Arthur-Merlin class $AM$. This is derived as a
consequence of our main result that presents an $FP^{prAM}$
algorithm for finding a small set of ``collectively irrefutable
certificates'' of a given $S_2$-type matrix. The main result also
yields some new consequences of the hypothesis that $NP$ has
polynomial size circuits. It is known that the above hypothesis
implies a collapse of the polynomial time hierarchy ($PH$) to
$S_2^psubseteq ZPP^{NP}$ (Cai 2007, K"obler and Watanabe 1998).
Under the same hypothesis, we show that $PH$ collapses to
$P^{prMA}$. We also describe an $FP^{prMA}$ algorithm for learning
polynomial size circuits for $SAT$, assuming such circuits exist.
For the same problem, the previously best known result was a
$ZPP^{NP}$ algorithm (Bshouty et al. 1996).

BibTeX - Entry

@InProceedings{chakaravarthy_et_al:LIPIcs:2008:1342,
  author =	{Venkatesan T. Chakaravarthy and Sambuddha Roy},
  title =	{{Finding Irrefutable Certificates for S_2^p via Arthur and Merlin}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{157--168},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Susanne Albers and Pascal Weil},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1342},
  URN =		{urn:nbn:de:0030-drops-13421},
  doi =		{10.4230/LIPIcs.STACS.2008.1342},
  annote =	{Keywords: Symmetric alternation, promise-AM, Karp--Lipton theorem, learning circuits}
}

Keywords: Symmetric alternation, promise-AM, Karp--Lipton theorem, learning circuits
Collection: 25th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2008
Date of publication: 06.02.2008

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI