BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//7.2.3.1//EN
TZID:Europe/Paris
X-WR-TIMEZONE:Europe/Paris
BEGIN:VEVENT
UID:7622@i2m.univ-amu.fr
DTSTART;TZID=Europe/Paris:20170302T110000
DTEND;TZID=Europe/Paris:20170302T120000
DTSTAMP:20241120T204428Z
URL:https://www.i2m.univ-amu.fr/evenements/monotonicity-in-logic-and-compl
 exity/
SUMMARY:Anupam Das (LIP\, ENS Lyon): Monotonicity in Logic and Complexity
DESCRIPTION:Anupam Das: Monotonicity is a fundamental notion in mathematics
  and computation. For usual real-valued functions R → R this simply corr
 esponds to the notion that a function is increasing (or decreasing) in its
  argument\, however this can be parametrised by any partially ordered doma
 in and codomain we wish. In computation we deal with programs that compute
  Boolean functions\, {0\,1}* → {0\,1}*. Restricting to increasing functi
 ons over this structure can be seen as prohibiting the use of negation in 
 a program\; for instance monotone Boolean functions are computed by Boolea
 n circuits without NOT gates. The idea of restricting negation scales to o
 ther models of computation\, and for some important classes of functions t
 he 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 mono
 tone circuits\, have been fundamental objects of study in computational co
 mplexity for decades.\n\nIn this talk I will propose a project that develo
 ps *logical* characterisations of monotone complexity classes\, via a proo
 f theoretic approach. Namely\, the project will identify theories of arith
 metic whose formally representable functions coincide with certain monoton
 e classes\, and also develop fundamental recursion-theoretic programming l
 anguages in which to extract the monotone functions themselves. In particu
 lar the project focusses on the role of structural proof theory\, i.e. the
  duplication and erasure of formulae\, in controlling monotonicity.\n\n\n
ATTACH;FMTTYPE=image/jpeg:https://www.i2m.univ-amu.fr/wp-content/uploads/2
 020/01/Anupam_Das.jpg
CATEGORIES:Séminaire,Logique et Interactions
END:VEVENT
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:STANDARD
DTSTART:20161030T020000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
END:STANDARD
END:VTIMEZONE
END:VCALENDAR