Pierre Fraigniaud
email: pierre.fraigniaud@liafa.jussieu.fr

David Ilcinkas
email: david.ilcinkas@labri.fr

Andrzej Pelc
email: pelc@uqo.ca

Communication Algorithms with Advice 6

Keywords: Algorithm, Broadcasting, Wakeup, Size of advice, Message complexity, Network, Graph

published or not. The documents may come

Introduction

Background and related work

For many network problems (such as leader election, constructing a minimum spanning tree, exploration, wakeup, broadcast, etc.), the quality of the algorithmic solutions often depends on the amount of knowledge given to nodes of the network. For example, if every node knows the topology of the network within radius ρ of it, it is shown in [START_REF] Awerbuch | A trade-off between information and communication in broadcast protocols[END_REF] that Θ(min{m, n 1+Θ(1)/ρ }) is the minimum number of messages of bounded length permitting the wakeup of a network with n nodes and m edges. (In [START_REF] Awerbuch | A trade-off between information and communication in broadcast protocols[END_REF] the authors talk about the broadcast but their model does not permit transmissions before receiving the source message, hence it is called wakeup in our terminology). Broadcasting time in radio networks is another subject where information available to nodes significantly influences efficiency. In [START_REF] Gasieniec | Faster communication in known topology radio networks[END_REF] it is shown that if nodes have complete knowledge of the network, then there is a deterministic polynomial algorithm that produces a broadcast scheme of time O(D + log 3 n), for n-node radio networks with diameter D. (This result has been improved to O(D + log 2 n) in [START_REF] Kowalski | Optimal deterministic broadcasting in known topology radio networks[END_REF]). On the other hand, in [START_REF] Clementi | Selective families, superimposed codes, and broadcasting on unknown radio networks[END_REF] a lower bound of Ω(n log D) is proved on deterministic broadcast time in radio networks in which nodes know only their own identity. (An almost matching upper bound of O(n log 2 D) is proved in [START_REF] Czumaj | Broadcasting algorithms in radio networks with unknown topology[END_REF]). The differences between the broadcast and wakeup problems in radio networks were explored in [START_REF] Emek | Broadcasting time in UDG radio networks with unknown topology[END_REF][START_REF] Emek | On the effect of the deployment setting on broadcasting in Euclidean radio networks[END_REF].

Another problem, in which partial information about the network significantly influences the efficiency of solutions, is network exploration by a mobile agent. For instance, it is proved in [START_REF] Bender | The power of a pebble: Exploring and mapping directed graphs[END_REF] that, if an upper bound n on the number n of nodes of an anonymous digraph is known, then a mobile agent can explore this digraph in time polynomial in n, using one pebble, while without this knowledge, Θ(log log n) pebbles are necessary and sufficient. On the other hand, in [START_REF] Dessmark | Optimal graph exploration without good maps[END_REF] the authors investigate the exploration of various types of graphs when the exploring agent is provided with an unlabeled map of the graph, and show how the cost of exploration changes when no map is available. A more precise study of relationships between information about the explored graph and efficiency of exploration has been recently presented in [START_REF] Fraigniaud | Tree exploration with an oracle[END_REF] (see end of Section 1.2).

In fact, the impact of knowledge concerning the environment is significant in many areas of distributed computing, as witnessed by [START_REF] Fich | Hundreds of impossibility results for distributed computing[END_REF][START_REF] Lynch | A hundred impossibility proofs for distributed computing[END_REF] where hundreds of impossibility results and lower bounds for distributed computing are surveyed, many of them depending on whether or not the nodes are provided with partial knowledge of the topology of the network. Finally, notice that the amount of knowledge has also a strong impact on computing in anonymous networks (cf., e.g., [START_REF] Kameda | Computing on anonymous networks: Part I -characterizing the solvable cases[END_REF], where the impact of knowing the total number of nodes is studied in depth).

The advice

A network is modeled as an undirected connected graph whose nodes have distinct labels, and ports at any node v of degree deg(v) are labeled 0,1,...,deg(v) -1. One distinguished node of the network is called the source. A priori, every node has only information concerning itself: it knows its own label (if any), and it knows whether it is the source or not. All additional knowledge available to the nodes of the network (in particular knowledge concerning the rest of the network), is modeled by an oracle providing advice. An oracle is a function O whose arguments are networks, and the value O(G), for a network G = (V, E), called the advice provided by the oracle to this network, is in turn a function f : V → {0, 1} * assigning a binary string to every node v of the network. Intuitively, the oracle looks at the entire labeled network and assigns to every node some information, coded as a string of bits. The size of the advice given by the oracle to a given network G is the sum of the lengths of all the strings it assigns to nodes. Hence this size is a measure of the amount of information about the network, available to its nodes.

Solving a network problem P using advice provided by oracle O consists in designing an algorithm that is unaware of the network G at hand but solves the problem P for it, as long as every node v of the network G is provided with the string of bits f (v), where f = O(G). Typical distributed network problems that may be solved using advice are various communication tasks, such as broadcast, wakeup or gossip (information exchange among nodes), as well as, e.g., the construction of a BFS tree or a minimum spanning tree. The formulation of the problem P may include a demand on the efficiency of the solution, thus we may be interested in communicating within a prescribed time, or constructing a minimum spanning tree using at 2 most a prescribed number of messages. Given the problem P, we ask what is the minimum size of an advice for solving it. This minimum size of advice can be considered as a measure of the difficulty of the problem P. The novelty and significance of the concept of advice used to model knowledge about the network is that it enables asking quantitative questions about the required knowledge, regardless of what kind of knowledge is supplied. This should be contrasted with the traditional approach that assumes availability of particular items of information, such as the neighborhood of a node. It turns out that the minimum size of advice, for which a distributed task can be accomplished efficiently, can be used to make a quantitative distinction between the difficulty of apparently similar problems. We show this for two fundamental communication primitives performing information dissemination: the broadcast and the wakeup from a single source. In both of them a distinguished node, called the source, has a message which has to be transmitted to all other nodes of the network. Nodes send messages along edges of the network. In the wakeup, only nodes that already got the source message (i.e., are awake) can send messages to their neighbors, thus waking them up. In the broadcast, all nodes can send control messages even before getting the source message, thus potentially facilitating its future dissemination. In both cases we are interested in accomplishing the communication task with optimal message complexity, i.e., using a number of messages linear in the number of nodes. We ask what is the minimum size of advice permitting to do that.

An approach similar to ours has been developed in the context of informative labelings. Informative labeling schemes are ways to label the nodes of a network with short labels in such a way that queries such as inter-node distance [START_REF] Gavoille | Distance labeling in graphs[END_REF], ancestor [START_REF] Abiteboul | Compact labeling schemes for ancestor queries[END_REF], connectivity [START_REF] Katz | Labeling schemes for flow and connectivity[END_REF], etc., can be answered based solely on the labels of the nodes involved in the query. The main objective in this context is to design schemes using short labels, and guaranteeing that queries can be rapidly answered. The oracle terminology is sometimes also used in the context of informative labeling (e.g., when the query can be answered in constant time [START_REF] Thorup | Approximate distance oracles[END_REF]). Conversely, the informative labeling terminology is sometimes also used for problems involving global properties [START_REF] Korman | Proof labeling schemes[END_REF].

Our point of view is to use the informative labeling terminology in the context of distributed datastructures enabling quick answers to queries, and to use the advice and oracle terminology in the context of distributed computing when nodes have to collaborate to achieve complex tasks (e.g., broadcasting, coloring, wake-up, leader election, etc.). One reason motivating this view is, for instance, that giving the knowledge of the network size n to the nodes can hardly be seen as labeling every node by n. Also, the notion of advice easily extends to the case when the information is not given a priori, but on line, during the execution of the protocol.

After the conference version of this paper has appeared, the concept of advice has been used in various settings, namely in [START_REF] Fraigniaud | Tree exploration with an oracle[END_REF] to study efficient exploration of networks by mobile agents, in [START_REF] Fraigniaud | Distributed computing with advice: Information sensitivity of graph coloring[END_REF] to study distributed graph coloring, in [START_REF] Fraigniaud | Local MST computation with short advice[END_REF] to study the distributed minimum spanning tree construction, in [START_REF] Nisse | Graph searching with advice[END_REF] to study graph searching, in [START_REF] Ilcinkas | Fast radio broadcasting with advice[END_REF] to study radio broadcasting, and in [START_REF] Fusco | Trade-offs between the size of advice and broadcasting time in trees[END_REF] to study broadcasting in trees.

Our results

We show that the minimum size of advice permitting the wakeup with a linear number of messages in a network with at most n nodes, is Θ(n log n), while the broadcast with a linear number of messages can be achieved with advice of size O(n). We also show that the latter size of advice is almost optimal: no advice of size o(n) can permit to broadcast with a linear number of messages. Thus an efficient wakeup requires strictly more information about the network than an efficient broadcast.

Our upper bounds are constructive: we show specific oracles providing advice of appropriate size and design wakeup and broadcast algorithms using them and accomplishing information dissemination with a linear number of messages. Apart from their tightness, our results have the following additional strength. Both upper bounds hold even for totally asynchronous communication, for anonymous nodes (no distinct labels), and using only bounded-size messages. On the other hand, both lower bounds hold even for synchronous communication, for labels of nodes 1,...,n, and for arbitrarily long messages.

