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, composition theorems, space-bounded computation, lifting, and proof complexity.

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

Update: In October 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

Fully Characterizing Lossy Catalytic Space
Marten Folkertsma, Ian Mertz, Florian Speelman, Quinten Tupker
In submission.
The Structure of Catalytic Space: Capturing Randomness and Time via Compression
James Cook, Jiatu Li, Ian Mertz, Edward Pyne
In submission.
[slides]
Tree Evaluation is in Space O(log n · log log n)
James Cook, Ian Mertz
Proc. 56th ACM Symposium on Theory of Computing (STOC '24), pp. 1268-1278, 2024.
[video (STOC)]   [video (IAS)]   [video (Lisbon)]   [slides]   [coverage]
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
James Cook, Ian Mertz
Proc. 52nd ACM Symposium on Theory of Computing (STOC '20), pp. 752-760, 2020.
[video (STOC)]   [video (IAS)]
Automating Cutting Planes is NP-Hard
Mika Göös, Sajin Koroth, Ian Mertz, Toniann Pitassi
Proc. 52nd ACM Symposium on Theory of Computing (STOC '20), pp. 68-77, 2020.
[video (STOC)]   [slides]
Short Proofs Are Hard to Find
Ian Mertz, Toniann Pitassi, Yuanhao Wei
Proc. 46th International Colloquium on Automata, Languages and Programming (ICALP '19), Leibniz International Proceedings in Informatics (LIPIcs), 84 (132) pp. 1-16, 2019.
[video (IAS)]   [slides]
Dual VP Classes
Eric Allender, Anna Gál, Ian Mertz
computational complexity, 25 pp. 1-43, 2016. An earlier version appeared in Proc. 40th International Symposium on Mathematical Foundations of Computer Science (MFCS '15), Lecture Notes in Computer Science, 9235 pp. 14-25, 2015.
[slides]
Complexity of Regular Functions
Eric Allender, Ian Mertz
Journal of Computer and System Sciences, 104 pp. 5-16, 2019. An earlier version appeared in Proc. 9th International Conference on Language and Automata Theory and Applications (LATA '15), Lecture Notes in Computer Science, 8977 pp. 449-460, 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. 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
2024 - postdoc Charles University Michal Koucký
2022 - 2024 postdoc University of Warwick Igor Carboni Oliveira
2018 - 2022 phd University of Toronto Toniann Pitassi
2016 - 2018 masters University of Toronto Toniann Pitassi,
Stephen Cook
2012 - 2016 undergraduate Rutgers University Eric Allender

summer 2024 Centrum Wiskunde & Informatica Florian Speelman,
Quinten Tupker
fall 2023 University of Lisbon Bruno Loff
spring 2023 Simons Institute
summer 2022 Charles University Michal Koucký
spring 2022 Institute for Advanced Study Toniann Pitassi
spring 2020 Institute for Advanced Study Toniann Pitassi
fall 2019 Heidelberg Laureate Forum
fall 2018 Simons Institute
fall 2017 Institute for Advanced Study Toniann Pitassi
fall 2016 Heidelberg Laureate Forum
summer 2015 Kyoto University Kazuo Iwama
summer 2012 PACT program (instructor) Rajiv Gandhi
summer 2011 PACT program Rajiv Gandhi
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
    日本語