Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > IAN MERTZ:
All reports by Author Ian Mertz:

TR25-055 | 24th April 2025
Yaroslav Alekseev, Yuval Filmus, Ian Mertz, Alexander Smal, Antoine Vinciguerra

Catalytic Computing and Register Programs Beyond Log-Depth

In a seminal work, Buhrman et al. (STOC 2014) defined the class $CSPACE(s,c)$ of problems solvable in space $s$ with an additional catalytic tape of size $c$, which is a tape whose initial content must be restored at the end of the computation. They showed that uniform $TC^1$ circuits are ... more >>>


TR25-019 | 27th February 2025
Michal Koucky, Ian Mertz, Edward Pyne, Sasha Sami

Collapsing Catalytic Classes

A catalytic machine is a space-bounded Turing machine with additional access to a second, much larger work tape, with the caveat that this tape is full, and its contents must be preserved by the computation. Catalytic machines were defined by Buhrman et al. (STOC 2014), who, alongside many follow-up works, ... more >>>




ISSN 1433-8092 | Imprint