We consider wakeup from a single source, where only one node, the source, is awake in the beginning. We choose this communication primitive due to its similarity with broadcasting, since we want to compare the amount of information needed to efficiently accomplish similar tasks. However, both the upper and the lower bound on the size of advice for wakeup still hold for a more traditional formulation of the wakeup problem, where the adversary wakes up an arbitrary subset of nodes which in turn have to wake up all other nodes.

Terminology and preliminaries

We now describe broadcast algorithms using advice provided by oracles, in a more detailed manner. Wakeup algorithms will be a particular type of broadcast algorithms, subject to an additional constraint. Consider a network, i.e., a connected graph G = (V, E) with a distinguished source s. Every node v of degree deg(v) has a distinct label id(v), and ports at v are labeled 0, 1, ..., deg(v) -1. The port at node v, corresponding to edge e, is denoted by port v (e). Every node v has also a bit s(v) called the status bit, which is set to 1 if the node v is the source, and to 0 otherwise. Fix an oracle O and let the advice f = O(G) given by this oracle to network G be a function f : V → {0, 1} * , assigning binary strings to nodes of G. A broadcast algorithm A using advice provided by oracle O is a function A : {0, 1} * × {0, 1} × IN × IN → Σ, where IN denotes the set of non-negative integers and Σ denotes the set of broadcast schemes (to be defined below). For a given node v, algorithm A takes the quadruple (f (v), s(v), id(v), deg(v)) and returns a broadcast scheme

S v = A(f (v), s(v), id(v), deg(v))
for the node v. It remains to define what such a scheme is. Intuitively, this is a prescription whether and on which ports the node should send messages, and what messages, given a particular history of communication to date. Such a history (at node v) is a sequence

H = (f (v), s(v), id(v), deg(v), (m 1 , p 1 ), (m 2 , p 2 ), . . . , (m k , p k )), where the prefix (f (v), s(v), id(v), deg(v)
) is the knowledge of the node before the broadcast starts, and (m 1 , m 2 , . . . , m k ) are messages already received by v, where m i came to node v on port p i . Intuitively, the history describes the total knowledge of the node at a given point of the broadcast process. Given a history H at node v, a broadcast scheme S v returns a set of couples

{(m ′ 1 , p ′ 1 ), . . . (m ′ r , p ′ r )}, where 0 ≤ p ′ i < deg(v)
. This means that v should send message m ′ i on port p ′ i , for i ≤ r. At each point of the scheme execution some nodes are informed. Intuitively, these are nodes that already got the source message. In the beginning only the source is informed. A node becomes informed after receiving a message from an informed node (indeed, the source message can be appended to any such message). Broadcast is completed when all nodes of the network are informed. Wakeup algorithms using advice provided by oracles produce wakeup schemes in a similar manner as above: a wakeup scheme for v is a broadcast scheme that does not send any messages (returns the empty set) on all histories with no messages, unless v is the source. Intuitively, nodes other than the source can spontaneously transmit in the broadcast but they cannot in the wakeup. The message complexity of a broadcast or a wakeup scheme is the total number of messages that it produces.

Size of advice for the wakeup

In this section we show that the minimum size of advice permitting the wakeup with a linear number of messages is Θ(n log n). Establishing the upper bound is easy. Fix a network G, and let T be any spanning tree of G. The advice f of oracle O on the network G is defined as follows. For any node v, f (v) is a binary string coding those port numbers at v that lead to its neighbors in T . Since port numbers are integers smaller than n and by using Elias delta coding [START_REF] Elias | Universal Codeword Sets and Representations of the Integers[END_REF], there exists such a string of length at most n(v)⌈log n⌉ + O(log log n), where n(v) is the number of neighbors of v in T . Hence the size of advice is n log n + o(n log n). Given this advice, the wakeup scheme at v tells the node to send messages on all ports coded by f (v). This scheme uses exactly 2(n -1) messages. Thus we have: Theorem 1. There exists advice of size O(n log n) permitting the wakeup with a linear number of messages of networks with at most n nodes.

The main result of this section establishes a matching lower bound on the size of advice for this task.

Theorem 2. The minimum size of advice permitting the wakeup with a linear number of messages of networks with at most n nodes is Ω(n log n).

To prove this theorem, we use an auxiliary problem, called edge discovery, defined as follows. We denote by K * n the n-node complete graph K n whose nodes are labeled from 1 to n, and the port number at node i of the edge leading to node j is labeled (ij) mod (n -1). The instances of the problem edge discovery are triples (n, X, Y ) where n is a positive integer, and X and Y represent two disjoint subsets of edges of K * n . More precisely, the edges represented in X are given distinct labels between 1 and |X|. So formally, X = {(e 1 , ℓ 1 ), . . . , (e |X| , ℓ |X| )}, where ℓ i is the label of e i , and Y is a subset of edges of K * n . The problem consists in designing a communication scheme that, given n, |X|, Y and the set I of possible instances, eventually discovers X, that is eventually sends a message through every edge of X. Whenever an edge e is traversed by a message of the communication scheme, the following information is obtained by the algorithm: if (e, ℓ) ∈ X, then (e, ℓ) is revealed; otherwise it is revealed that (e, ℓ) ∈ X for any label ℓ.

We prove the following lemma that will be used later as a key tool for proving our lower bounds. In the absence of any information about the instances, this lemma could be proved using techniques similar to those in, e.g., [START_REF] Korach | The Optimality of Distributive Constructions of Minimum Weight and Degree Restricted Spanning Trees in a Complete Network of Processors[END_REF] and [START_REF] Korach | Optimal Lower Bounds for Some Distributed Algorithms for a Complete Network of Processors[END_REF]. However, the presence of advice changes the setting radically.

Lemma 1. Let I be a subset of instances of edge discovery, all yielding the same input for the problem (i.e., these instances differ only in the sets X, and all these sets X have the same size). The worst-case message complexity of edge discovery restricted to I is at least log |I| |X|! messages.

Proof. For any given instance (n, X, Y ) of edge discovery, the edges in X are called special. Let us consider any communication scheme S solving edge discovery for all instances in I. Messages traverse edges during the execution of S. At the beginning of the execution of the scheme, all instances in I are called active. When an edge is traversed, the scheme learns whether this edge is special or not. This knowledge enables to discard instances from the set of active instances. For example, if the traversed edge e is not special, then all currently active instances in which e is special can be discarded. Conversely, if the traversed edge e is special, then all currently active instances in which e is not special can be discarded.

We describe an adversary that aims at slowing down the discovery of the special edges by S. We consider the synchronous execution of S. A set J ⊆ I of active instances, after t messages have been sent by S and r special edges have been discovered by S, for some t ≥ 0 and r ≥ 0, is said to be uniform if (1) the t first messages are sent by S through the same edges in all instances in J, and (2) the set of revealed couples (e, ℓ), for special edges e, is the same in all instances of J. If J is uniform, then the scheme S will proceed identically at the next step of its execution in all instances of J. That is, a message is sent through edge e and this edge is the same for all instances in J. The adversary considers uniform sets of active instances, and proceeds as follows. Let J special (resp., J regular ) be the set of instances in a uniform set J, for which e is special (resp., not special). If |J special | ≥ |J regular | then the adversary decides that e is special, else it decides that e is not special. Note that |J special | ≥ 1 2 |J| in the former case, and |J regular | ≥ 1 2 |J| in the latter case. In case e is set to be special by the adversary, the label ℓ(e) remains to be set. The adversary proceeds as follows. Since r special edges have been already discovered, the label of e can take |X|r values. The adversary chooses the label l 0 such that the set J (l0) special of active instances in J special for which ℓ(e) = l 0 , has the largest size. Note that then |J

(l0) special | ≥ |J| 2(|X|-r)
. We say that J regular is the regular subset of J, and J (l0) special is the special subset of J. By construction, J regular , as well as all J (l) special for 1 ≤ l ≤ |X|, are uniform. Hence, we can define recursively the following sequence of sets: I 0,0 = I and        I t+1,r = the regular subset of I t,r , if the (t + 1)th edge is set as not special; I t+1,r+1 = the special subset of I t,r , if the (t + 1)th edge is set as special.

By construction, and depending on which of the cases holds, we have

|I t+1,r | ≥ |I t,r |/2 or |I t+1,r+1 | ≥ |I t,r |/(2(|X| -r)).
For the above defined adversary, let x t,r denote the number of active instances after t messages have been sent in S, and r special edges have been discovered. Thus, x 0,0 = |I| and x t+1,r ≥ x t,r 2 and x t+1,r+1 ≥ x t,r 2(|X|r) .

Therefore, by simple induction on r and t, we get

x t,r ≥ x 0,0 (|X| -r)! 2 t |X|! .
As a consequence, x t,r ≥ x 0,0 /(2 t |X|!) for any r ≤ |X|. When the communication scheme S is completed, only one instance remains active, i.e., x t,r ≤ 1. By the previous inequality, our adversarial scenario guarantees that this cannot occur before t messages have been sent, where

x 0,0 (2 t |X|!) ≤ 1 .
Since x 0,0 = |I|, we conclude that t ≥ log |I| |X|! , which completes the proof of Lemma 1.

Proof of Theorem 2. We first prove that, for any α < 1/2, there exists ǫ > 0 such that, for any integer n greater than some constant, there exists a (2n)-node graph for which no algorithm can perform wakeup with less than ǫ (2n) log(2n) messages, if the size of advice is not more than α (2n) log(2n).

Fix a positive integer n. Recall that K * n is the n-node complete graph with the following labeling. The nodes of K * n are labeled from 1 to n. The port numbers of the edges are fixed as follows: for any 1 ≤ i, j ≤ n, the port number at i of the edge {i, j} is (ij) mod (n -1).

