All reports by Author Ian Mertz:

__
TR24-138
| 8th September 2024
__

Marten Folkertsma, Ian Mertz, Florian Speelman, Quinten Tupker#### Fully Characterizing Lossy Catalytic Computation

__
TR24-106
| 17th June 2024
__

James Cook, Jiatu Li, Ian Mertz, Edward Pyne#### The Structure of Catalytic Space: Capturing Randomness and Time via Compression

__
TR23-179
| 18th November 2023
__

Ian Mertz#### Reusing Space: Techniques and Open Problems

__
TR23-174
| 15th November 2023
__

James Cook, Ian Mertz#### Tree Evaluation is in Space O(log n · log log n)

__
TR15-018
| 31st January 2015
__

Eric Allender, Ian Mertz#### Complexity of Regular Functions

Revisions: 1

__
TR14-122
| 30th September 2014
__

Eric Allender, Anna Gal, Ian Mertz#### Dual VP Classes

Revisions: 2

Marten Folkertsma, Ian Mertz, Florian Speelman, Quinten Tupker

A catalytic machine is a model of computation where a traditional space-bounded machine is augmented with an additional, significantly larger, "catalytic" tape, which, while being available as a work tape, has the caveat of being initialized with an arbitrary string, which must be preserved at the end of the computation. ... more >>>

James Cook, Jiatu Li, Ian Mertz, Edward Pyne

In the catalytic logspace ($CL$) model of (Buhrman et.~al.~STOC 2013), we are given a small work tape, and a larger catalytic tape that has an arbitrary initial configuration. We may edit this tape, but it must be exactly restored to its initial configuration at the completion of the computation. This ... more >>>

Ian Mertz

In the world of space-bounded complexity, there is a strain of results showing that space can, somewhat paradoxically, be used for multiple purposes at once. Touchstone results include Barrington’s Theorem and the recent line of work on catalytic computing. We refer to such techniques, in contrast to the usual notion ... more >>>

James Cook, Ian Mertz

The Tree Evaluation Problem ($TreeEval$) (Cook et al. 2009) is a central candidate for separating polynomial time ($P$) from logarithmic space ($L$) via composition. While space lower bounds of $\Omega(\log^2 n)$ are known for multiple restricted models, it was recently shown by Cook and Mertz (2020) that TreeEval can be ... more >>>

Eric Allender, Ian Mertz

We give complexity bounds for various classes of functions computed by cost register automata.

more >>>Eric Allender, Anna Gal, Ian Mertz

We consider arithmetic complexity classes that are in some sense dual to the classes VP(Fp) that were introduced by Valiant. This provides new characterizations of the complexity classes ACC^1 and TC^1, and also provides a compelling example of

a class of high-degree polynomials that can be simulated via arithmetic circuits ...
more >>>