Maximilian Thiessen

Hey there, my name is Max. I am a postdoc* hosted by Ulrike von Luxburg in the theory of ML group at Uni Tübingen. I did my PhD supervised by Thomas Gärtner at TU Wien and in between spent 3 months at the MPI for Informatics in Saarbrücken. Before my PhD, I studied CS in Bonn.

My main research area is learning theory and I am currently getting more into theoretical aspects of explainability. In the past, I have been working on learning with graphs, active learning, and convexity theory.

  1. News
  2. Publications
  3. Workshop Papers
  4. Community Activities
  5. People
  6. Contact

News

May '26Big news: started a postdoc in the Theory of ML group at Uni Tübingen hosted by Ulrike von Luxburg.
May '26Learning conditional averages got accepted at COLT! See you in San Diego.
Feb '26Visiting MPI Informatics the next 3 months hosted by Danupon Nanongkai!
Dec '25Submitted thesis!
Sep '25Together with Steve Hanneke and Shay Moran, we got our paper on nonuniform PAC learnability accepted to NeurIPS!
Aug '25Visited Sandra Zilles, Hans Simon, Rex Lei, and Shay Moran at the MPI Informatics.
July '25New preprint on Efficient Algorithms for Learning and Compressing Monophonic Halfspaces in Graphs with Marco Bressan, Victor Chepoi, and Emmanuel Esposito.
Jun '25Yet again visited the Laila group in Milan. Then visited CENTAI in Turin.

Older news
May '25Two papers accepted at COLT 2025!! And will also be presented at HALG 2025. Together with Marco Bressan, Nataly Brukhim, Nicolò Cesa-Bianchi, Emmanuel Esposito, Yishay Mansour, and Shay Moran.
Dez '24Together with Georgy Sokolov, Margarita Akhmejanova, Fabio Vitale, and Francesco Orabona, we got our paper Self-Directed Node Classification on Graphs accepted to ALT.
Nov '24Looking forward to the NeurIPS@Paris meetup and the Learning on Graphs (LoG) satellite in Aachen.
Nov '24Together with Franka Bause, Fabian Jogl, Patrick Indri, Tamara Drucks, David Penz, Nils Kriege, Thomas Gärtner, and Pascal Welke, we got our paper Maximally Expressive GNNs for Outerplanar Graphs accepted to TMLR.
Oct '24Together with pals from Uni Siena, Technion, LMU Munich, and RWTH Aachen, we started a new monthly graph learning reading group GLOW, with a focus on foundations and interactive discussions. Join our next session!
Sep '24Together with Stephen Pasteris, Alberto Rumi, Shota Saito, Atsushi Miyauchi, Fabio Vitale, and Mark Herbster we got our paper on (adverserial) contextual bandits with abstention accepted to NeurIPS!
Jun '24Happy to be invited to give a short talk on my research at the Austrian CS day (ACSD).
May '24Two papers accepted at COLT 2024!! Together with Marco Bressan, Nicolò Cesa-Bianchi, Emmanuel Esposito, Yishay Mansour, and Shay Moran. See you in Edmonton!
Mar '24Visited Marco Bressan and Nicolò Cesa-Bianchi at the University of Milan supported by an ELLIS / ELISE travel grant.
Mar '24We are organising the Mining and Learning with Graphs workshop (MLG) at ECMLPKDD in Vilnius. Submit your work!
Jan '24Happy to receive a DOC fellowship of the Austrian Academy of Sciences (ÖAW) to continue my PhD studies for two more years!
Nov '23Two papers accepted at the 2nd LoG conference with Franka Bause (Uni Vienna), Andrei Brasoveanu, Fabian Jogl, and Pascal Welke.
Nov '23Happy to be again recognised as a top reviewer of NeurIPS.
Oct '23Together with Franka Bause (Uni Vienna), Fabian Jogl, Patrick Indri, Tamara Drucks, David Penz, Nils Kriege (Uni Vienna), Thomas Gärtner, and Pascal Welke we got our paper Maximally Expressive GNNs for Outerplanar Graphs accepted as an oral at GLFrontiers@NeurIPS.
Sep '23Together with Fabian Jogl and Thomas Gärtner we got our paper Expressivity-Preserving GNN Simulation accepted to NeurIPS '23!
Jul '23I won a best poster award at G-Research's ICML poster party in London.
Mai '23Together with Pascal Welke, Fabian Jogl, and Thomas Gärtner we got our paper Expectation-Complete Graph Representations with Homomorphisms accepted to ICML '23!
Feb '23We are organising the 1st Community event for machine learning PhD students in Vienna (C’Est La Wien)!
Oct '22Workshop papers accepted at GLFrontiers@NeurIPS / LoG conference (with Pascal Welke and Thomas Gärtner) and NeurReps@NeurIPS (with Sohir Maskey, Ali Parviz, Hannes Stärk, Ylli Sadikaj, and Haggai Maron)!
Sep '22Together with Marco Bressan, Andrea Paudice, Nicolò Cesa-Bianchi (University of Milan), and Silvio Lattanzi (Google) we got our paper Active Learning of Classifiers with Label and Seed Queries accepted to NeurIPS '22!
Jul '22Happy to be recognised as an outstanding reviewer (top 10%) of ICML!
Jul '22My colleague Fabian Jogl got our paper Weisfeiler and Leman Return with Graph Transformations accepted to MLG@ECMLPKDD '22 and won the (community-voted) best poster award.
Jul '22Together with a team lead by my colleague Tamara Drucks, we organised machine learning courses for children at the KinderUni Wien.
Jun '22Our paper Online Learning of Convex Sets on Graphs got accepted to ECMLPKDD '22!
Jun '22I visited Marco Bressan and Nicolò Cesa-Bianchi at the University of Milan.