For any n-tuple S = (e 1 , e 2 , . . . , e n ) of distinct edges in K * n , let G n,S be the graph defined from K * n as follows (see Figure 1). For any 1 ≤ i ≤ n, a node w i labeled n + i is inserted in the middle of the edge e i = {u i , v i }. The port number at u i (resp. at v i ), of the edge {u i , w i } (resp. {v i , w i }), is the same as the port number at u i (resp. at v i ), of the former edge {u i , v i }. Assume, without loss of generality, that the label of u i is smaller than the label of v i . Then the port number at w i of the edge {u i , w i }, (resp. {v i , w i }), is 0 (resp. 1). Other port numbers remain unchanged. Let node with label 1 be the source.

This implies

n 2 n ≥ n 2 n n .
Moreover, we have n 2 = n(n-1)

2

≥ n 2 /4. Hence

P ≥ n! n 4 n . (2)
Consider an arbitrary wakeup algorithm using advice provided by an oracle O. Assume that this advice has size at most q = α(2n) log(2n) on all graphs of size 2n, for some α < 1/2. We will prove that there are many graphs G n,S for which the advice is identical.

Let us first compute how many different advice functions f coded on at most q bits can there be for (2n)node graphs. Let v 1 , . . . , v 2n be the list of nodes of such a graph G, in increasing order of their identifiers. Consider an advice function f for G. For any 1 ≤ i ≤ 2n, f (v i ) is the (possibly empty) string given (by the oracle) to the node v i in the graph G. Let s be the concatenation of the strings f (v i ) in increasing order of i. Let q ′ be the size of s. By definition of q, we have q ′ ≤ q. There are 2 q ′ possible different strings s for a given q ′ . Moreover, using standard combinatorial arguments, one can show that there are q ′ +2n-1 2n-1 different ways to partition the q ′ bits of the string s into 2n (possibly empty) substrings f (v i ). To summarize, there are at most 2 q ′ q ′ +2n-1 2n-1 different advice functions of size q ′ for (2n)-node graphs. Since q ′ can be chosen between 0 and q, the number of possible advice functions is exactly

Q = q q ′ =0 2 q ′ q ′ + 2n -1 2n -1 .
Let us compute an upper bound on Q. Since 2 q ′ q ′ +2n-1 2n-1

is increasing as a function of q ′ , it follows that Q is at most (q + 1) 2 q q+2n-1 2n-1

. Note that q+2n-1 2n-1

≤ q+2n

2n because q ≥ 0. Thus we have Q ≤ (q + 1) 2 q q + 2n 2n

Recall that q = α(2n) log(2n). Thus we have q+2n Take β = 1/4 + α/2. We have α < β, and thus for n large enough,

Q ≤ 2 2βn log(n/4) . (5)
There exist at most Q different advice functions for the P different graphs G n,S . Therefore, there exists an advice function f which is the same for a set G of at least P/Q different graphs G n,S . For all these graphs, the wakeup scheme returned by the algorithm is the same.

To any graph G n,S ∈ G we can associate an instance (n, S, ∅) of the edge discovery problem, where the special edges of edge discovery are the subdivided edges of the graph G n,S , and the label of a special edge is the rank of the subdivided edge in S. Let I be the set of instances of edge discovery obtained from all graphs in G. Clearly, I and G have the same cardinality. Performing wakeup in a graph G n,S requires that, for any e ∈ S, at least one message be sent to the node hidden in the edge e. Moreover, this node has an identifier that corresponds to the position of e in S. Therefore, performing wakeup in a graph G n,S requires at least the same number of messages as solving the edge discovery problem on the corresponding instance.

Combining Equations 2 and 5, we get 4) .

P/Q ≥ n! 2 (1-2β)n log(n/
Since |I| ≥ P/Q, the application of Lemma 1 gives a worst-case message complexity of at least

log( n! 2 (1-2β)n log(n/4) n! ) = (1 -2β) n log(n/4) (6)
Since α < 1/2, we have β < 1/2 and thus the above message complexity is greater than ǫ (2n) log(2n) for n large enough, where ǫ is a positive constant not depending on n.

We can now conclude the proof of the theorem. Assume that the theorem does not hold. Then there exists an infinite increasing sequence of integers (n i ) i≥1 , an oracle providing advice of size less than 1 4 n i log n i for the graphs with at most n i nodes, i ≥ 1, and an algorithm A using this advice, such that the algorithm performs wakeup with a linear number of messages in any graph. Fix i ≥ 1. Let m i = n i if n i is even and m i = n i -1 otherwise. For graphs of size at most m i , the advice has size at most 1 4 n i log n i . For i large enough, we have 1 4 n i log n i ≤ 1 3 m i log m i . Applying the previous result with α = 1/3, there exists a positive constant ǫ such that A has a worst-case message complexity of at least ǫ m i log m i on m i -node graphs, for i large enough. Thus the message complexity of A is not linear. This contradiction concludes the proof of the theorem. Remark 1. In the above proof, we obtained a threshold 1/2 for α. Given an arbitrary constant integer c, a threshold c c+1 can be obtained by subdividing cn edges instead of only n edges. Hence, one can show that our upper bound n log n + o(n log n) on the size of advice permitting wakeup with a linear number of messages in graphs with at most n nodes, shown at the beginning of the section, is asymptotically optimal.

Size of advice for the broadcast

In this section we establish almost tight bounds on the minimum size of advice permitting the broadcast with a linear number of messages. In particular, the following upper bound, together with Theorem 2, shows that an efficient wakeup requires strictly more information about the network than an efficient broadcast.

Theorem 3. There exists advice of size O(n) permitting the broadcast with a linear number of messages in networks with at most n nodes.

Proof. We construct an oracle O providing advice and a broadcast algorithm A using it, which returns a broadcast scheme B with linear message complexity. We first describe the oracle O. Let G = (V, E) be any n-node network. Every edge e = {u, v} ∈ E is given the weight w(e) = min{port u (e), port v (e)}.

Let # 2 (w) be the number of bits for encoding a non-negative integer w using standard binary representation, that is # 2 (w) = 1 if w ≤ 1, and # 2 (w) = ⌊log w⌋ + 1 if w > 1. Call the number # 2 (w(e)) the contribution of the edge e. Claim 3.1. There exists a spanning tree T 0 of G, for which e∈E(T0) # 2 (w(e)) ≤ 4n.

We establish the claim by constructing a tree T 0 that yields this contribution. The construction is a variant of Kruskal's minimum-weight spanning tree (MST) algorithm (cf. [START_REF] Cormen | Introduction to Algorithms[END_REF]), similar to the one in [START_REF] Cohen | Labeling Schemes for Tree Representation[END_REF]. It maintains a collection of trees. Initially, each node of G forms a tree on its own. The construction merges these trees into larger trees until it remains with a single tree giving the solution T 0 . More precisely, the construction proceeds in phases. Each phase k ≥ 1 of the construction consists of four steps. At the beginning of the phase, we identify the collection of "small" trees for the phase:

T small (k) = {T : |T | < 2 k },
where |T | denotes the size (number of nodes) of a tree T . Second, for each tree T ∈ T small (k), we look at the set S(T ) of edges that connect T to G \ T , and select an edge e(T ) of minimum weight in S(T ). (Note that S(T ) = ∅ since the graph G is connected.) Third, we add these edges to the collection of trees, thus merging the trees into subgraphs. Each subgraph may contain a cycle, thus, finally, for the last of the four steps, in each subgraph we arbitrarily select one of the edges on the cycle and erase it, effectively transforming the subgraph back into a tree. This process is continued until a single tree remains, which is the desired tree T 0 .

To prove the claim, let us denote the collection of trees at the beginning of the kth phase, k ≥ 1, by

T (k) 1 , . . . , T (k) q k ,
where q k is the number of trees maintained in phase k. We have q 1 = n, and

|T (1) i | = 1 for any 1 ≤ i ≤ n. Moreover, q k i=1 |T (k) i | = n for every k ≥ 1. By induction, we easily get that |T (k) i | ≥ 2 k-1
for every k ≥ 1 and 1 ≤ i ≤ q k . Thus q k ≤ n/2 k-1 for every k ≥ 1. In particular, the number of phases of the construction is at most ⌈log n⌉.

Assume that, when considering a small tree T i . Hence even if all of these edges are "lighter" than the edges leading outside the tree, the port number used for e(T

(k) i ) is at most |T (k) i | -1, hence w(e(T (k) i )) ≤ |T (k) i | -1. Therefore # 2 (w(e(T (k) i ))) = 1 if k = 1 # 2 (w(e(T (k) i ))) ≤ ⌊log(|T (k) i | -1)⌋ + 1 if k > 1 For T (k) i ∈ T small (k), we have log |T (k) i | < k.
Since outgoing edges are selected only for small trees, we have

# 2 w e T (k) i ≤ k .
Hence the total contribution C k of the edges added to the structure throughout the kth phase satisfies

C k ≤ k |T small (k)| ≤ k q k ≤ k n/2 k-1 .
Therefore, the total contribution k≥1 C k of all edges of the resulting tree T 0 satisfies k≥1

C k ≤ k≥1 kn/2 k-1 ≤ 4n .
This completes the proof of Claim 3.1.

We now describe the advice function provided by oracle O. For every edge e = {u, v} ∈ E(T 0 ), it assigns the binary representation of w(e) to the extremity x ∈ {u, v} such that w(e) = port x (e), where ties are broken arbitrarily. The same node may receive binary representations of several weights w(e 1 ), . . . , w(e t ), in which case they can be encoded using Elias gamma coding [START_REF] Elias | Universal Codeword Sets and Representations of the Integers[END_REF] by one binary string of length 2 t i=1 # 2 (w(e i )). In view of Claim 3.1, the size of the advice is at most 8n.

Based on the strings assigned to the nodes of G, Algorithm A constructs the broadcast scheme B defined in Figure 2. The general idea behind this broadcast scheme is that each node transmits a "hello" message through its incident edges that are designated by the advice. As a consequence, each node eventually knows which of its incident edges belong to the spanning tree T 0 . The source message can thus be efficiently disseminated through this spanning tree. We establish the first part of the claim by combining the following properties. Clearly, the source message M as well as the "hello" messages are sent only through the n -1 edges of T 0 . The message M does not traverse an edge more than once because M is sent by x only through edges of K x \ S x , where S x is the set of edges through which either M has been sent by x before, or M has been received by x. A "hello" message traverses an edge e of T 0 in one direction only because only one extremity x of e is given the port number port x (e) in the advice.

The second part of the claim is established by induction on the distance d of a node from the source, in the tree T 0 . Let P (d) be the property "all nodes at distance ≤ d from the source in T 0 eventually receive the message M ". P (0) clearly holds. Assume P (d) holds for d ≥ 0, and consider a node x at distance d + 1 from the source in T 0 . Node x is a neighbor in T 0 of a node y at distance d from the source in T 0 . The edge e = {x, y} is eventually discovered by y because, by definition of the advice, either y is given port y (e), or x is given port x (e), and, in the latter case, x will eventually send a message "hello" to y, enabling e to be known by y. By the induction hypothesis, y will eventually receive the message M . Therefore the message will eventually be sent through e by y. Therefore P (d + 1) holds too, and hence B achieves broadcast. Theorem 4. Any broadcast algorithm using advice of size o(n) in networks with at most n nodes, cannot return a broadcast scheme of linear message complexity.

Proof. The proof uses a similar construction as for proving Theorem 2, but requires novel ideas, since the nodes can now transmit spontaneously. Recall that K * n denotes the n-node complete graph K n whose vertices are labeled from 1 to n, and the port number at node i of the edge leading to node j is labeled (ij) mod (n -1). For any k and n such that 4k divides n, and for any (n/k)-tuple S = (e 1 , . . . , e n/k ) of distinct edges of K * n , let us consider the graphs obtained from K * n by replacing edge e i by a clique H i of size k, for i = 1, . . . , n/k. More precisely, one edge {a i , b i } of the clique H i replacing e i is removed from H i , and a i is connected to one extremity of e i in K * n , while b i is connected to the other extremity of e i in K * n . Nodes of H i are labeled from n + (i -1)k + 1 to n + ik, for i = 1, . . . , n/k. The port number at node n + (i -1)k + a of the edge leading to node n + (i -1)k + b is labeled (ab) mod (k -1). By abuse of notation, the edge {n + (i -1)k + a, n + (i -1)k + b} is called the edge {a, b} of H i . The set S does not fully specify the graph resulting from the above transformation because edges {a Any C ∈ C (together with the set S) fully characterizes the graph as follows. For any edge e i in S, i = 1, . . . , n/k, let e i = {u i , v i }, where id(u i ) < id(v i ). The edge e i of K * n and the edge f = {a i , b i } of H i are replaced by the edges {a i , u i } and {b i , v i }. The port number at u i (resp., v i ) of the edge {a i , u i } (resp., {b i , v i }) is the same as the port number at u i (resp., v i ) of the edge e i . Similarly, the port number at a i (resp., b i ) of the edge {a i , u i } (resp., {b i , v i }) is the same as the port number at a i (resp., b i ) of the edge f i . The resulting graph is denoted by G n,S,C . The construction is illustrated in Figure 3. (For clarity purposes, 4k does not divide n in this example.) Let the node with label 1 be the source. For any pair of positive integers (n, k) such that 4k divides n, the family of graphs defined as above is denoted by G n,k . In other words, we have

G n,k = {G n,S,C | S is a (n/k)-tuple of edges of K * n , C ∈ C } .
Note that, by construction, every graph in G n,k has 2n nodes, and in each such graph, all nodes with labels larger than n (i.e., those in the added cliques) have degree k -1.

a)

b)

