Relations between Space-Bounded and Adaptive Massively Parallel Computations

Thumbnail Image
Date
2023-12
Authors
Chen, Michael Qi Yin
Major Professor
Advisor
Aduri, Pavan
Chaudhuri, Soma
Quinn, Christopher
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Authors
Research Projects
Organizational Units
Journal Issue
Is Version Of
Versions
Series
Department
Computer Science
Abstract
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}}$.
Comments
Description
Keywords
Citation
DOI
Source
Subject Categories
Copyright