Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > EXTERNAL MEMORY MODEL:
Reports tagged with external memory model:
TR26-223 | 2nd October 2026
Danil Sibgatullin, Ryan Williams

Space-Efficient Simulations Beyond Multitape Turing Machines

We explore new directions in simulating complex computations with low space, building on the work of Williams [STOC'25] and Cook-Mertz [STOC'24, SICOMP'25]. We define and study a strengthened version of the parallel external memory model, in which there are $P$ processors each with private internal memory $M$, all of which ... more >>>




ISSN 1433-8092 | Imprint