e' e source 1 To establish the claim, let us assume, for the purpose of contradiction, that there exists a broadcast algorithm A using advice of size at most n 2k , for all graphs in G n,k , which produces a broadcast scheme of message complexity less than n(k -1)/8. Let σ i be the sum of numbers of bits given in this advice to the nodes of H i . Since Σ n/k i=1 σ i ≤ n 2k , we conclude that at least half of the cliques do not receive any bit of information. On the other hand, if

A(∅, 0, n + (i -1)k + a, k -1)
is not defined for some pair (i, a), where 1 ≤ i ≤ n/k and 1 ≤ a ≤ k, then at least one node of H i requires some advice to specify its broadcast scheme, and thus the clique H i must receive at least one bit of information. Such an index i is called heavy. Let i ∈ {1, . . . , n/k} be a non heavy index (i.e., i is such that A(∅, 0, n + (i -1)k + a, k -1) is defined for all a = 1, . . . , k), and let us observe the behavior of the communication scheme produced by A in the clique H i , when the advice function gives no information to the nodes of H i . If in the synchronous execution of the scheme, all edges of H i are eventually traversed by at least one message, then i is called internal. Otherwise, i.e., if the communication scheme leaves at least one edge of H i not traversed by any message in the synchronous execution of the scheme, then i is called external. External indices result from the fact that the scheme exchanges messages but lets always one edge free of message, or result from the fact that the execution of the scheme reaches a point at which the action of a node is not defined (the history of the execution cannot be produced by the broadcast scheme returned by A).

For every internal index i, let us consider the synchronous execution of the scheme, and let f i = {a i , b i } be an edge of H i that is traversed last. For every external index i, let us again consider the synchronous execution of the scheme, and let f i be any edge of H i that is not traversed by any message. Finally, for every heavy index i, let f i be any edge of H i . This setting of the f i 's defines one (n/k)-tuple from C, denoted by C * . We will now restrict attention to those graphs in G n,k , for which S takes all possible values of (n/k)-tuples of edges of K * n , but C = C * . Fix S and consider G n,S,C * . As observed before, at least half of the cliques in G n,S,C * receive no bits of advice. Let I be the corresponding set of indices. We have |I| ≥ n/(2k). Indices in I are either internal or external because cliques with heavy indices must receive at least one bit of advice. Hence I can be decomposed into two sets I int and I ext that are subsets of internal and external indices, respectively, and such that I = I int ∪ I ext . For all cliques H i with i ∈ I ext , the setting of the f i 's implies that the broadcast scheme generated by A has the property that, in its synchronous execution, no message goes out of H i before a message goes into H i from the rest of the graph. Among all cliques H i with i ∈ I int , some may have the property that, in the synchronous execution of the broadcast scheme, a message goes out of H i before any message goes into H i from the rest of the graph. Let I + int be the indices from I int , for which this phenomenon occurs. By the setting of the f i 's, for every i ∈ I + int , the message complexity of the broadcast scheme restricted to H i is at least k(k -1)/2 since f i is one of the edges traversed last. Therefore, since the broadcast scheme generated by A has message complexity less than n(k -1)/8, we get that

|I + int | < n 4k . Thus, |I \ I + int | ≥ n 4k .
This inequality implies that the number of cliques H i such that, in the synchronous execution of the broadcast scheme, no message goes out of H i before a message goes into H i from the rest of the graph, is at least n 4k . In other words, at least n 4k cliques have to be discovered from the outside, and at most 3n 4k can reveal themselves spontaneously to the rest of the graph. Therefore, the broadcast problem in G n,S,C * is at least as hard as the auxiliary problem edge discovery with instances

where the first inequality follows from Equation 1. On the other hand, let Q be the number of possible advice functions of size at most q for the graphs of G n,k . By the same calculations as for deriving Equation 3, we get Q ≤ (q + 1)2 q 2n + q q .

It follows from Equation 4 that 2n + n for n and k large enough. Since n 2k + 1 < n k , we get

Q ≤ n k 2 n 2k (24k) n 2k , if q ≤ n 2k .
Therefore, for n and k large enough,

Q ≤ (50k) n 2k . (8)
There exists a set of graphs of size at least P/Q for which the advice is the same. Combining Equations 7 and 8, we conclude that there exists a set of graphs of size at least

|X|! n 5000 k n 4k
for which the advice is the same. Applying Lemma 1 to this set of graphs, we get that the number of exchanged messages is at least n 4k log( n 5000 k ). For k ≤ √ log n, and for n and k large enough, this number is at least n(k -1)/8, a contradiction with the hypothesis that A produces a broadcast scheme of message complexity less than n(k -1)/8. This completes the proof of Claim 3.3.

To complete the proof of the theorem, let us consider a broadcast algorithm A using advice of size f (n) in networks of at most n nodes, where f (n) is in o(n). Let f be the function defined by f (n) = max{f (n), n √ log n }. Hence A uses advice of size at most f (n) in networks of at most n nodes. For any n ≥ 1, let k(n) = n/ f (n), and let k ′ (n) = ⌊ k(n) 4 ⌋. Let n ′ be the largest integer smaller or equal to n and divisible by 4k ′ (n). Note that, since n/k ′ (n) grows to infinity, we have n ′ ≥ n/2, for n large enough. The advice has size at most f (n) in networks with at most n ′ nodes. We have

