![[LIPN]](/blog-themes/lipn-automne/img/logo_lipn.png){kind=logo}
![[CNRS]](/blog-themes/lipn-automne/img/logo_cnrs.png){kind=logo}
![[Université Paris 13]](/blog-themes/lipn-automne/img/logo_paris13.png){kind=logo}
Le 30 avril 2012, à 14h en salle B311, le séminaire LCR accueille Barbara Petit (Bologne).
Keyword - complexité implicite
Monday 23 April 2012
Monday 23 April 2012 at 02.00 PM — Seminars
Le 23 avril 2012, à 14h en salle B311, le séminaire LCR accueille Paolo Parisen Toldin (Bologne).
Contrary to ICC standard approach, we present a small WHILE language characterizing the class PP.
The main problem concerning the imperative approach is to understand how informations/values flow throw variables in a program.
In literature are well known many works that have polytime soundness but just few of them (using the imperative paradigm) are able to give a polytime completeness.
Our system, MAL0 (Multiplied, Affine, Linear, 0 dependeces ), is sound and complete. Moreover, our system can be used also to check if a program is running in probabilistic polytime (can be easily restrict to just polytime soundness). We claim that, contrary to works found in literature, our system is able to certify a program in polytime.
This is a joint work in progress with Jean-Yves Moyen.
Monday 28 November 2011
Monday 28 November 2011 at 02.00 PM — Seminars
Le 28 novembre 2011, à 14h en salle B311, le séminaire LCR accueille Paolo Parisen Toldin (Bologne).
We present RSLR, an implicit higher-order characterization of the class PP of those problems which can be decided in probabilistic polynomial time with error probability smaller than 1/2. Analogously, a (less implicit) characterization of the class BPP can be obtained. RSLR is an extension of Hofmann’s SLR with a probabilistic primitive, which enjoys basic properties such as subject reduction and confluence. Polynomial time soundness of RSLR is obtained by syntactical means, as opposed to the standard literature on SLR-derived systems, which use semantics in an essential way.
Monday 24 October 2011
Monday 24 October 2011 at 02.00 PM — Seminars
Le 24 octobre 2011, à 14h en salle B311, le séminaire LCR accueille Margherita Zorzi (LIPN, post-doc ANR Complice).
One of the strong motivations behind quantum computing is computational complexity: quantum computers seem to be able to solve efficiently classical hard problems, thanks to the potential speed up in the execution time induced by superposition phenomena.
Quantum complexity theory has been developed since the Nineties, after the definition of quantum computational models such as quantum Turing machines and quantum circuit families. A particular attention is devoted to the quantum polytime classes (EQP, BQP, ZQP).
After a preliminarily discussion about quantum models and quantum complexity theory, the polytime quantum lambda calculus SQ (inspired by soft linear logic) is presented, showing an Implicit Computational Complexity approach in the quantum setting.
Monday 28 March 2011
Monday 28 March 2011 at 03.30 PM — Seminars
Le 28 mars 2011, à 15h30 en salle B311, le séminaire LCR accueille Pierre Clairambault (Université de Bath, Royaume Uni).
We estimate the maximal length of interactions between strategies in HO/N game semantics, in the spirit of the work by Schwichtenberg and Beckmann for the length of reduction in simply typed lambda calculus. Because of the operational content of game semantics, the bounds presented here also apply to head linear reduction on lambda terms and to the execution of programs by abstract machines, including in presence of computational effects such as non-determinism or ground type references. The proof proceeds by extracting from the games model a combinatorial rewriting rule on trees of natural numbers, which can then be analysed independently of game semantics or lambda calculus
Monday 21 March 2011
Monday 21 March 2011 at 03.30 PM — Seminars
Le 21 mars 2011, à 15h30 en salle B311, le séminaire LCR accueille Jean-Yves Moyen (LIPN, Paris 13).
Les QI et l’analyse mwp sont deux techniques de complexité implicite pour caractériser Ptime. Les QI travaillent avec des programmes fonctionnels tandis que l’analyse mwp étudie des programmes impératifs.
Je montre, via une transformation de programmes, que bien qu’étant apparemment très différentes ces deux techniques sont moralement équivalentes et capables d’analyser les mêmes cas.
Monday 20 December 2010
Monday 20 December 2010 at 03.30 PM — Seminars
Le 20 décembre 2010, à 15h30 en salle B311, le séminaire LCR accueille Ugo Dal Lago (Bologne).
We consider the problem of functional programming with data in external memory, in particular as it appears in sublinear space computation. Writing programs with sublinear space usage often requires one to use special implementation techniques for otherwise easy tasks, e.g. one cannot compose functions directly for lack of space for the intermediate result, but must instead compute and recompute small parts of the intermediate result on demand. We study how the implementation of such techniques can be supported by functional programming languages.
Monday 13 December 2010
Monday 13 December 2010 at 03.30 PM — Seminars
Le 13 décembre 2010, à 15h30 en salle B311, le séminaire LCR accueille Simone Martini (Bologne, Professeur invité à Paris 13).
I will discuss an application of light/soft linear logic technology to restrict the higher order pi-calculus. In this restricted calculus any process terminates in polynomial time. While several interesting processes are expressible, more work is needed to understand a satisfactory way of describing "resource bounded" processes.
Tuesday 2 December 2008
Tuesday 2 December 2008 at 04.00 PM — PhD & Habilitations defends
Bonjour à tous, j’ai le plaisir de vous inviter à la soutenance de ma thèse intitulée « Typage et Réduction Optimale pour le lambda-calcul dans les variantes de la Logique Linéaire pour la complexité implicite ».
La soutenance aura lieu salle B311 du LIPN (Institut Galilée) à Paris-13 Villetaneuse le mardi 2 décembre à 16h00 (plan d’accès) et le jury sera composé de :
- Patrick Baillot, CNRS/ENS Lyon, Directeur
- Christophe Fouqueré, Université Paris 13, Examinateur
- Ian Mackie, CNRS/Ecole Polytechnique, Rapporteur
- Simone, Martini, Università di Bologna, Rapporteur
- Virgile Mogbil, Université Paris 13, Examinateur
- Laurent Regnier, Université Aix-Marseille 2, Examinateur
- Simona Ronchi Della Rocca, Università di Torino, Examinatrice
- Jacqueline Vauzeilles, Université Paris 13, Co-Directrice
Vous êtes bien sûr également conviés au pot qui suivra. Une page regroupant les informations sur la soutenance et contenant une version préliminaire du manuscrit est disponible : http://www-lipn.univ-paris13.fr/~atassi/soutenance/
Monday 24 November 2008
Monday 24 November 2008 at 01.30 PM — Seminars
The next meeting of the GdT "Logique et Programmation" will take place on
Monday, 24 November 2008,
at 1:30 pm, in room B311.
We will listen to a talk given by Amir Ben-Amram, invited researcher from the School of Computer Science at the Academic College of Tel-Aviv Yaffo, who will tell us about his latest ideas regarding size-change termination.
« previous entries - page 1 of 2
![[ICS]](http://www-lipn.univ-paris13.fr/actualites/?pf=icsfeed/icon.png){kind=icon}
Events related to tag 'complexité implicite' (ICS format)
About the ICS format