BEGIN:VCALENDAR
VERSION:2.0
X-WR-TIMEZONE:Europe/Paris
CALSCALE:GREGORIAN
PRODID:-//SPIP/Plugin Agenda//NONSGML v1.0//FR
X-WR-CALNAME;VALUE=TEXT: -- Institut de Mathématiques de Marseille\, UMR 7373
X-WR-RELCALID:https://www.i2m.univ-amu.fr/spip.php?page=article&id_article=0
BEGIN:VEVENT
SUMMARY:Anupam DAS - Monotonicity in Logic and Complexity
UID:20170126T105303-a123-e1634@https://www.i2m.univ-amu.fr
DTSTAMP:20170126T105303
DTSTART:20170302T110000
DTEND:20170302T120000
CREATED:20170126T105303
ATTENDEE;CN=Anupam DAS:mailto:no-reply@math.cnrs.fr
LAST-MODIFIED:20170301T105425
LOCATION:Salle des séminaires 304-306 (3ème étage)
DESCRIPTION:Monotonicity is a fundamental notion in mathematics and computation. For usual real-valued functions R → R this simply corresponds to the notion that a function is increasing (or decreasing) in its argument\, however this can be parametrised by any partially ordered domain and codomain we wish. In computation we deal with programs that compute Boolean functions\, 0\,1* → 0\,1*. Restricting to increasing functions over this structure can be seen as prohibiting the use of negation in a program ; for instance monotone Boolean functions are computed by Boolean circuits without NOT gates. The idea of restricting negation scales to other models of computation\, and for some important classes of functions the formulation is naturally robust\, not depending on the particular model at hand\, e.g. for the polynomial-time functions. Monotone computational problems abound in practice\, e.g. sorting a string and detecting cliques in graphs\, and 'nonuniform' monotone models of computation\, such as monotone circuits\, have been fundamental objects of study in computational complexity for decades. In this talk I will propose a project that develops *logical* characterisations of monotone complexity classes\, via a proof theoretic approach. Namely\, the project will identify theories of arithmetic whose formally representable functions coincide with certain monotone classes\, and also develop fundamental recursion-theoretic programming languages in which to extract the monotone functions themselves. In particular the project focusses on the role of structural proof theory\, i.e. the duplication and erasure of formulae\, in controlling monotonicity. http://anupamdas.com Anupam DAS [
CATEGORIES:(Séminaire Logique et Interactions|textebrut|filtrer_ical)]
URL:https://www.i2m.univ-amu.fr/Seminaire-Logique-et-Interactions?id_evenement=1634
SEQUENCE:1
STATUS:CONFIRMED
END:VEVENT