Relations between Space-Bounded and Adaptive Massively Parallel Computations

dc.contributor.advisor Aduri, Pavan
dc.contributor.advisor Chaudhuri, Soma
dc.contributor.advisor Quinn, Christopher
dc.contributor.author Chen, Michael Qi Yin
dc.contributor.department Computer Science en_US
dc.date.accessioned 2024-01-25T20:18:57Z
dc.date.available 2024-01-25T20:18:57Z
dc.date.issued 2023-12
dc.date.updated 2024-01-25T20:18:58Z
dc.description.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}}$.
dc.format.mimetype PDF
dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/7wbOKBYv
dc.language.iso en
dc.language.rfc3066 en
dc.subject.disciplines Computer science en_US
dc.subject.keywords AMPC en_US
dc.subject.keywords Complexity Classes en_US
dc.subject.keywords LogSpace en_US
dc.subject.keywords Massively Parallel Computation en_US
dc.subject.keywords NL en_US
dc.subject.keywords PSPACE en_US
dc.title Relations between Space-Bounded and Adaptive Massively Parallel Computations
dc.type article en_US
dc.type.genre thesis en_US
dspace.entity.type Publication
thesis.degree.discipline Computer science en_US
thesis.degree.grantor Iowa State University en_US
thesis.degree.level thesis $
thesis.degree.name Master of Science en_US
File
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
Chen_iastate_0097M_21265.pdf
Size:
541.64 KB
Format:
Adobe Portable Document Format
Description:
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
0 B
Format:
Item-specific license agreed upon to submission
Description: