Ian Mertz

According to our database, Ian Mertz authored at least 20 papers between 2015 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2025

The Structure of In-Place Space-Bounded Computation.

James Cook, Surendra Ghentiyala, Ian Mertz, Edward Pyne, Nathan S. Sheffield

CoRR, October, 2025

Computational Complexity of Discrete Problems (Dagstuhl Seminar 25111).

Swastik Kopparty, Meena Mahajan, Rahul Santhanam, Till Tantau, Ian Mertz

Dagstuhl Reports, March, 2025

Bipartite Matching is in Catalytic Logspace.

Aryan Agarwala, Ian Mertz

Electron. Colloquium Comput. Complex., 2025

Collapsing Catalytic Classes.

Michal Koucký, Ian Mertz, Edward Pyne, Sasha Sami

Electron. Colloquium Comput. Complex., 2025

Quantum Catalytic Space.

Harry Buhrman, Marten Folkertsma, Ian Mertz, Florian Speelman, Sergii Strelchuk, Sathyawageeswar Subramanian, Quinten Tupker

Proceedings of the 20th Conference on the Theory of Quantum Computation, 2025

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

James Cook, Jiatu Li, Ian Mertz, Edward Pyne

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Catalytic Computing and Register Programs Beyond Log-Depth.

Yaroslav Alekseev, Yuval Filmus, Ian Mertz, Alexander Smal, Antoine Vinciguerra

Proceedings of the 50th International Symposium on Mathematical Foundations of Computer Science, 2025

Fully Characterizing Lossy Catalytic Computation.

Marten Folkertsma, Ian Mertz, Florian Speelman, Quinten Tupker

Proceedings of the 16th Innovations in Theoretical Computer Science Conference, 2025

2024

Tree Evaluation Is in Space O(log n · log log n).

James Cook, Ian Mertz

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

2023

Reusing Space: Techniques and Open Problems.

Ian Mertz

Electron. Colloquium Comput. Complex., 2023

2022

The Complexity of Composition: New Approaches to Depth and Space

Ian Mertz

PhD thesis, 2022

Lifting with Sunflowers.

Shachar Lovett, Raghu Meka, Ian Mertz, Toniann Pitassi, Jiapeng Zhang

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Trading Time and Space in Catalytic Branching Programs.

James Cook, Ian Mertz

Proceedings of the 37th Computational Complexity Conference, 2022

2021

Encodings and the Tree Evaluation Problem.

James Cook, Ian Mertz

Electron. Colloquium Comput. Complex., 2021

2020

Lifting: As Easy As 1, 2, 3.

Ian Mertz, Toniann Pitassi

Electron. Colloquium Comput. Complex., 2020

Automating cutting planes is NP-hard.

Mika Göös, Sajin Koroth, Ian Mertz, Toniann Pitassi

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Catalytic approaches to the tree evaluation problem.

James Cook, Ian Mertz

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

2019

Short Proofs Are Hard to Find.

Ian Mertz, Toniann Pitassi, Yuanhao Wei

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2015

Dual VP Classes.

Eric Allender, Anna Gál, Ian Mertz

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Complexity of Regular Functions.

Eric Allender, Ian Mertz

Proceedings of the Language and Automata Theory and Applications, 2015