f (n) = n k(n) ≤ 2n ′ k(n) ≤ n ′ 2 k ′ (n) .
Therefore, the size of advice is at most n ′ 2 k ′ (n) in networks with at most n ′ nodes. By the construction of f , we get k ′ (n) ≤ √ log n ′ . Hence Claim 3.3 applies, and we conclude that the broadcast scheme returned by A on graphs with at most n ′ nodes has message complexity at least n ′ (k ′ (n) -1)/8, which is not in O(n ′ ). Therefore, any broadcast algorithm A using advice of size f (n) in networks with at most n nodes, where f (n) is in o(n), returns a broadcast scheme that does not have a linear message complexity.

Conclusion

We investigated the concept of advice: a new way of modeling knowledge that nodes have about the network. We showed that the minimum size of advice for which a task can be accomplished efficiently, can serve as a measure of difficulty of this task, and can be used to quantitatively differentiate the difficulty of related tasks. In this paper we concentrated on two similar communication tasks, broadcast and wakeup with a linear number of messages, and used the size of advice to strictly separate their difficulty. However, we conjecture that the minimum size of advice can be also used to assess difficulty of a broader range of distributed network problems, not only concerning information dissemination but also, e.g., spanner construction or graph coloring. Moreover, the size of advice could be potentially used to establish precise tradeoffs between the amount of knowledge available to nodes of a network and the efficiency (in terms of time or message complexity) of accomplishing a given task.

Figure 1 : a) the graph K * 5 b

 15 Figure 1: a) the graph K * 5

.For n large enough, we have e 1 +

 1 b ≤ a, we get 2n(1 + α log(2n)) 2n ≤ e 1 + α log(2n) 2n α log(2n) 2n ≤ 6α log(2n) 2n and thus Q ≤ α (2n) log(2n) + 1 • 2 α (2n) log(2n) • 6α log(2n) 2n .

  in the kth phase, the edge e(T (k) i ) incident to some node x of T (k) i was selected. The only edges incident to node x excluded from consideration are the at most |T (k) i | -1 edges leading from x to the other nodes in T (k)

Figure 2 :

 2 Figure 2: Broadcast Scheme B

  i , b i } are not yet specified. Let C = (a 1 , b 1 ), . . . , (a n/k , b n/k ) | (a i , b i ) ∈ {1, . . . , k} 2 , a i < b i , i = 1, . . . , n/k .

Figure 3 :

 3 Figure 3: a) the graph K * 5

  (n, X, Y ) satisfying |X| = n 4k and |Y | = 3n 4k . For n, |X|, and Y fixed, there are |X|! n 2 -|Y | |X| different instances of edge discovery. Hence, for |X| = n 4k and |Y | = 3n 4k , the number of different instances P = |X|! P ′ satisfies

  /* Broadcast Scheme B executed by node x. M is the source message. */ begin Kx ← list of port numbers given to x in the advice; /* Kx = incident edges known by x */ Hx ← Kx; /* Hx = incident edges through which "hello" messages may be sent */ Sx ← ∅; /* Sx = incident edges through which the message M has been transmitted */ repeat if x receives the message M via port p then Kx ← Kx ∪ {p}; Sx ← Sx ∪ {p}; if x receives the message M then send message M on all ports of Kx \ Sx;

	Sx ← Kx;
	Hx ← Hx \ Sx;
	if Hx = ∅ then
	send "hello" messages on all ports of Hx;
	Hx ← ∅;
	if x receives a "hello" message via port p / ∈ Kx then
	Kx ← Kx ∪ {p};
	endrepeat
	end

 [START_REF] Abiteboul | Compact labeling schemes for ancestor queries[END_REF]This work was done while Pierre Fraigniaud and David Ilcinkas were with the University Paris-Sud (LRI). They were both supported by the projects "PairAPair" of the ACI Masses de Données, and "FRAGILE" of the ACI Sécurité Informatique. Additional support was from the INRIA project "Grand Large".

2 Andrzej Pelc was supported in part by NSERC discovery grant and by the Research Chair in Distributed Computing of the Université du Québec en Outaouais. This work was done during the visit of Andrzej Pelc at LRI. Additional support was from the Ministère des Relations Internationales du Québec, from the University Paris-Sud, and from the project "PairAPair" of the ACI Masses de Données.


Arsene Arlette Simo Fotso

Kra Kouassi

Marie-Claude Boily

Romain Silhol

Anthony Vautier

Joseph Larmarange

Arlette Simo

Knowledge, attitude and practices towards HIV testing following the introduction of self-testing: The case of the ATLAS project in Côte d'Ivoire

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Outcomes

• Being exposed to Shuga-Babi was associated with a higher odds of Knowing about HIVST and the odds was even higher for those exposed to Shuga-Babi campaign who lived in ATLAS implementation strata arlette.simo-fotso@ined.fr

•

Background

Method

Results

Conclusion

• HIV testing is a central element of the strategy to end AIDS epidemic, as status awareness is the entry point to HIV prevention and care.

• In Côte d'Ivoire, only 85% of people living with HIV (PLHIV) were aware of their HIV status in 2021 (UNAIDS, 2023).

• To address this gap, the ATLAS project distributed a total of ~200000 kits self-tests (HIVST) in Côte d'Ivoire between 2019 and 2022, including ~75000

in Bas-Sassandra region, targeting key populations aged 16+ and their network.

• Concurrently, a multi-media campaign Shuga-Babi, promoting testing and • A total of 6271 people were interviewed (3203 males and 3068 females).

• 11% of participants reported having heard about HIVST

• Most participants showed a positive attitude toward HIVST and reported that they would be interested/very interested to use it if freely available

• About 14% reported having performed at least 1 conventional test or HIVST in the last 12 months

• While 3% of participants had already used a HIVST in the past.

• ATLAS program combined with Shuga-babi intervention was strongly and significantly associated with HIVST use

• Residence in ATLAS implementation strata alone was not significantly associated with KAP towards HIV testing and self-testing

• The weak association between ATLAS intervention and those outcomes could be explained by the fact that:

⚬ ATLAS targeted key populations and vulnerable groups which represent a small proportion of the population interviewed ⚬ ATLAS intervention was indirectly captured through the residence in an ATLAS strata

• These hypotheses need to be further investigated in upcoming analysis

  Living in ATLAS implementation strata and exposure to Shuga-Babi alone was not significantly associated with the use of HIVST, but being exposed to both interventions was positively associated with previous use of HIVST • Interest to use HIVST for self was not associated with interventions • Interest to use for sexual partners was associated with exposition to Shuga-Babi campaign • HIV-Testing in the last 12 months was positively associated with exposition to Shuga-Babi campaign but was not associated to living in ATLAS implementation strata alone. Knowledge, attitude and practices towards HIV testing following the introduction of self-testing: The case of the ATLAS project in Côte d'Ivoire Arlette Simo Fotso 1, 2 , Arsène Kouassi Kra 2 , Marie Claude Boily 3 , Romain Silhol 3 , Anthony Vautier 4 , Joseph Larmarange 1, 2 1 Institut National d'Études Démographiques (Ined) ; 2 Centre Population et Développement (Ceped), Université Paris Cité, Institut de Recherche pour le Développement (IRD), Inserm, France; 3 MRC Centre for Global Infectious Disease Analysis, School of Public Health, Imperial College London; 4 Solidarité Thérapeutique et Initiatives pour la Santé (Solthis), Sénégal

•

  HIVST, was launched by MTV foundation targeting mainly population aged 15-24 The aim of this study is to assess levels and correlates of knowledge, attitude and practice (KAP) towards HIV testing and self-testing in general population after the introduction of HIVST in Bas-Sassandra, Côte d'Ivoire. • We conducted a population-based cross-sectional survey of the population aged 15-49 years in the Bas-Sassandra region of Côte d'Ivoire, in December 2021 • Survey: 24 months after HIVST was introduced in the region by ATLAS and 6 months after Shuga-Babi campaign • Weighed proportions were used to assess level of KAP toward HIV testing, • Logistic regressions were used to identified factors associated to KAP toward HIV testing • The survey used a three-stage stratified sampling approach with 8 strata: ⚬ 3 of the strata are the 3 departments where ATLAS was implemented ⚬ 1 strata includes departments with almost no ATLAS activities ⚬ each further stratified on urban and rural settings

Figure 1 :

 1 Figure 1 : Logistic regression of knowledge, attitude and practice (KAP) towards HIV testing

Table 1 :

 1 Level of knowledge, attitude and practice (KAP) towards HIV testing


Patrick Chamoiseau

When everything is darkness around you, literally and figuratively, it is that it is oneself who becomes the light to discover, the instance to work on, to extend."

The night has long remained a forgotten dimension, a "terra incognita" little researched, as if left to fantasies and representations. Between insecurity and freedom, it still fascinates. Coloured by light and economic activities, it has recently become a key area of tension between individuals, groups and neighbourhoods of our cities that no longer live at the same pace.

