Ian Mertz

postdoctoral researcher

Computer Science Institute (IUUK)
Faculty of Mathematics and Physics
Charles University

Room 342
Malostranské nám. 25
118 00 Praha 1, Czech Republic

iwmertz [at] iuuk.mff.cuni.cz

about

I'm a postdoctoral researcher in the Center for Foundations of Contemporary Computer Science (CZSI) group at Charles University, where I'm fortunate to be working with Michal Koucký. Before this I was a postdoc at University of Warwick under Igor Carboni Oliveira, before that I was a graduate student at University of Toronto advised by Toniann Pitassi, and even further back I was an undergraduate at Rutgers University.

My research focus is on computational complexity, and more specifically my current interests mostly include catalytic computing, composition theorems, and space-bounded computation, along with some work on lifting and proof complexity.

[CV]   [DBLP]   [Google Scholar]   [ORCID]   [coverage (Quanta)]

publications

SURVEYS

Reusing Space: Techniques and Open Problems
Ian Mertz
Bulletin of EATCS (2023)

TCS PAPERS

Bipartite Matching is in Catalytic Logspace
Aryan Agarwala, Ian Mertz
ECCC (2025)
Collapsing Catalytic Classes
Michal Koucký, Ian Mertz, Edward Pyne, Sasha Sami
ECCC (2025)
The Structure of Catalytic Space: Capturing Randomness and Time via Compression
Fully Characterizing Lossy Catalytic Space
Tree Evaluation is in Space O(log n · log log n)
Trading Time and Space in Catalytic Branching Programs
Lifting with Sunflowers
Encodings and the Tree Evaluation Problem
James Cook, Ian Mertz
ECCC (2021)
Catalytic Approaches to the Tree Evaluation Problem
Automating Cutting Planes is NP-Hard
Short Proofs Are Hard to Find
Dual VP Classes
Complexity of Regular Functions
Eric Allender, Ian Mertz
JCSS (2019), LATA 2015
[slides]

TECHNICAL NOTES / MISCELLANEOUS

The Complexity of Composition: New Approaches to Depth and Space
Ian Mertz
Ph.D thesis
[video (ToniCS)]   [slides]
Catalytic Computing, Tree Evaluation, & Clean Computation
Ian Mertz
Thesis proposal
[slides]
Catalytic Computing Between L and P
Ian Mertz
Qualifying exam
[slides]
Proof Complexity and Automatizability
Ian Mertz
Master's thesis
[slides]
Transforming Potential into Promise: A Depth-First Approach
Rajiv Gandhi, David Jacobowitz, Ian Mertz
On hold.
research
teaching assistant
summer 2021 CSC 165 mathematical expression and reasoning for c.s.
fall 2020 CSC 236
CSC 2426
introduction to the theory of computation
fundamentals of cryptography
fall 2019 CSC 165 mathematical expression and reasoning for c.s.
winter 2019 CSC 165 (x2) mathematical expression and reasoning for c.s.
winter 2018 CSC 165
CSC 463
mathematical expression and reasoning for c.s.
computational complexity and computability
summer 2017 CSC 373 algorithm design, analysis, and complexity
winter 2017 CSC 463 computational complexity and computability
fall 2016 CSC 165 mathematical expression and reasoning for c.s.
fall 2015 CS 509 foundations of computer science
    日本語