Orateurs invités (1h)

Véronique Cortier

(Loria, Nancy)

Titre: Vote électronique : la logique à la rescousse.

Résumé: Le vote électronique se doit d'offrir les mêmes garanties que le vote traditionnel à l'urne. Dans ce but, les protocoles de vote électronique ont recours à des primitives cryptographiques, comme dans le cas plus classique des protocoles d'authentification ou d'échange de clefs. Il est désormais reconnu que tous ces protocoles sont difficiles à concevoir et à vérifier. Ainsi, des attaques peuvent être découvertes des années plus tard. Les modèles formels, comme les algèbres de processus, les clauses de Horn ou les systèmes de contraintes, ont été utilisés avec succès pour analyser automatiquement de nombreux protocoles. Cependant, les protocoles de vote électronique compliquent significativement la tâche des outils de vérification. En effet, ils font appel à des primitives souvent nouvelles et complexes (comme le chiffrement homomorphique), à de nouveaux schémas d'exécution et assurent de nouvelles propriétés de sécurité.
Après une introduction au vote électronique, nous décrirons différentes techniques d'analyses formelles applicables au vote électronique et les nombreux problèmes qui restent à résoudre.

Javier Esparza

(Université Technique de Munich, Allemangne)

Titre: Stochastic Process Creation

Résumé: Branching processes are stochastic processes modeling the behaviour of populations whose individuals die and reproduce. We have studied some of these processes from a computer science point of view, and considered questions like: How fast can we compute the probability of extinction (that is, the probability that at some point in time no descendants of the original process are alive)? How much memory is needed in average to simulate a process in a computer? I report on our results, which show some beautiful connections between seemingly unrelated disciplines.

Joachim von zur Gathen

(Bonn-Aachen International Center for Information Technology, Allemagne)

Titre: Combinatorics on polynomial equations: do they describe nice varieties?

Résumé: We consider natural combinatorial questions about systems of multivariate polynomials over a finite field and the variety that they define over an algebraic closure. Fixing the number of variables, the number of polynomials and the sequence of degrees, there are finitely many such systems. We ask: for how many systems is the variety nice? Is that usually the case?
"Nice" can refer to various properties: The system is regular, the variety is a set-theoretic (or ideal-theoretic) complete intersection, it is (absolutely) irreducible, or nonsingular.
All properties usually hold. More precisely, for each of them we present a nonzero obstruction polynomial in the coefficients of the system so that the property holds when the obstruction does not vanish. The obstructions come with explicit bounds on their degrees. They yield estimates on the probability for the properties to hold. These probabilities tend rapidly to 1 with growing field size.
A further important property is non-degeneracy: the variety is not contained in a hyperplane. Somewhat surprisingly, this behaves differently. Fixing the dimension and the degree, most systems (with at least two polynomials) describe varieties that are hypersurfaces in some proper linear subspace. Thus they are highly degenerate.
Joint work with Guillermo Matera.

Francisco Santos Leal

(Université de Cantabrie, Espagne)

Titre: Diameters of polyhedra and simplicial complexes

Résumé: The Hirsch conjecture, posed in 1957, stated that the graph of a d -dimensional polytope or polyhedron with n facets cannot have diameter greater than n−d . The conjecture itself has been disproved by Klee-Walkup (1967) for unbounded polyhedra and by Santos (2010) for bounded polytopes, but what we know about the underlying question is quite scarce. Most notably, no polynomial upper bound is known for the diameters that were conjectured to be linear. In contrast, no polyhedron violating the Hirsch bound by more than 25% is known.
In this talk we review several recent attempts and progress on the question. Some of these work in the world of polyhedra or (more often) bounded polytopes, but some try to shed light on the question by generalizing it to simplicial complexes. In particular, we show that the maximum diameter of arbitrary simplicial complexes is in $n^{\Theta(d)}$ , we sketch the proof of Hirsch's bound for ``flag'' polytopes (and more general objects) by Adiprasito and Benedetti via ``combinatorial segments'', a recent construction of Labbé, Manneville and Santos showing that combinatorial segments in non-flag polytopes can have exponential length, and a recent construction by Bogart and Kim of paths of almost quadratic length in the context of subset partition graphs.

---