For the last twenty years, night has become part of the daytime news: holiday lightings, sleepless nights, but also light pollution, urban violence or noise pollution. We are progressively witnessing a trivialization of the night and of the night-time offer where the consumer component has become central in a context of territorial marketing and competition between cities. The public authorities, who have always sought to control it, are now interested in this fleeting and cyclical territory. In Europe, initiatives are proliferating in three main directions: improving the quality of life for residents through new services and the expansion of daytime activities, nightlife as part of territorial marketing and attractivity, and public tranquility or security. Better "councils" and "mayors of the night" have been set up in Geneva, London, Paris, New York, but also in small towns like Quimper or La Rochelle where specific public policies are being developed. The health crisis with the confinement and the return of the curfew in some countries 1. Rare. [In an antiquated style] Spend the night. Every evening, these animals [jackdaws] fled the cathedral and only returned the next day, at dawn, after having overnighted in a forest three leagues from Chartres (Huysmans, Cathédr.,1898, p. 408). www.cnrtl.fr/definition/pernocter has highlighted the importance of the night as a moment of silence but also of socializing. The energy crisis and climate change force us to think in terms of light moderation, and even to imagine a shift in summer activity towards the evening and night when conditions are more manageable. The night is now of interest to politicians, community professionals, the general public and also for human and social science research.

An emerging interdisciplinary field. The economy of the night, public policies, questions of mobility, insecurity, and light pollution are now explored by different disciplines from the angle of new geographies, but also from social, cultural, biological, ecological, political, and media viewpoints. For some years now, the field of night studies (Gwiadzinski, Maggioli and Straw 2020) has been gradually structured around an interdisciplinary approach to nocturnal spacetime. Within this framework, and even if ethnographic methods and materials are often used in these various disciplines, ethnography, a diurnal science that has prioritized sight [START_REF] Diamanti | Sensing the Night: Nocturnal Filmmaking in Guantánamo, Cuba[END_REF], has paid little attention to the night. In anthropology, the night also remained for a long time in the shadow of the day before a few researchers really took an interest in it (Becquelin and Galiner 2020;[START_REF] Diamanti | Sensing the Night: Nocturnal Filmmaking in Guantánamo, Cuba[END_REF]Galinier et al. 2010;Gonlin and Nowell 2018;[START_REF] Schnepel | Introduction: 'When Darkness Come': Steps toward an Anthropology of the Night[END_REF].

A distinct imaginary. The concept of night is not an obvious one. Our Western societies are still very marked by the imaginary -for which a clear definition remains difficult to produce (Wunenburger 2006) -of the progress which would lead towards the light. The "dawn of time" is a very remote period of which we know nothing. The age of "enlightenment" has largely exploited the metaphor (Gwiazdzinski 2005). In this sense, all research is opposed to the night since "we legitimately ask thought to dispel the fogs and obscurities" [START_REF] Edgar | Introduction à la pensée complexe[END_REF]. Discovery is done in terms of clarification: we like to "chase away the darkness,» "shed light,» " clarify the situation " or make readable what was hidden. The researcher who tries to bring light to the night, to record its limits, forms, environments and uses, ends up objectifying it, putting it into equations (Deleuil 1993), at the risk of undoubtedly contributing to the destruction of the object of the research, its very essence. It is all the ambiguity of the night -"being able to be white and black at the same time" according to the cruciverbalists -and of the research.

The need for other approaches. The night is certainly one of the domains where the trio "knowledge, ignorance, mystery" is best revealed, inviting a "nocturnal thought" (Gwiazdzinski 2020) that allows for nuances. The night is also an interesting place for learning other modes of research and thinking, and even a space-time for innovation (Gwiazdzinski 2005). It is not only a space-time on hold subject to the conquest of the day, a simple extension of the day, its negative counterpart, nor a day in reverse (Galinier et al. 2010). It is a particular space-time with its own environments, practices, uses, and representations that cannot be addressed with the same methods and analytical materials as in daylight. Beyond statistics, it is also towards immersion in the night, the mobilization of senses other than sight that research can be directed. One can also take an interest in the "imaginary" -which in psychoanalytical terminology, sometimes indicates "the recording of images, of projection, of identifications and, in a way, of illusion" -and which, in the Pascalian sense, is in opposition to reason -and in the sensory and aesthetic dimensions, that is to say, the a priori forms of perceptible knowledge: space for the external world and time for the internal world of the awareness.

An anticipation and ambitions. One could expect a lot from ethnography defined as "the descriptive and analytical study, in the field, of the manners, customs of given populations," 2 and from the "ethnographic method" [START_REF] Dufour Stéphane | L'enquête de terrain en sciences sociales. L'approche monographique et les méthodes qualitatives[END_REF] qualitative methodology, requiring the work in situ, the direct observation, even the participation of the researcher. The two editors invite us to this exploration of the night from its aesthetic, imaginary and sensory components, in the sense of the "aesthetically reimagined night" [START_REF] Bronfen | Night Passages : Philosophy, Literature, and Film[END_REF]) with reference to the imaginaries of the night enriched by writers, poets and filmmakers [START_REF] Diamanti | Sensing the Night: Nocturnal Filmmaking in Guantánamo, Cuba[END_REF]. This issue of Ethnologies aims to "foster debate by bringing together interdisciplinary articles on ethnographic studies that focus on the night from an imaginary and aesthetic point of view." The editors wish to "map nocturnal ethnographies and understand what impacts night has on the work of researchers and what kinds of tools and techniques are proposed to study the space-time that follows nightfall." They have succeeded in bringing together various disciplines and contributions by researchers from different backgrounds conducting ethnographic research on the night: from anthropology and ethnology to sociology and media studies to geography around a few questions. How do ethnographers conduct their research at night and on the night? Are there any special features of the 24-hour cycle that begins at dusk? All these questions allow us to sketch a composite landscape of the night, its inhabitants and patrons of yesterday and today, but also its explorers and their methods and materials, their different ways of spending the night.

www.cnrtl.fr/definition/ethnographie

A first mapping. This first international survey of "nocturnal ethnographies" -naturally impressionistic and incomplete -explores practices, temporalities and territories that have been little explored until now, such as "sung lullabies" (Levesque), "virtual dance" (Krisel) the "specters" linked to the marine zones of scattering of ashes and web platforms hosting the dead in the etheric world in Hong Kong (Lecuyer), the twilights of Scandinavia (Pardue) or the hospital corridor (Davies), an intermediary and ambiguous place with no specific activities, rules of conduct or dress codes. The nocturnal ethnography undertaken by the two editors in Cuba explores the island's night. The associated film -Guardians of the Night -Guardianes de la noche (2018) -shows the nocturnal daily lives of the guardians of the night on construction sites, in train stations, in bars, on buses, on bicycles, in the dimly lit streets of a drowsy, as if frozen, nocturnal Cuba. The slumped and tired bodies on the benches, the sidewalks, as if crumbled, contrast with that of a young dancer who works on her flexibility. The precise gestures of the baker who is busy. The general calm contrasts with some oasis of music. Everywhere the pale lights and the outdated atmospheres of a world in virtual standstill that is preparing to face the day, nibbling and gaining strength. Guards like ghosts, an almost fixed camera, a light musical background for a soft night dive. An aesthetic of slowness and of daily slowing down.

A range of ethnographic methods. The array of methods presented does indeed include a great deal of immersion "in the field," of firsthand observation, and even of the researcher's own participation and auto-ethnography, as Nick Dunn did, in order to develop broader and deeper knowledge of a located, relational, and practiced nature of the city after daylight. They also employ auto-ethnographic but also artistic approaches to listening and the body in the study of sung lullabies (Levesque). The spectral methodology used by Marie Lecuyer involves a multimedia and infra-linguistic ethnography of unconventional cemeteries. The panorama goes beyond contemporary nights with a historical approach based on the utilization of little-used materials, such as the specialized press of the thirties (Straw) or the analysis of philosophical and medical works such as Jayson Althofer's interest in the night work of children in the 19th century and nocturnal experiments on worthless bodies. For Chantal Meng the practice of night drawing becomes an active move to study and re-examine the night in a different way. Joshua Dittrich uses ethnography to examine the nocturnal practices of users of "so(m)niferous media." Based on classic surveys of young people in Montreal, a group of researchers (Cossette, Moriceau, Braa, Couvy, Oder, Boucher and Amiraux) succeed in bringing to the fore a third dimension of the night in which the people interviewed attempt to live ordinary nocturnal activities, focused on the search for intimacy and tranquility.

Positions of progress and projections. Beyond the mere methodological advances and documentation of a phenomenon, the authors question the social consequences, take a stand and even commit themselves and predict: questioning what the advent of virtual dance parties may mean for the future of urban nightlife (Krisel), reflecting on and discussing our experience of and relationship to light (Meng), exploring the entanglements between light and dark, work and rest, creativity and place, and denouncing the consumer society that inserts itself even into sleep (Dittrich), imagining the implications of the study of sonic lullabies for music and peacebuilding research. Still others are looking for follow-ups and applications to their discoveries. Lauren Levesque looks ahead and believes that her work could contribute to interdisciplinary conversations about self-examination and performance as ethnographic access points to peace imaginaries in night studies. Nick Dunn, who is interested in those who inhabit the urban night through their work, engage with its aesthetics, and develop knowledge about these specific geographies, questions how multisensory experiences and the aesthetics of nocturnal places allow for a re-imagining of what these environments might be.

Beyond these first nocturnal ethnographies, these contributions allow us to discover and explore various ways of spending the night for both the reader and the researcher. They allow us to understand, without completely lifting the veil, the mysteries of this fascinating space-time and the practices of its inhabitants. Exploring urban nights also means learning to manage the contradictions and paradoxes of a super-modern society and its actors: illuminating the night without killing it.


Michel Volle
email: michel.volle@univ-avignon.fr

Jean-Baptiste Hiriart-Urruty

