Paulin de Naurois 
  Research Team Logic, Computation and Reasonning (LCR)
Research Topic
Linear logic, proof-nets and applications

Paulin Jacobé de Naurois

Version Française

ANR Project COMPLICE: (Implicit Computational Complexity, Concurrency and Extraction)

 + [33] 1 49 40 44 43
Laboratoire d'Informatique de l'Université Paris Nord (LIPN)
Institut Galilée - Université Paris-Nord
99, avenue Jean-Baptiste Clément 
93430 Villetaneuse

I am a former student of the École Normale Supérieure de Lyon (1998-2002).
I have done a joint PhD between the INPL, in Nancy, France, and City University of Hong Kong.
My supervisors were Jean-Yves Marion and Olivier Bournez in Nancy, and Felipe Cucker in Hong Kong.

I now hold a CNRS research assistant position in the computer science department of Institut Galilée at Université Paris-Nord. The research lab where I belong is LIPN. I work in the research team Logic, Computation and Reasonning (LCR), on the topic Linear logic, proof-nets and applications.


My research field is complexity theory. More precisely, I have studied syntactic characterizations of complexity classes in the BSS model of computation over arbitrary structures. I have also been interested in the BSS computation over real numbers with addition and order (additive case), and I have obtained new completeness results for natural geometrical and topological problems.


Research reports:

  • Paulin Jacobé de Naurois: Coverability in a NonFunctional Extension of BVASS. 2014. (download .pdf)


  • Paulin Jacobé de Naurois, Virgile Mogbil: Correctness of linear logic proof structures is NL-complete. Theor. Comput. Sci. 412(20): 1941-1957 (2011)
  • Felipe Cucker, Paulin Jacobé de Naurois: Parallel Time and Quantifier Prefixes. Computational Complexity 18(4): 527-550 (2009)
  • Peter Bürgisser, Felipe Cucker, Paulin Jacobé de Naurois: The complexity of semilinear problems in succinct representation. Computational Complexity 15(3): 197-235 (2006) (download .pdf)
  • O. Bournez, F. Cucker, P. Jacobé de Naurois and J.-Y.Marion, Implicit Complexity over an Arbitrary Structure: Quantifier Alternations.  Information and Computation, Volume 204, Issue 2, February 2006, Pages 210-230. (download .pdf)
  • O. Bournez, F. Cucker, P. Jacobé de Naurois and J. -Y. Marion, Implicit Complexity over an Arbitrary Structure: Sequential and Parallel Polynomial Time, Journal of Logic and Computations, Volume 15, February 2005, Pages 41 - 58. (download .pdf)