Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > CATALYTIC COMPUTATION:
Reports tagged with Catalytic Computation:
TR19-095 | 18th July 2019
Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari

#### Unambiguous Catalytic Computation

The catalytic Turing machine is a model of computation defined by Buhrman, Cleve,
Kouck, Loff, and Speelman (STOC 2014). Compared to the classical space-bounded Turing
machine, this model has an extra space which is filled with arbitrary content in addition
to the clean space. In such a model we study ... more >>>

TR20-024 | 20th February 2020
Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari

#### Randomized and Symmetric Catalytic Computation

A catalytic Turing machine is a model of computation that is created by equipping a Turing machine with an additional auxiliary tape which is initially filled with arbitrary content; the machine can read or write on auxiliary tape during the computation but when it halts auxiliary tape’s initial content must ... more >>>

TR20-056 | 17th April 2020
James Cook, Ian Mertz

The study of branching programs for the Tree Evaluation Problem, introduced by S. Cook et al. (TOCT 2012), remains one of the most promising approaches to separating L from P. Given a label in $[k]$ at each leaf of a complete binary tree and an explicit function in $[k]^2 \to ... more >>> TR21-035 | 13th March 2021 Robert Robere, Jeroen Zuiddam #### Amortized Circuit Complexity, Formal Complexity Measures, and Catalytic Algorithms Revisions: 1 We study the amortized circuit complexity of boolean functions. Given a circuit model$\mathcal{F}$and a boolean function$f : \{0,1\}^n \rightarrow \{0,1\}$, the$\mathcal{F}$-amortized circuit complexity is defined to be the size of the smallest circuit that outputs$m$copies of$f$(evaluated on the same input), ... more >>> TR21-054 | 14th April 2021 James Cook, Ian Mertz #### Encodings and the Tree Evaluation Problem We show that the Tree Evaluation Problem with alphabet size$k$and height$h$can be solved by branching programs of size$k^{O(h/\log h)} + 2^{O(h)}$. This answers a longstanding challenge of Cook et al. (2009) and gives the first general upper bound since the problem's inception. more >>> TR22-026 | 17th February 2022 James Cook, Ian Mertz #### Trading Time and Space in Catalytic Branching Programs An$m$-catalytic branching program (Girard, Koucky, McKenzie 2015) is a set of$m$distinct branching programs for$f\$ which are permitted to share internal (i.e. non-source non-sink) nodes. While originally introduced as a non-uniform analogue to catalytic space, this also gives a natural notion of amortized non-uniform space complexity for ... more >>>

ISSN 1433-8092 | Imprint