All reports by Author Ian Mertz:

__
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

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 >>>