Ian Mertz

postdoctoral researcher

Centre for Discrete Mathematics
      and its Applications (DIMAP)

Department of Computer Science
University of Warwick

Room MS 1.15
Mathematical Science Building
Coventry, United Kingdom, CV4 7AL

first_name [dot] last_name [at] warwick.ac.uk

about

I'm a postdoctoral researcher in the Theory and Foundations Group at the University of Warwick, where I'm fortunate to be working with Igor Carboni Oliveira. Before this I was a graduate student at University of Toronto advised by Toniann Pitassi, and before that I was an undergraduate at Rutgers University.

At the moment my research interests mostly include catalytic computing, lifting theorems, arithmetic circuit complexity, and proof complexity.

[CV]   [DBLP]   [Google Scholar]   [ORCID]

Update: In September I'll be starting a new postdoctoral position at Charles University with Michal Koucký.

publications

SURVEYS

Reusing Space: Techniques and Open Problems
Ian Mertz
Bulletin of EATCS, 141 pp. 57-106, 2023.

TCS PAPERS

The Structure of Catalytic Space: Capturing Randomness and Time via Compression
James Cook, Jiatu Li, Ian Mertz, Edward Pyne
In submission.
Tree Evaluation is in Space O(log n · log log n)
Trading Time and Space in Catalytic Branching Programs
James Cook, Ian Mertz
Proc. 37th Computational Complexity Conference (CCC 2022), pp. 8:1-8:21, 2022.
[video (CCC)]   [slides]
Encodings and the Tree Evaluation Problem
James Cook, Ian Mertz
Upcoming journal version to be merged with Catalytic Approaches to the Tree Evaluation Problem, 2021.
Lifting with Sunflowers
Shachar Lovett, Raghu Meka, Ian Mertz, Toniann Pitassi, Jiapeng Zhang
Proc. 19th Innovations in Theoretical Computer Science (ITCS '22), pp. 104:1-104:24, 2022.
[video (ITCS)]   [video (MIAO)]   [slides]
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

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. See also: Catalytic Approaches to the Tree Evaluation Problem.
[slides]
Catalytic Computing Between L and P
Ian Mertz
Qualifying exam. See also: Catalytic Approaches to the Tree Evaluation Problem.
[slides]
Proof Complexity and Automatizability
Ian Mertz
Master's thesis. See also: Short Proofs are Hard to Find.
[slides]
Transforming Potential into Promise: A Depth-First Approach
Rajiv Gandhi, David Jacobowitz, Ian Mertz
In production.
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
    日本語