David Heath

Parallel RAM from Cyclic Circuits

2023 · arXiv (Cornell University)

Known simulations of random access machines (RAMs) or parallel RAMs (PRAMs) by Boolean circuits incur significant polynomial blowup, due to the need to repeatedly simulate accesses to a large main memory. Consider a single modification …