Dmytro Gavinsky, Alexander A. Sherstov

We prove that NP$\ne$coNP and coNP$\nsubseteq$MA in the number-on-forehead model of multiparty communication complexity for up to $k=(1-\epsilon)\log n$ players, where $\epsilon>0$ is any constant. Specifically, we construct a function $F:(\zoon)^k\to\zoo$ with co-nondeterministic

complexity $O(\log n)$ and Merlin-Arthur

complexity $n^{\Omega(1)}$.

The problem was open for $k\geq3$.

VyasRam Selvam

We explore the implications of the two queries assumption, $P^{NP[1]}=P_{||}^{NP[2]}$, with respect to the polynomial hierarchy and the classes $AM$ and $MA$.

We prove the following results:

1. $P^{NP[1]}=P_{||}^{NP[2]}$ $\implies$ $AM = MA$

2. $P^{NP[1]}=P_{||}^{NP[2]}$ $\implies$ $PH \subset MA_{/1}$

3. $\exists\;B\;P^{NP[1]^B}=P^{NP[2]^B}$ and $NP^B \not\subseteq coMA^B$.

4. $P^{NP[1]}=P_{||}^{NP[2]}$ $\implies$ $PH ...
more >>>

Oded Goldreich, Avi Wigderson

{\em Does derandomization of probabilistic algorithms become easier when the number of ``bad'' random inputs is extremely small?}

In relation to the above question, we put forward the following {\em quantified derandomization challenge}:

For a class of circuits $\cal C$ (e.g., P/poly or $AC^0,AC^0[2]$) and a bounding function $B:\N\to\N$ (e.g., ...
more >>>

Dorit Aharonov, Alex Bredariol Grilo

Despite the interest in the complexity class MA, the randomized analog of NP, there is just a couple of known natural (promise-)MA-complete problems, the first due to Bravyi and Terhal (SIAM Journal of Computing 2009) and the second due to Bravyi (Quantum Information and Computation 2015). Surprisingly, both problems are ... more >>>