Nathan Grosshans

Ph.D. student, ENS Cachan & UdeM

About me

Short presentation

I am a Ph.D. student under international joint supervision since the 15 September 2014 at the Ecole Normale Supérieure de Cachan, under the supervision of Luc Segoufin within the Laboratoire Spécification et Vérification (LSV) on the one side; and at the Université de Montréal, under the supervision of Pierre McKenzie within the Laboratoire d'Informatique Théorique et Quantique (LITQ) on the other side.

Documents

Research

Ph.D. thesis subject

Title

Applications and limits of recent branching program lower bounds.

Domains

Computational complexity theory, automata theory, logic.

Summary

Computational complexity aims at classifying computational problems according to the amounts of resources needed for solving these problems. The challenge that arises is often the lower bounds issue: given a problem and an apparently optimal solution strategy for it, back the intuition up with a formal mathematical proof that no better strategy exists. A flurry of recent work has focused on the branching program computation model. The goal of this project is

  1. to push these results further,
  2. to explain the limits of these methods and
  3. to cross-breed these methods (in particular those that pertain to the tree evaluation problem) with the techniques developed over the course of a decade to capture the power of tree automata models and their precise logical characterizations.

Publications

See my list of publications.

Teaching

As part of my Ph.D. studies, I am in charge of a teaching mission at the ENS Cachan.

2016-2017

Projet programmation 2 (1A Informatique)

Projet
Cours

Projet base de données (1A Informatique)

Projet

Sujet

Cours

TP de calcul formel (M2 FESUP Mathématiques, option C)

01/25 : Complexité

2015-2016

Projet base de données (1A Informatique)

2014-2015

Soutien (1A Informatique)

Initiation à LaTeX

Génie logiciel (2A Informatique)

TP de calcul formel (M2 FESUP Mathématiques, option C)

03/17 : Énumération du groupe symétrique
03/24 : Élimination

About LSV

Contact

Nathan Grosshans
Address
LSV, CNRS & ENS de Cachan
61, avenue du Président Wilson
94235 CACHAN Cedex, France
Office
4ème étage, Bâtiment d'Alembert
Phone
+33 (0)1 47 40 22 69
Fax
+33 (0)1 47 40 75 21
Secr.
+33 (0)1 47 40 75 20
E-Mail
first_name.last_name@lsv.ens-cachan.fr