BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen - ECPv5.7.0//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen
X-ORIGINAL-URL:https://www.greyc.fr
X-WR-CALDESC:évènements pour GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:20250330T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:20251026T010000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20250930T104500
DTEND;TZID=Europe/Paris:20250930T114500
DTSTAMP:20260419T024556
CREATED:20250901T143917Z
LAST-MODIFIED:20250924T083807Z
UID:11939-1759229100-1759232700@www.greyc.fr
SUMMARY:Séminaire Algorithmique : Etienne Grandjean (GREYC)\, « How does preprocessing make it possible to obtain constant time? »
DESCRIPTION:In this work co-written by Louis Jachiet (Télécom Paris)\, we attempt to answer the following questions: Given that many computer systems are efficient thanks to preprocessing (index calculations in a database\, knowledge compilation in AI)\, which complexity classes with preprocessing are relevant? In this framework\, does constant time have any meaning? For this purpose\, we define the class Const-PP (constant time with preprocessing) of operations on natural numbers computable in constant time after preprocessing in linear time. Our model of computation is the random access machine (RAM) using only addition. \nWe prove that most of the usual arithmetic functions belong to this class (= are computable in constant time after linear preprocessing): multiplication\, division\, square root\, logarithm\, etc. We also show that the Const-PP class is robust (= does not change for many changes)\, for example if the set of native operations of the RAM is modified\, e.g. is {+\,-\,x\,div} instead of {+}\, or if the preprocessing time O(N) increases to O(N^c) or decreases to O(N^{1/c})\, for any constant c > 1. Interestingly\, the robustness of the Const-PP class implies that the usual complexity classes on RAMs are equally robust. For example\, the class Time(T(N)) of problems computable in time O(T(N))\, for a time bound T(N) ≥ N\, is invariant whether the native operations of a RAM are +\,-\,x\,div or are reduced to +. I will conclude the presentation with some open problems.
URL:https://www.greyc.fr/event/seminaire-algorithmique-etienne-grandjean-greyc-which-time-complexity-classes-make-sense/
LOCATION:Sciences 3- S3 351
CATEGORIES:Amacc,General,News,Séminaire Algo
END:VEVENT
END:VCALENDAR