Les lundis, à partir de 14h - UPEC CMC - Salle P2-131

26 juin 2017

On more variants of the Majority Problem

Emmanuel Preissmann

The problem we are considering is the following. A colorblind player is given a set B={b1,b2,...,bN} of N colored balls. He knows that each ball is colored either red or green, and that there are less green balls (this will be called a Red-green coloring), but he cannot distinguish the two colors. For any two balls he can ask whether they are colored the same. His goal is to determine the set of all green balls of B (and hence the set of all red balls). We study here the case where the Red-green coloring is such that there are at most p green balls, where p is given, and denote by Q(N,p,) the minimum integer k such that there exists a method that finds for sure, for any Red-green coloring, the color of each ball of B after at most k (color) comparisons. We extend the cases for which the exact value of Q(N,p,) is known and provide lower and upper bounds as well as exact values for Q(N,p,=) (defined similarly as Q(N,p,), but for a Red-green coloring with exactly p green balls)

12 juin 2017

TBA

Yuri Gurevich (Microsoft Research)

12 juin 2017

Quantum computing and abstract state machines

Yuri Gurevich (Microsoft Research)

Computations are performed in physical world. This requires sophisticated physics and engineering. Computer science abstracts away the physical and engineering problems; computer scientists and programmers may be blissfully unaware of them. Their levels of abstraction keep rising, making abstract state machines ever more useful.

12 juin 2017

Quantum computing and abstract state machines

Yuri Gurevich (Microsoft Research)

Computations are performed in physical world. This requires sophisticated physics and engineering. Computer science abstracts away the physical and engineering problems; computer scientists and programmers may be blissfully unaware of them. Their levels of abstraction keep rising, making abstract state machines ever more useful.

22 mai 2017

On the chemistry of typestate-oriented actors

Silvia Crafa (Université de Padoue)

Typestate-oriented programming is an extension of the OO paradigm in which objects are modeled not just in terms of interfaces but also in terms of their usage protocols, describing legal sequences of method calls, possibly depending on the object’s internal state. We argue that the Actor Model allows typestate-OOP in an inherently distributed setting, whereby objects/actors can be accessed concurrently by several processes, and local entities cooperate to carry out a communication protocol. We illustrate the approach by means of a number of examples written in Scala Akka.

15 mai 2017

Pavages par coupe et projection de type fini

Thomas Fernique (LIPN)

Les pavages par coupe et projection sont des discrétisations de plans d’un espace de dimension plus grande. Quand la pente du plan est irrationnelle, on obtient un pavage apériodique, fréquemment utilisé pour modéliser les quasicristaux. Dans ce contexte, il est important de comprendre à quelle condition un tel pavage est de type fini, c’est-à-dire peut être décrit par ses seules configurations locales (malgré son apériodicité). On montrera qu’une condition nécessaire est que la pente soit algébrique. On discutera de la réciproque.

15 mai 2017

Pavages par coupe et projection de type fini

Thomas Fernique (LIPN)

Les pavages par coupe et projection sont des discrétisations de plans d’un espace de dimension plus grande. Quand la pente du plan est irrationnelle, on obtient un pavage apériodique, fréquemment utilisé pour modéliser les quasicristaux. Dans ce contexte, il est important de comprendre à quelle condition un tel pavage est de type fini, c’est-à-dire peut être décrit par ses seules configurations locales (malgré son apériodicité). On montrera qu’une condition nécessaire est que la pente soit algébrique. On discutera de la réciproque.

24 avril 2017

Computational modeling using P systems

Agustín Riscos Núñez (Universidad de Sevilla)

The talk will try to provide a general overview of modeling frameworks for systems biology and population dynamics based on membrane computing.
We will overview some recent achievements which show that this unconventional and bio-inspired computing paradigm can be an alternative to classical modeling frameworks (e.g. those based on differential equations).
We will also refer to the associated simulation software tools which are necessary to enable virtual experimentation, as well as for the process of model validation.

3 avril 2017

Non-commutative lower bounds

Guillaume Lagarde (IRIF)

No knowledge in arithmetic complexity will be assumed.
We still don’t know an explicit polynomial that requires non-commutative circuits of size at least superpolynomial.
However, the context of non commutativity seems to be convenient to get such lower bound because the rigidity of the non-commutativity implies a lot of constraints about the ways to compute.
It is in this context that Nisan, in 1991, provides an exponential lower bound against the non commutative Algebraic Branching Programs computing the permanent, the very first one in arithmetic complexity. We show that this result can be naturally seen as a particular case of a theorem about circuits with *unique parse tree*, and show some extensions to get closer to lower bounds for general NC circuits.
Two joint works: with Guillaume Malod and Sylvain Perifel; with Nutan Limaye and Srikanth Srinivasan.

27 mars 2017

TBA

Catalin Dima (LACL)

TBA