A characterization of essentially strictly convex functions on reflexive Banach spaces

Keywords: Reflexive Banach space, weakly lower-semicontinuous function, essentially smooth function, essentially strictly convex function, closed convex relaxation, Asplund function, proximal set-valued mapping

We call a function J : X → R ∪ {+∞} "adequate" whenever its tilted version by a continuous linear form x → J(x) -x * , x has a unique (global) minimizer on X, for appropriate x * ∈ X * . In this note we show that this induces the essentially strict convexity of J. The proof passes through the differentiability property of the Legendre-Fenchel conjugate J * of J, and the relationship between the essentially strict convexity of J and the Gâteaux-differentiability of J * . It also involves a recent result from the area of the (closed convex) relaxation of variational problems. As a by-product of the main result derived, we express the subdifferential of the (generalized) Asplund function associated with a couple of functions (f, h) with f ∈ Γ(X) cofinite and h : X → R ∪ {+∞} weakly lower-semicontinuous. We do this in terms of (generalized) proximal set-valued mappings defined via (g, h). The theory is applied to Bregman-Tchebychev sets and functions for which some new results are established.

Introduction to the context of the work

Let us consider an extended real-valued (not necessarily convex) function J : X → R ∪ {+∞}, not identically equal to +∞ (such a function is called proper), defined on a reflexive Banach space (X, . ). We denote by (X * , . * ) the topological dual space of X endowed with the dual norm . * of . , and by Γ(X) (resp. Γ(X * )) the set of convex lower-semicontinuous proper functions on X (resp. X * ). All the notations we are going to use are usual in the context of Functional convex analysis, Set-valued and variational analysis. For example, by ∂J : X ⇒ X * we mean the subdifferential (set-valued) mapping of J. Actually, that is the inverse set-valued mapping of ∂J which will be of interest to us, namely M J := (∂J) -1 : X * ⇒ X

x * → M J(x * ) = {x ∈ X|x * ∈ ∂J(x)}.

(1)

To be a bit more explicit, given a continuous linear form x * on X, M J(x * ) is the set of (global) minimizers of the function x ∈ X → J(x) -x * , x , the tilted version of J. As a general rule, we have M J(x * ) ⊂ ∂J * (x * ), hence coM J(x * ) ⊂ ∂J * (x * )

(2) for all x * ∈ X * , where J * stands for the Legendre-Fenchel conjugate of J. Since the underlying space X has been assumed to be reflexive, we know (see [As, Theorem 2] for example) that J * is Gâteaux-differentiable on a dense G δ -subset of int(dom J * ). Furthermore, the inclusion ( 2) is made meaningful when J is weakly lower-semicontinuous on X, as shown in the next statement.

Proposition 1. Suppose J is weakly lower-semicontinuous on a reflexive Banach space X. Then M J(x * ) is nonempty for all x * ∈ int(dom J * ). In other words,

∅ = coM J(x * ) ⊂ ∂J * (x * ) for all x * ∈ int(dom J * ). (3)
Proof. The only point we have to prove is that M J(x * ) is nonempty whenever x * is taken in int(dom J * ).

Due to the fact that x * has been chosen in the interior of dom J * , the function J * is finite and continuous at x * . Therefore, there is a neighborhood of x * on which J * is bounded from above. Said otherwise, there is α > 0 and r ∈ R such that

J * ≤ i B * (x * ,α) + r. (4)
Here, i B * (x * ,α) denotes the indicator function of the closed ball (for the norm . * ) centered at x * and of radius α > 0.

By taking the Legendre-Fenchel conjugates in both sides of (4), we get at the following inequality:

J ≥ J * * ≥ x * , . + α . -r.
It then follows that the tilted function J -x * , . is 0-coercive on X (i.e., it goes to +∞ when x → +∞). As a result, J -x * , . is bounded from below and achieves its lower bound. We just have proved that M J(x * ) is nonempty. ¿From what was said about the Gâteaux-differentiability of J * and the Proposition just above, we immediately derive: Proposition 2. Let J (and X) be as in Proposition 1. Then the set-valued mapping M J is single-valued (M J(x * ) = {m J (x * )}) on a G δ -dense subset of int(dom J * ).

"Adequate" vs essentially strictly convex functions

In order to reinforce the property of M J laid out in Proposition 2, we introduce hereafter a definition.

Definition. A proper extended real-valued function J : X → R ∪ {+∞} is said to be "adequate" if dom M J = dom (∂J * ) is a nonempty open set ;

M J is single-valued on its domain.

Remembering the explanation of M J(x * ) in Section 1, the definition above expresses that the tilted version of J, namely J -x * , . , has a unique (global) minimizer on X. Such a definition of "adequate" functions is related, although we do not assume a priori any convexity property of J, with the following concepts, introduced in [BBC], that extend to the infinite dimensional setting those similar given in [START_REF] Rockafellar | Convex analysis[END_REF]Section 26]. Let us recall these specific definitions:

• A function Φ ∈ Γ(X *
) is said to be essentially smooth if the subdifferential set-valued mapping ∂Φ is both single-valued and locally bounded on its domain.

• A function J ∈ Γ(X) is said to be essentially strictly convex if J is strictly convex on every convex subset of dom(∂J) and M J = (∂J) -1 is locally bounded on its domain.

In the definitions above, a locally bounded set-valued mapping x → Γ(x) means that some neighborhood V of x has a bounded image Γ(V ).

¿From [START_REF] Bauschke | Essential smoothness, essential strict convexity, and Legendre functions in Banach spaces[END_REF]Theorem 5.4], we know that J ∈ Γ(X) is essentially strictly convex if and only if J * is essentially smooth. A function J ∈ Γ(X) which is both essentially strictly convex and essentially smooth is called a Legendre function.

Let us now provide a standard example of what an "adequate" function is. Proposition 3. A weakly lower-semicontinuous function J : X → R ∪ {+∞} for which J * is essentially smooth is necessarily "adequate".

Proof. By Proposition 1 we have int(domJ * ) ⊂ domM J. Since J * is essentially smooth, one has int(domJ * ) = dom∂J * , so dom∂J * ⊂ domM J. Conversely, it comes from (2) that domM J ⊂ dom∂J * , and finally domM J = dom∂J * = int(domJ * ). Since ∂J * is single-valued on its domain, Proposition 1 says that M J is single-valued on int(domJ * ) and J is therefore "adequate".

In particular, any weakly lower-semicontinuous function J : X → R ∪ {+∞} whose conjugate J * is Gâteaux-differentiable on X * is "adequate".

In the sequel we will need Theorem A below that completes an earlier result by Soloviov [START_REF] Soloviov | Dual extremal problems and their applications to problems of minimax estimation[END_REF]Theorem 1.2.1] (see also [START_REF] Zȃlinescu | Convex analysis in general vector spaces[END_REF]Theorem 9.3.2]). Its proof easily follows from [START_REF] Bauschke | Essential smoothness, essential strict convexity, and Legendre functions in Banach spaces[END_REF]Theorems 5.4 and 5.6] and the above considerations.

Theorem A. A weakly lower-semicontinuous function J : X → R ∪ {+∞} on a reflexive Banach space X is essentially strictly convex if and only if J * is essentially smooth.

Our main result (the forthcoming Theorem 1) also relies on the next theorem whose main applications are in the relaxation of variational problems. It just says that the inclusion (3) in Proposition 1 is in fact an equality.

Theorem B. Let J : X → R ∪ {+∞} be a weakly lower-semicontinuous function on a reflexive Banach space. Then:

∂J * (x * ) = coM J(x * ) for all x * ∈ int(dom J * ).
(5)

Proof. Since x * ∈ int(dom J * ) we have from [START_REF] Lopez | A formula for the optimal solutions of a relaxed minimization problem. Applications to subdifferential calculus[END_REF]Theorem 1] or [START_REF] Hiriart-Urruty | The epsilon strategy in variational analysis: illustration with the closed convexification of a function[END_REF]Theorem 6] that

∂J * (x * ) = argmin(J -x * , . ) * * = >0 co( -argmin(J -x * , . )).
(5')

Assume now that x ∈ coM J(x * ). By the Hahn-Banach Theorem, there exist

y * ∈ X * , r ∈ R, such that i * M J(x * ) (y * ) < r < y * , x ,
and M J(x * ) is included in the (weakly) open half-space [ y * , . < r]. Since x * ∈ int domJ * and J is weakly lower-semicontinuous, all the sublevel sets {u ∈ X : J(u) -x * , u ≤ s}, s ∈ R, are weakly compact. So, the set-valued mapping ≥ 0 → -argmin(J -x * , . ) is weakly upper-semicontinuous [START_REF] Moreau | Fonctionnelles convexes, Cours au Collège de France[END_REF]Proposition 11.c], and there exists > 0 such that -argmin(J -x * , . ) ⊂ [ y * , . < r]. We thus have i * -argmin(J-x * ,. ) (y * ) ≤ r < y * , x , and, by the Hahn-Banach Theorem again, x ∈ co( -argmin(J -x * , . )). It then follows from (5') that x ∈ ∂J * (x * ), and the proof is achieved.

We now are in a position to state the main result of our note.

Theorem 1. A weakly lower-semicontinuous function J : X → R ∪ {+∞} defined on a reflexive Banach space X turns out to be "adequate" if and only if it is essentially strictly convex.

Proof. (Sufficiency) Since J is essentially strictly convex, J * is essentially smooth and, by Proposition 3, J is "adequate".

(Necessity) Let us assume that the weakly lower-semicontinuous function J : X → R ∪ {+∞} is "adequate" ; by Theorem A, we will succeed in our aims if we prove that J * is essentially smooth. By definition of what an "adequate" J is, M J is single-valued on its domain dom M J = dom(∂J * ), which is nonempty and open. We thus have dom M J = int(dom J * ). As an application of Theorem B, we then get that ∂J * is single-valued on dom(∂J * ) = int(dom J * ) = ∅. It then follows from [START_REF] Bauschke | Essential smoothness, essential strict convexity, and Legendre functions in Banach spaces[END_REF]Theorem 5.6] that J * is essentially smooth.

