Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > CIRCUIT CLASSES:
Reports tagged with circuit classes:
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 >>>




ISSN 1433-8092 | Imprint