About me
Hi! I am Nathan Wallheimer, a third-year PhD student in Theoretical Computer Science at the Weizmann Institute of Science, advised by Prof. Amir Abboud. My main research area is complexity theory, specifically fine-grained complexity and algorithms. Recently, I have also been working on lower bounds for distributed algorithms (work in progress). I am also interested in extremal and additive combinatorics.
Previously, I completed my Master's at the University of Haifa under the supervision of Prof. Oren Weimann, where we worked on data structures for planar graphs. You can contact me via nathan.wallheimer@weizmann.ac.il.
Publications
Witness-Sensitive Detection of Diamonds (ICALP 2026)
Joint work with Tomer Even, Keren Censor-Hillel, and Virginia Vassilevska Williams.
[arXiv]
Equivalent Dichotomies for Triangle Detection in Subgraph, Induced, and Colored H-Free Graphs (ESA 2026)
Joint work with Amir Abboud and Ron Safier.
[arXiv]
Triangle Detection in H-Free Graphs (ITCS 2026)
Joint work with Amir Abboud and Ron Safier.
[arXiv], [Slides], [Poster], [Video]
Recognizing Sumsets is NP-Complete (SODA 2025)
Joint work with Amir Abboud, Nick Fischer, and Ron Safier.
[arXiv], [Slides]
Worst-Case to Expander-Case Reductions: Derandomized and Generalized (ESA 2024)
Joint work with Amir Abboud.
[arXiv], [Slides], [Poster]
Worst-Case to Expander-Case Reductions (ITCS 2023)
Joint work with Amir Abboud.
[arXiv], [Slides], [Poster], [Video]
Improved Compression of the Okamura-Seymour Metric (ISAAC 2022)
Joint work with Shay Mozes and Oren Weimann.
[DROPS], [Slides]
Teaching
| July 2024 |
DIMACS Tutorial on Fine-Grained Complexity Teaching Assistant |
| 2018 - 2021 |
Advanced Data Structures, University of Haifa Teaching Assistant |
| 2018 - 2021 |
Data Structures, University of Haifa Teaching Assistant |
| 2017 - 2021 |
Probability, University of Haifa Teaching Assistant |