Current Preprints

  1. Efficient algorithms for learning and compressing monophonic halfspaces in graphs
    Marco Bressan, Victor Chepoi, Emmanuel Esposito, MTαβ

    [pdf] [arXiv]

(αβ alphabetical ordering)

Publications

  1. Learning Conditional Averages
    Marco Bressan, Nataly Brukhim, Nicolò Cesa-Bianchi, Emmanuel Esposito, Yishay Mansour, Shay Moran, MTαβ
    COLT (2026)

    [conference]

  2. Marginal-Nonuniform PAC Learnability
    Steve Hanneke, Shay Moran, MTαβ
    NeurIPS (2025)

    [conference]

  3. Of Dice and Games: a Theory of Generalized Boosting
    Marco Bressan, Nataly Brukhim, Nicolò Cesa-Bianchi, Emmanuel Esposito, Yishay Mansour, Shay Moran, MTαβ
    COLT (2025)

    [pdf] [conference]

  4. A Fine-Grained Characterization of PAC Learnability
    Marco Bressan, Nataly Brukhim, Nicolò Cesa-Bianchi, Emmanuel Esposito, Yishay Mansour, Shay Moran, MTαβ
    COLT (2025)

    [pdf] [conference]

  5. Self-Directed Node Classification on Graphs
    Georgy Sokolov*, MT*, Margarita Akhmejanova*, Fabio Vitale, Francesco Orabona
    ALT (2025)

    [pdf] [video] [reviews] [conference]

  6. Maximally Expressive GNNs for Outerplanar Graphs
    Franka Bause*, Fabian Jogl*, Patrick Indri, Tamara Drucks, David Penz, Nils Kriege, Thomas Gärtner, Pascal Welke, MT
    TMLR (2025)

    [pdf] [reviews] [journal]

  7. Bandits with Abstention under Expert Advice
    Stephen Pasteris, Alberto Rumi, MT, Shota Saito, Atsushi Miyauchi, Fabio Vitale, Mark Herbster
    NeurIPS (2024)

    [pdf] [reviews] [conference]

  8. Efficient Algorithms for Learning Monophonic Halfspaces in Graphs
    Marco Bressan, Emmanuel Esposito, MTαβ
    COLT (2024)

    [pdf] [conference]

  9. A Theory of Interpretable Approximations
    Marco Bressan, Nicolò Cesa-Bianchi, Emmanuel Esposito, Yishay Mansour, Shay Moran, MTαβ
    COLT (2024)

    [pdf] [conference]

  10. Expressivity-Preserving GNN Simulation
    Fabian Jogl, MT, Thomas Gärtner
    NeurIPS (2023)

    [pdf] [poster] [reviews] [conference]

  11. Expectation-Complete Graph Representations with Homomorphisms
    Pascal Welke*, MT*, Fabian Jogl, Thomas Gärtner
    ICML (2023)

    [pdf] [poster] [slides] [video] [code] [reviews] [arXiv] [conference]

  12. Active Learning of Classifiers with Label and Seed Queries
    Marco Bressan, Nicolò Cesa-Bianchi, Silvio Lattanzi, Andrea Paudice, MTαβ
    NeurIPS (2022)

    [video] [arXiv] [conference]

  13. Online Learning of Convex Sets on Graphs
    MT, Thomas Gärtner
    ECMLPKDD (2022)

    [pdf] [conference]

  14. Active Learning of Convex Halfspaces on Graphs
    MT, Thomas Gärtner
    NeurIPS (2021)

    [pdf] [slides] [video] [code] [reviews] [conference]

  15. Improving a Branch-and-Bound Approach for the Degree-Constrained Minimum Spanning Tree Problem with LKH
    MT, Luis Quesada, Kenneth N Brown
    CPAIOR (2020)

    [video] [conference]

