(1) While point-set topology is highly practical as a framework to do spatial reasoning, one can rise some ontological and logical suspicions about naive notion of points as they constitute idealized objects with somewhat inaccessible aspects in a constructive and finite point of view. Locales and Frames theories are two deeply entangled realms aimed at rebuilding topology on latticial and categorical foundations, in which usual notions of points, opens, subspaces, separability, compacity… can be reexpressed as first order algebraic properties in latticial context, or both generalized and made constructive.

Formal topology goes further into this last direction, using systems of axioms about coverings as a deductive systems which leads to a type-theoretic flavored, predicative and constructive topology, endowed with multiple and finer notions of points, separability… and suited for intuitionistic reasoning.

(2) The Number On the Forehead model is a multiparty communication game between k players that collaboratively want to evaluate a given function F : X1 x … x Xk → Y on some input (x1, …, xk) by broadcasting bits according to a predetermined protocol. The input is distributed between the players in such a way that each player i sees all of it except xi (as if xi is written on the forehead of player i).

A central open question in this model, called the log n barrier, is to find a function which is hard to compute when the number of players is polylog(n) or more (where the xi's have size poly(n)). This has an important application in circuit complexity, as it could help to separate ACC0 from other complexity classes.

In this talk, we will recall first the connection between ACC0 and communication complexity, and then describe a new efficient communication protocol that prevents some important functions from breaking the log n barrier.