Generalized proximal set-valued mappings in reflexive Banach spaces

In this section we consider the case when

J = f + h
where f ∈ Γ(X) is cofinite (this means that f * is real-valued on X * : domf * = X * ) and h : X → R ∪ {+∞} admits a continuous affine minorant : domh * = ∅. We also assume that J is proper : domf ∩ domh = ∅. Such a function J is not necessarily convex but it is cofinite. Indeed, picking a * ∈ domh * , there exists r ∈ R such that J ≥ f + a * , . -r, and so, for any x * ∈ X * , one has J * (x * ) ≤ f * (x * -a * ) + r ∈ R. On the other hand, since J is proper, J * does not take the value -∞. Consequently, J is cofinite. We now introduce the notation

M J(x * ) = Prox f h (x * ), x * ∈ X * , (6)
and justify this choice by considering the case when (X, ) is a Hilbert space and f = 1 2 2 . We thus have

M J(x * ) = argmin u∈X 1 2 x * -u 2 + h(u) , x * ∈ X * = X.
In other words, M J is just the so-called Moreau proximal set-valued mapping associated with the function h. It should be emphasized however that we do not assume that h is convex. We also set

J * = (f + h) * = Φ f h , (7)
a continuous convex function that can be viewed as an extension of the Asplund function : indeed, taking f = 1 2 2 , S ⊂ X, h = i S (the indicator function of S) in a Hilbert space setting, and denoting by d S the distance function to S, we get, for any x * ∈ X * = X,

Φ f h (x * ) = 1 2 x * 2 -d 2 S (x * ) = Φ S (x * ),
which is called the Asplund function associated with S ( [HU]). In the same setting (i.e. (X, ) Hilbert and f = 1 2

2 ) one has

Φ f h = 1 2 -(h 1 2 2 ),
where denotes the infimal convolution operation, and h 1 2 2 is a Moreau envelope of the (non-necessarily convex) function h (see for example [Wa] Theorem 3.5 for the Euclidean case).

Proposition 4. Let X be reflexive, f ∈ Γ(X), f cofinite, and h : X → R ∪ {+∞} a weakly lower-semicontinuous function such that domf ∩ domh = ∅, domh * = ∅. Then the set-valued mapping Prox f h defined in ( 6) is single-valued on a G δ -dense subset of X * and the subdifferential of the continuous convex function Φ f h defined in ( 7) is given by

∂Φ f h (x * ) = co Prox f h (x * ) , ∀x * ∈ X * . ( 8
)
Proof. We know that the weakly lower-semicontinuous function J = f + h is cofinite. It then suffices to apply Proposition 2 and Theorem B.

In the particular case where (X, ) is a Hilbert space, f = 1 2 2 , and h = i S is the indicator function of a weakly closed subset of X, what (8) says is that the

associated Asplund function Φ S = 1 2 2 -d 2 S has a subdifferential expressed as ∂Φ S (x * ) = co (P S (x * )) , (9)
where P S (x * ) is the projection set-valued mapping on S (i.e., P S (x * ) is the set of points in S at minimal distance of x * ). A formula like ( 9) is hopeless for general S, especially as P S (x * ) can be empty (while the continuous convex function Φ S has a nonempty subdifferential everywhere on X). That is the reason why a different strategy had to be applied in order to express ∂Φ S (x * ); this was done in [HULV, Section 3] by enlarging P S (x * ) to P S (x * ) for > 0, and then filtering on the resulting closed convex set coP S (x * ). In a famous and rather hold result (1961), V. Klee proved that every weakly closed Tchebychev subset S of a Hilbert space X is necessary convex. In other words (P S (x * ) single-valued for all x * ∈ X) ⇒ (S convex).

To know whether this implication holds true for general closed sets S is still an open question; see [HU] for an overview on this problem. We now extend Klee's theorem to the set-valued proximal process introduced in this note :

Theorem 2. Let X be reflexive, f ∈ Γ(X), f cofinite, h : X → R ∪ {+∞}
weakly lower-semicontinuous and such that dom f ∩ dom h = ∅. The following assertions are then equivalent :

(i)    h is f -Tchebychev, meaning that Prox f h is single-valued on X * (that is to say : Prox f h (x * ) = {prox f h (x * )}, ∀x * ∈ X * ) (ii) f + h is essentially strictly convex.
In such a case, Φ f h is Gâteaux-differentiable on X * and one has

∇Φ f h (x * ) = prox f h (x * ), ∀x * ∈ X * . ( 10
)
Proof. According to the very definition of Prox f h (see ( 6)) and since J is cofinite, one clearly has J adequate ⇔ Prox f h single-valued on X * . Therefore, the equivalence between (i) and (ii) comes from Theorem 1. Formula (10) comes from (8).

Theorem 2 says, among other things, that, even if the function h is not convex, the generalized Asplund function Φ f h is a primitive function of the mapping prox f h on X * , whenever h is a weakly lower-semicontinuous f -Tchebychev function. Remark 1. Taking for (X, ) a Hilbert space and f = 1 2 2 in both Proposition 4 and Theorem 2, we extend Theorem 3.5 in [Wa] from Euclidean spaces to Hilbert spaces and answer Problem 8 posed in ( [BMW] Section 8) by characterizing the class of Tchebychev functions in infinite dimensional spaces.

Adequate functions and Bregman-Tchebychev sets

Let f ∈ Γ(X) be Gâteaux-differentiable on int(domf ) = ∅. The so-called Bregman "distance" associated with f (see e.g. [BBC]) is defined as

D f (x, y) = f (x) -f (y) -∇f (y), x -y , (x, y) ∈ dom f × int(dom f ).
Given S ⊂ X, S ∩ dom f = ∅, and y ∈ int(dom f ), we set D f S (y) = inf u∈S D f (u, y)

for the D f -distance from y to S and P f S (y) = {x ∈ S : D f (x, y) = D f S (y)} for the D f -projection of y on S. One says that S is D f -Tchebychev whenever P f S is single-valued on int(dom f ). Taking X and f as in Remark 1 the D f -Tchebychev sets boil down to the usual ones. We now introduce the additional assumption

∇f (int(dom f )) = X * , (11)
that holds, for instance, if f is a cofinite Legendre function. It is thus easy to check that

S is D f -Tchebychev ⇔ i S is f -Tchebychev ⇔ f + i S is adequate. (12)
Proposition 5. Let X be reflexive and f ∈ Γ(X) satisfying (11). For any weakly closed S ⊂ X such that S ∩ dom f = ∅, the following assertions are equivalent :

(i) S is D f -Tchebychev (ii) f + i S is essentially strictly convex.
So, if S is D f -Tchebychev, then S ∩ dom f is convex. In particular, any weakly closed D f -Tchebychev set included in dom f is convex.

Proof. Due to (12), Theorem 1 gives the equivalence between (i) and (ii). The other assertions are then trivial.

Corollary 1. Assume f is a cofinite Legendre function and S is a weakly closed set included in int(dom f ). Then S is D f -Tchebychev if and only if S is convex.

Proof. Sufficiency comes from [START_REF] Bauschke | Essential smoothness, essential strict convexity, and Legendre functions in Banach spaces[END_REF]Corollary 7.9]. Necessity is due to the second part of Proposition 5.

Remark 2. Since there are Legendre functions that are cofinite but not 1coercive ([BBC, Example 7.5]), Corollary 1 above improves a bit [START_REF] Li | The Bregman distance, approximate compactness and convexity of Chebyshev sets in Banach spaces[END_REF]Theorem 4.1].

The finite dimensional case

In this context, Theorem B reads as follows : Theorem B'. Let J : R n → R ∪ {+∞} be lower-semicontinuous. Then, for any x * ∈ int(dom h * ), one has : ∂J * (x * ) = coM J(x * ).

(13)

Proof. Since x * ∈ int(dom J * ) and J is lower-semicontinuous, the set M J(x * ) is compact and coM J(x * ) is compact too. Thus (13) is just (5).

We now give another proof of Theorem B' that does not use Theorem B. It is based on a formula given in [BHU] which is limited to finite dimensional spaces. Since x * ∈ int(dom h * ) we know that there exist α > 0 and r ∈ R such that J -x * , . ≥ α . + r.

Thus the asymptotic function (J -x * , . ) ∞ of J -x * , . , that is J ∞ -x * , .

where, for any x ∈ R n , J ∞ (x) = lim inf (t,u)→(0 + ,x) tJ(u/t), is nonnegative and vanishes at the origin of R n only. We then have (see [HULV] Theorem 6 or [BHU] p 1672) :

∂J * (x * ) = argmin(J -x * , . ) * * = co argmin(J -x * , . ) = coJM (x * ).

Remark 3. According to Theorem B' one can replace co by co in the formulas (8) and ( 9) when X is finite dimensional.

[As] E. Asplund, Fréchet differentiability of convex functions. Acta. Math., Vol. 121, 31-47 (1968).