Tito's presence on the Web

Welcome to my homepage! I am a graduate student in theoretical computer science at the Laboratoire d’informatique de Paris Nord (LIPN). I started my PhD in 2018 under the supervision of Stefano Guerrini and Thomas Seiller.

Contact / personal information:

Family name Given name Email address Visual identification
Nguyễn Lê Thành Dũng nltd at nguyentito dot eu no photo available yet

My research focuses on combinatorial and complexity-theoretic aspects of linear logic, a logical system born out of the proofs-as-programs correspondence (“Curry-Howard isomorphism”). I am particularly interested in possible connections between proof theory and other topics in computer science such as graph theory, implicit computational complexity, finite automata and transducers, descriptive complexity…

Outside of my research work, my scientific interests also span:

This page serves as my vita (kind of). You can also download a PDF resume (last updated May 2019) in French.


Full list of publications: see my dblp page.

The click-to-expand parts in this section use the HTML5 <details> element, no JavaScript involved! (However, Markdown/pandoc adds <p> tags…)

Not my own work

A scan of a paper of Leivant & Marion: TODO.

Some slides on the expressivity of the simply-typed λ-calculus:

Unique perfect matchings, edge-colored graphs and proof nets

Description By extending ideas by Christian Retoré, I provided a correspondence between graphs equipped with perfect matchings and proof nets for linear logic, a graphical representation of proofs. This relates the combinatorially tricky theory of proof nets with a well-studied counterpart in mainstream graph theory. The relationship is not bijective, but there are reductions in both directions preserving many structural properties (some of which were overlooked by Retoré’s pioneering work); in particular, correctness of a proof corresponds to uniqueness of a perfect matching, and sequentializations correspond to bridge elimination orderings.

I also worked on edge-colored graphs and paths/trails avoiding forbidden transitions, both as a topic of intrinsic interest and to apply them to proof nets.


Talks (for logicians)

Talks (for graph theorists)

Revisiting implicit complexity in linear logic with finite semantics of polymorphism and automata theory

Description It is hard to summarize this research project, and the order of publication is all messed up relatively to both the order of discovery and the logical dependencies.

Basically, we are working at the confluence of:

This leads, for instance, to characterizations in (variants of) linear logic of


Talks (for an audience familiar with linear logic and/or denotational semantics)

Talks (for the implicit computational complexity community)


Coherent interaction graphs This is a rather specialized and technical topic. We build a variant of Seiller’s interaction graphs in which the correctness criterion for proof nets admits a convincing interpretation as a non-deterministic counter-proof. That is, we revisit an idea from the early days of linear logic (cf. Girard’s Multiplicatives paper) in a more satisfactory way.

The work was presented at the Linearity-TLLA 2018 joint workshop, and published in its post-proceedings.

Unfruitful work in combinatorial optimization (Master’s internship) In 2016, I did a 4-month internship with Christoph Dürr and Nguyễn Kim Thắng for my master’s degree. We tried to design an approximation algorithm for the online node-weighted Steiner forest problem. Our approach didn’t work, but we improved our understanding of the difficulty of the problem. However, thanks to a recreational algorithmic puzzle given by Christoph during this internship, I learned about the relationship between perfect matchings and edge-colored graphs, which would eventually lead to my above-mentioned work. You can see my first ideas on these topics and their connection to linear logic in the slides of the defense (in French).

Involvement in computer science teaching / outreach

University teaching

In 2016, I was a teaching assistant for the Algorithms course given by Gaël Mahé at Université Paris Descartes for second-year students.

Since 2018, I have been TAing as part of my PhD at Institut Galilée, Université Paris 13. See my courses webpage (French).


As a member of the Prologin organization from 2014 to 2018, I helped organize Prologin, a programming contest for people under 20 years old, and Girls Can Code!, a summer coding camp.

I was in charge of the semifinal problems in 2015 and 2016. Furthermore, in 2015, I was the main developer on the game for which the contestants had to write an AI during the finals; and from mid-2015 to mid-2016, I was heavily involved in the logistics of both Prologin and Girls Can Code! as a board member.

From 2017 to 2018, I designed and implemented programming contest exercises as a freelance consultant for Isograd, selling the skills that I had developed thanks to Prologin to the private sector.

Science popularization

Jérémy Ledent and I wrote some articles for Tangente, a French math magazine for high schoolers, on the aforementioned proofs-as-programs correspondance and on homotopy type theory.


Academic studies


Programming experience

My projects: see my Github account and my Bitbucket account, or this page.



I used to contribute to ENS’s student newspaper.