We prove that NP\necoNP and coNP\nsubseteqMA 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.

more >>>

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 >>>

{\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 >>>

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 >>>