Speaker:Michael Qi Yin Chen

Relations Between Space-Bounded and Adaptive Massively Parallel Computations

This thesis studies the class of languages solvable by Adaptive Massively Parallel Computations in constant rounds from a computational complexity theory perspective. A language $L$ is in the class $\AMPC^0$ if for every $\varepsilon \in(0,1)$, there is a deterministic AMPC algorithm running in constant rounds with a $\textup{poly}(n)$ processors, where the local memory of each machine $O(n^\varepsilon)$. This thesis proves $\L\subsetneq\AMPC^0$ and then further improves it by showing $\ReachUL\subsetneq \AMPC^0$. The complexity class $\ReachUL$ lies between the well-known space-bounded complexity classes $\L$ and $\NL$. We also show that $\AMPC^0\subseteq\cap_{\varepsilon\in(0,1)}\DSPACE(n^\varepsilon)$, which is stronger than $\AMPC^0\subseteq\SubEXP$. We establish that it is unlikely that $\PSPACE$ admits $\AMPC$ algorithms, even with polynomially many rounds. We also establish that showing $\PSPACE$ is a subclass of (nonuniform) $\AMPC$ with polynomially many rounds leads to a significant separation result in complexity theory, namely $\PSPACE$ is a proper subclass of $\EXP^{\Sigma_2^{\P}}$.

Committee: Pavan Aduri (major professor), Soma Chaudhuri, and Chris Quinn.