(* shared first)

Workshop Papers and Extended Abstracts

  1. Efficient Minimization of Peakless Functions on Bounded-degree Graphs
    Christoph Sandrock, Sebastian Lüderssen, MT, Thomas Gärtner
    MLG@ECMLPKDD (2025)

    [pdf] [workshop]

  2. Bandits with Abstention under Expert Advice
    Stephen Pasteris, Alberto Rumi, MT, Shota Saito, Atsushi Miyauchi, Fabio Vitale, Mark Herbster
    ForLaC (2024)

    [workshop]

  3. Maximally Expressive GNNs for Outerplanar Graphs
    Franka Bause*, Fabian Jogl*, Patrick Indri, Tamara Drucks, David Penz, Nils Kriege, Thomas Gärtner, Pascal Welke, MT
    GLFrontiers@NeurIPS (2023)

    [workshop]

  4. Extending Graph Neural Networks with Global Features
    Andrei Dragos Brasoveanu*, Fabian Jogl*, Pascal Welke, MT
    LoG (2023)

    [workshop]

  5. Maximally Expressive GNNs for Outerplanar Graphs
    Franka Bause*, Fabian Jogl*, Pascal Welke, MT
    LoG (2023)

    [workshop]

  6. Generalized Laplacian Positional Encoding for Graph Representation Learning
    Sohir Maskey, Ali Parviz, MT, Hannes Stärk, Ylli Sadikaj, Haggai Maron
    NeurReps@NeurIPS (2022)

    [pdf] [reviews] [arXiv] [workshop]

  7. Expectation Complete Graph Representations using Graph Homomorphisms
    Pascal Welke*, MT*, Thomas Gärtner
    LoG (2022)

    [pdf] [poster] [code] [reviews] [conference]

  8. Expectation Complete Graph Representations using Graph Homomorphisms
    MT*, Pascal Welke*, Thomas Gärtner
    GLFrontiers@NeurIPS (2022)

    [pdf] [poster] [code] [reviews] [workshop]

  9. Weisfeiler and Leman Return with Graph Transformations
    Fabian Jogl, MT, Thomas Gärtner
    MLG@ECMLPKDD (2022)

    [pdf] [workshop]

  10. Reducing Learning on Cell Complexes to Graphs
    Fabian Jogl, MT, Thomas Gärtner
    GTRL@ICLR (2022)

    [pdf] [reviews] [workshop]

  11. Active Learning Convex Halfspaces on Graphs
    Fabian Jogl, MT, Thomas Gärtner
    SubSetML@ICML (2021)

    [pdf] [video] [code] [workshop]

  12. Active Learning on Graphs with Geodesically Convex Classes
    MT, Thomas Gärtner
    MLG@KDD (2020)

    [pdf] [video] [code] [workshop]

Community Activities

  1. Program committee member/reviewer at conferences: COLT26, ALT26, NeurIPS21'22*'23*'24'25, ICML'22*'23'24'25,26, ICLR'24, ECMLPKDD'22'23*'24'25, LOG'22'23, and LWDA'22.
  2. Reviewer for MLJ and the ECMLPKDD journal track (2023).
  3. Organizer of MLG@ECMLPKDD 2022, 2023, and 2024, the 18th, 20th, and 22nd Workshop on Mining and Learning with Graphs.
  4. Co-organizer of Graph Learning on Wednesdays (GLOW), a monthly reading group focusing on interactive disucssions.
  5. Co-organizer of C'Est La Wien '23, the Community Event for Students of Learning Algorithms in Wien.
  6. Session chair at ECMLPKDD'23.
  7. Co-organizer of a machine learning course for children at the KinderUni Wien (2022).
(* top reviewer)

People

Collaborators and colleagues

Contact

You can find me on Bluesky, Twitter, LinkedIn, and Google scholar.

Office: 2nd Floor, Erzherzog-Johann-Platz 1 (FB02), 1040 Vienna, Austria.
Email: You can send mail to maximilian.thiessen@tuwien.ac.at.

This page is blatantly copied from my lovely colleague Pascal Welke. It tries to be minimalistic in layout, bandwith, and used tools. It is hosted on Github pages, using neat.css stylesheets, and bibtexparser to generate the lists of references.