イアン・マーツ

自己紹介

カレル大学計算理論学部所属。現在ポスドクで、ありがたいことに Michal Koucký教授よりご指導頂いています。かつてウォーリック大学でポスドク（Igor Carboni Oliveira教授指導）、トロント大学で博士号（Toniann Pitassi教授指導）、そしてその前ラトガーズ大学コンピュータサイエンス学部卒業。

着目している研究テーマは計算複雑性理論、近年特にcatalytic計算、composition定理、空間計算について研究し、ついでにlifting、証明複雑性についても研究を続けています。

[CV] [DBLP] [Google Scholar] [ORCID] [報道]

研究発表

大系

Reusing Space: Techniques and Open Problems

Ian Mertz
EATCS会報、141 pp.57-106、2023年。

出版（理論計算機科学）

Bipartite Matching is in Catalytic Logspace

Aryan Agarwala, Ian Mertz
近刊、2025年。

Collapsing Catalytic Classes

Michal Koucký、Ian Mertz、Edward Pyne、Sasha Sami
近刊、2025年。

The Structure of Catalytic Space: Capturing Randomness and Time via Compression

James Cook、Jiatu Li、Ian Mertz、Edward Pyne
ACM Symposium on Theory of Computing (STOC) （近刊）、2025年。
[スライドショー]

Fully Characterizing Lossy Catalytic Space

Marten Folkertsma、Ian Mertz、Florian Speelman、Quinten Tupker
第16回 Innovations in Theoretical Computer Science (ITCS)、2025年。

Tree Evaluation is in Space O(log n · log log n)

James Cook、Ian Mertz
第56回 ACM Symposium on Theory of Computing (STOC)、2024年。
[ビデオ(STOC)] [ビデオ(IAS)] [ビデオ(リスボン大学)] [スライドショー] [報道]

Trading Time and Space in Catalytic Branching Programs

James Cook、Ian Mertz
第37回 Computational Complexity Conference (CCC)、2022年。
[ビデオ(CCC)] [スライドショー]

Encodings and the Tree Evaluation Problem

James Cook、Ian Mertz
Catalytic Approaches to the Tree Evaluation Problemとともに論文誌投稿予定、2021年。

Lifting with Sunflowers

Shachar Lovett、Raghu Meka、Ian Mertz、Toniann Pitassi、Jiapeng Zhang
第13回 Innovations in Theoretical Computer Science (ITCS)、2022年。
[ビデオ(ITCS)] [ビデオ(MIAO)] [スライドショー]

Catalytic Approaches to the Tree Evaluation Problem

James Cook、Ian Mertz
第52回 ACM Symposium on Theory of Computing (STOC)、2020年。
[ビデオ(STOC)] [ビデオ(IAS)]

Automating Cutting Planes is NP-Hard

Mika Göös、Sajin Koroth、Ian Mertz、Toniann Pitassi
第52回 ACM Symposium on Theory of Computing (STOC)、2020年。
[ビデオ(STOC)] [スライドショー]

Short Proofs Are Hard to Find

Ian Mertz、Toniann Pitassi、Yuanhao Wei
第46回 International Colloquium on Automata, Languages and Programming (ICALP)、2019年。
[ビデオ(IAS)] [スライドショー]

Dual VP Classes

Eric Allender、Anna Gál、Ian Mertz
computational complexity、2016年。
第40回 International Symposium on Mathematical Foundations of Computer Science (MFCS)、2015年。

Complexity of Regular Functions

Eric Allender、Ian Mertz
Journal of Computer and System Sciences、2019年。
第9回 International Conference on Language and Automata Theory and Applications (LATA)、2015年。
[スライドショー]

草稿・雑

The Complexity of Composition: New Approaches to Depth and Space

Ian Mertz
博士論文。
[ビデオ(ToniCS)] [スライドショー]

Catalytic Computing, Tree Evaluation, & Clean Computation

Ian Mertz
論文の提案・関連項目：Catalytic Approaches to the Tree Evaluation Problem。
[スライドショー]

Catalytic Computing Between L and P

Ian Mertz
一次試験・関連項目：Catalytic Approaches to the Tree Evaluation Problem。
[スライドショー]

Proof Complexity and Automatizability

Ian Mertz
修士論文・関連項目：Short Proofs are Hard to Find。
[スライドショー]

Transforming Potential into Promise: A Depth-First Approach

Rajiv Gandhi、David Jacobowitz、Ian Mertz
未刊

研究歴

2024年～	ポスドク	カレル大学	Michal Koucký先生
2022年～2024年	ポスドク	ウォーリック大学	Igor Carboni Oliveira先生
2018年～2022年	博士後期課程	トロント大学	Toniann Pitassi先生
2016年～2018年	博士前期課程	トロント大学	Toniann Pitassi先生、 Stephen Cook先生
2012年～2016年	学士課程	ラトガーズ大学	Eric Allender先生

2024年夏期	数学や情報学のセンター	Florian Speelman先生、 Quinten Tupkerさん
2023年秋期	リスボン大学	Bruno Loff先生
2023年春期	Simons Institute
2022年夏期	カレル大学	Michal Koucký先生
2022年春期	プリンストン高等研究所	Toniann Pitassi先生
2020年春期	プリンストン高等研究所	Toniann Pitassi先生
2018年秋期	Simons Institute
2017年秋期	プリンストン高等研究所	Toniann Pitassi先生
2015年夏期	京都大学	岩間一雄先生
2012年夏期	PACTプログラム（担当役）	Rajiv Gandhi先生
2011年夏期	PACTプログラム	Rajiv Gandhi先生

ティーチングアシスタント

2021年夏期	CSC 165	コンピュータ科学向けの論理的表現と推論
2020年秋期	CSC 236 CSC 2426	計算理論額の導入暗号学の基礎
2019年秋期	CSC 165	コンピュータ科学向けの論理的表現と推論
2019年冬期	CSC 165（二つ）	コンピュータ科学向けの論理的表現と推論
2018年冬期	CSC 165 CSC 463	コンピュータ科学向けの論理的表現と推論計算複雑性と計算可能性
2017年夏期	CSC 373	アルゴリズムデザイン・解析・複雑性
2017年冬期	CSC 463	計算複雑性と計算可能性
2016年秋期	CSC 165	コンピュータ科学向けの論理的表現と推論
2015年秋期	CS 509	コンピュータ科学の基礎