Andrei Romashchenko

Pseudo-random graphs and bit probe schemes with one-sided error *

We study probabilistic bit-probe schemes for the membership problem. Given a set A of at most n elements from the universe of size m we organize such a structure that queries of type "x ∈ A?" can be answered very quickly.

H. Buhrman, P.B. Miltersen, J. Radhakrishnan, and S. Venkatesh proposed a bit-probe scheme based on expanders. Their scheme needs space of O(n log m) bits. The scheme has a randomized algorithm processing queries; it needs to read only one randomly chosen bit from the memory to answer a query. For every x the answer is correct with high probability (with two-sided errors).

). We obtain a slightly weaker result (space of size n 1+δ poly(log m) bits and two bit probes for every query) for a scheme that is effectively encodable.

Our construction is based on the idea of naive derandomization, which is of independent interest. First we prove that a random combinatorial object (a graph) has the required properties, and then show that such a graph can be obtained as an outcome of a pseudo-random bits generator. Thus, a suitable graph can be specified by a short seed of a PRG, and we can put an appropriate value of the seed into the cache memory of the scheme.

1 Introduction.

We investigate the static version of the membership problem. The aim is to represent a set A ⊂ {1, . . . , m} by some data structure so that queries "x ∈ A?" can be easily replied. We are interested in the case when the number of elements in the set n = |A| is much less than size m of the universe (e.g., n = exp{poly(log log m)} or n = m 0.01 ).

In practice, many different data structures are used to represent sets: simple arrays, different variants of height-balanced trees, hash tables, etc. The simplest solution is just an array of m bits; to answer a query "x ∈ A?" we need to read a single bit from the memory (the x-th bit in the data storage is equal to 1 if x ∈ A). However, the size of this data structure is excessive: it requires m bits of memory, while there exist only m n = 2 Θ(n log m) different subsets A of size n in the m-elements universe.

Nowadays the standard practical solution for the membership problem is a more complex data structure proposed by Fredman, Komlós, and Szemerédi [START_REF] Fredman | Storing a sparse table with O(1) worst case access time[END_REF]. This scheme is based on perfect hashing; a set is represented as a table of O(n) words (hash-values) of size log m bits, and a query "x ∈ A?" requires to read O(1) words from the memory. The space complexity of this construction is quite close to the trivial lower bound Ω(log m n ). The asymptotic of the space complexity of this scheme was further improved in [START_REF] Fiat | Non-oblivious hashing[END_REF][START_REF] Brodnik | Membership in Constant Time and Minimum space[END_REF][START_REF] Pagh | Low Redundancy in Static Dictionaries with O(1) Worst Case Lookup Time[END_REF]. Similar space complexity was achieved in dynamic data structures, which support fast update of the set stored in the database (see, e.g., analysis of the cuckoo hashing scheme in [START_REF] Pagh | Cuckoo Hashing[END_REF][START_REF] Devroye | Cuckoo hashing: Further analysis[END_REF]). A subtle analysis of the space and bit-probe complexity for the membership problems was given also in [START_REF] Pagh | On the Cell Probe Complexity of Membership and Perfect Hashing[END_REF] (in particular, [START_REF] Pagh | On the Cell Probe Complexity of Membership and Perfect Hashing[END_REF] suggested a membership scheme based on bounded concentrator graphs). Note that all these schemes require to read from the memory O(log m) bits to answer each query.

Another popular practical solution is Bloom's filter [START_REF] Bloom | Space-time trade-offs in hash coding with allowable errors[END_REF]. This data structure requires only O(n) bits, whatever is the size of the universe; to answer a query we need to read O(1) bits from the memory. The drawback of this method is that we can get false answers to some queries. Only false positives answers are possible (for some x ∈ A Bloom's filter answers "yes"), but false negatives are not. When this technique is used in practice, it is believed that for a "typical" set A the fraction of false answers should be small. However, in many applications we cannot fix a priori any reasonable probability distribution on the family of all sets A and on the space of possible queries.

An interesting alternative approach was suggested by Harry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, and Venkatesh Srinivasan [START_REF] Buhrman | Are bitvectors optimal? Siam[END_REF]. They introduced randomness into the query processing algorithm. That is, the data structure remains static (it is deterministically defined for each set A), but when a query is processed, we a toss coins and read randomly chosen bit from the memory. In this model, we allow to return a wrong answer with some small probability. Notice the sharp difference with the Bloom's filter: Now we must correctly reply to the query "x ∈ A?" with probability close to 1 for each x.

Buhrman, Miltersen, Radhakrishnan, and Venkatesh investigated both two-sided and one-sided errors. In this paper we will concentrate mostly on one-sided errors: if x ∈ A, then the answer must be always correct, and if x ∈ A, then a small probability of error is allowed.

Recall that a trivial information-theoretic bound shows that the size of the structure representing a set A cannot be less that log m n = Ω(n log m) bits. Surprisingly, this bound can be achieved if we allow two-sided errors and use only single bit probe for each query. This result was proven in [START_REF] Buhrman | Are bitvectors optimal? Siam[END_REF]. We refer to the scheme proposed their as the BMRV-scheme:

Theorem 1 (two-sided BMRV-scheme, [START_REF] Buhrman | Are bitvectors optimal? Siam[END_REF]) For any ε > 0 there is a scheme for storing subsets A of size at most n of a universe of size m using O( n ε 2 log m) bits so that any membership query "Is x ∈ A?" can be answered with error probability less than ε by a randomized algorithm which probes the memory at just one location determined by its coin tosses and the query element x.

The size of the memory achieved in this theorem is only a constant factor greater than the best possible. In fact, the trivial lower bound log m n can be improved: the less is the probability of an error of the scheme, the more memory we need.

Theorem 2 (lower bound, [START_REF] Buhrman | Are bitvectors optimal? Siam[END_REF]) (a) For any ε > 0 and n ε < m 1/3 , any εerror randomized scheme which answers queries using one bitprobe must use space Ω( n ε log 1/ε log m). (b) Any scheme with one-sided error ε that answers queries using at most one bitprobe must use Ω( n 2 ε 2 log(n/ε) log m) bits of storage. Note that for one-sided error schemes the known lower bound is much stronger. Part (b) of the theorem above implies that we cannot achieve the size of space O(n log m) with a one probe scheme and one-sided error. However we can get very close if we allow O(1) probes instead of a single probe: Theorem 3 (one-sided BMRV-scheme, [START_REF] Buhrman | Are bitvectors optimal? Siam[END_REF]) Fix any δ > 0. There exists a constant t such that the following holds: There is a one-sided 1 3 -error randomized scheme that uses space O(n 1+δ log m) and answers membership queries with at most t probes.

The constructions in [START_REF] Buhrman | Are bitvectors optimal? Siam[END_REF] is not explicit: given the list of elements A, the corresponding scheme is constructed (with some brute force search) in time 2 poly(m) . Moreover, each membership query requires exponential in m computations.

The crucial element of the constructions in Theorem 1 is an unbalanced expander graph. Existence of a graph with required parameters was proven in [START_REF] Buhrman | Are bitvectors optimal? Siam[END_REF] probabilistically. We know that such a graph exists and we can find it by brute force search, but we do not know how to construct it explicitly. In case we have an effective construction of an expander with good parameters, we will get a practical variant of the BMRV-scheme. This scheme could be also generalized to build more complex data structures (see [START_REF] Östlin | One-Probe Search[END_REF] for a construction of a dictionary data structure based on the BMRV-scheme and some explicit expanders).

Since Bassalygo and Pinsker defined expanders [START_REF] Pinsker | On the complexity of a concentrator[END_REF][START_REF] Bassalygo | The complexity of an optimal nonblocking commutation scheme without reorganization[END_REF], many explicit (and poly-time computable) constructions of expander graphs were discovered, see a survey [START_REF] Hoory | Expander graphs and their applications[END_REF]. However, most of the known constructions are based on the spectral technique that is not suitable to get an expander of degree d with an expansion parameter greater than d/2, see [START_REF] Kahale | Eigenvalues and expansion of regular graphs[END_REF]. This is not enough for the construction used in the proof of Theorem 1 in [START_REF] Buhrman | Are bitvectors optimal? Siam[END_REF]; we need there a graph with expansion parameter close to d.

There are only very few effective constructions of unbalanced graph with large expansion parameter. One of the known constructions was suggested by Capalbo et al in [START_REF] Capalbo | Randomness Conductors and Constant-Degree Lossless Expanders[END_REF]; its parameters are close to the optimal values if the size of the right part of the graph is constant times less than the size of the left part of the graph. However, in the BMRV-scheme we need a very unbalanced expander, i.e., a graph where the right part of the graph is much less than the left part; so, the technique from [START_REF] Capalbo | Randomness Conductors and Constant-Degree Lossless Expanders[END_REF] seems to be not suitable here. Some explicit version of the BMRV-scheme was suggested in [START_REF] Ta-Schma | Storing information with extractors[END_REF] (this construction involves Trevisan's extractor; note that Trevisan's extractor is known to be a good highly unbalanced expander, [START_REF] Ta-Shma | Loss-less Condensers, Unbalanced Expanders, and Extractors[END_REF]). The best known explicit construction of a highly unbalanced expander graph was presented in [START_REF] Guruswami | Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes[END_REF]. It is based on the Parvaresh-Vardy code with an efficient list decoding. Thanks to the special structure if this expander, it enjoys some nice property of effective decoding. Using this technique, the following variant of Theorem 1 can be proven: Theorem 4 ( [START_REF] Guruswami | Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes[END_REF]) For any δ > 0 there exists a scheme for storing subset A of size at most n of a universe of size m using n 1+δ • poly(log m) bits so that any membership query can be answered with error probability less than ε by a randomized algorithm which probes the memory at one location determined by its coin tosses and the query element x.

Given the list of elements A, the corresponding storing scheme can be constructed in time poly(log m, n). When the storing scheme is constructed, a query for an element x can be calculated in time poly(log m).

In Theorems 1, 3, 4, a set A is encoded into a bit string, and when we want to know if x ∈ A, we just read from this string one randomly chosen bit (or O(1) bits in Theorem 3). The obtained information is enough to decide whether x is an element of the set. Let us notice that in all these computations we implicitly use more information than just a single bit extracted from the memory. To make a query to the scheme and to process the retrieved bit, we need to know the parameters of the scheme: the size n of the set A, the size m of the universe, and the allowed error probability ε. This auxiliary information is very short (it takes only log(m/ε) bits), and it does not depend on the stored set A. We assume that this information is somehow hardwired into the bitprobe scheme (we shall say that this information is cached in advance by the algorithms that processes queries).

In this paper we consider a more liberal model, where some small information cached by the scheme can depend not only on n, m, and ε, but also on the set A. Technically, the data stored in our scheme consists of two parts of different size: a small cached string C of length poly(log m), and a long bit string B of length n • poly log(m). Both these strings are prepared for a given set A of n elements (in the universe of size m). When we need to answer a query "x ∈ A?", we use C to compute probabilistically a position in B and read there one bit. This is enough to answer whether x is an element of A, with a small one-sided error:

Theorem 5 Fix any constant ε > 0. There exists a one-sided ε-error randomized scheme that includes a string B of length O(n log 2 m) and an auxiliary word C of length poly(log m). We can answer membership queries "x ∈ A?" with one bit probe to B. For x ∈ A the answer is always correct; for each x ∈ A probability of error is less than ε.

The position of the bit probed in A is computed from x and the auxiliary word C in time poly(log m).

Remark 1: Schemes with 'cached' auxiliary information that depends on A (not only on its size n = |A| and the size m of the universe) make sense only if the cached information is very small. Indeed, if the size of the cached data is about log m n bits, then we can put there the list of all elements of A, so the problem becomes trivial. Since in our construction we need cached information of size poly(log m) bits, the result is interesting when poly(log m) ≪ n ≪ m, e.g., for n = exp{poly(log log n)}. Note that by Theorem 2 the space size O(n log 2 m) with one-sided error cannot be achieved by any schemes without cached auxiliary information that depends on A.

Remark 2: The model of data structures with cached memory looks useful for practical applications. Indeed, most computer systems contain some hierarchy of memory levels: CPU registers and several levels of processor caches, then random access memory, flash memory, magnetic disks, remote network-accessible drives, etc. Each next level of memory is cheaper but slower. So, it is interesting to investigate the tradeoff between expensive and fast local memory and cheap and slow external memory. There is a rich literature on algorithms with external memory, see, e.g, surveys [START_REF] Vitter | External memory algorithms and data structures[END_REF][START_REF] Vitter | Algorithms and Data Structures for External Memory[END_REF]. Thus, the idea of splitting the data structure into 'cached' and 'remote' parts is very natural and quite common in computer science. However, tradeoff between local and external memory is typically studied for dynamic data structures. The same time, it is not obvious that fast cache memory of negligible size can help to process queries in a static data structure. Since a small cache 'knows' virtually nothing about most objects in the database, at first sight it seems to be useless. However, Theorem 5 shows that even a very small cache can be surprisingly efficient.

Remark 3: In the proof of Theorem 5 we derandomize a probabilistic proof of existence of some kind of expander graphs. In many papers derandomization of probabilistic arguments involves highly sophisticated ad-hoc techniques. But we do derandomization in rather naive and straightforward way: take a value of a suitable pseudo-random bits generator and check that with high probability (i.e., for most values of the seed) a pseudo-random objects enjoys the required property. In fact, we observe that several types of generators fit our construction. Since the required property of a graph can be tested in AC 0 , we can use the classic Nisan-Wigderson generator or (thanks to the recent result of Braverman [START_REF] Braverman | Poly-logarithmic Independence Fools AC 0 Circuits[END_REF]) any polylog-independent function. Also the required property of a pseudo-random graph can be tested by a machine with logarithmic space. Hence, we can use Nisan's generator [START_REF] Nisan | Pseudorandom generators for space-bounded computation[END_REF]. Our idea of employing pseudo-random structures is quite similar to the construction of pseudo-random hash-functions in [START_REF] Arbitman | De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results[END_REF]. We stress that we do not need any unproven assumptions to construct all these generators.

In Theorem 5 we construct a scheme such that decoding is effective: when the scheme is prepared, we can answer queries "x ∈ A?" in time polynomial in log m. However the encoding (preparing the database and the auxiliary word for a given set A) runs in expected time poly(m). We assume that n ≪ m, and the time polynomial in m seems to be too long. It is natural to require that encoding of the scheme runs in time poly(n, log m) (i.e., polynomial in the size of the encoded set A and the size of an index of each element in the universe). The next theorem claims that the encoding time can be reduced if we slightly increase the space of the scheme: Theorem 6 The scheme from theorem 5 can be made effectively encodable in the following sense. Fix any constants ε, δ > 0. There exists randomized scheme that includes a bit string B of length n 1+δ poly(log m) and an auxiliary word C of length poly(log m). We can answer membership queries "x ∈ A?" with two bits probe to B. For x ∈ A the answer is always correct; for x ∈ A probability of error is less than ε.

The position of the bit probed in A is computed by x and the auxiliary word C in time poly log(m). Given A, the entire scheme (the string B and the word C) can be computed probabilistically in average time poly(n, log m).

The rest of the paper is organized as follows. In Section 2 we remind the main ideas in the BMRV-scheme. We prove Theorem 5 in Section 3, and Theorem 6 in Section 4. In Section 5 we show that the proof of Theorem 2 (a) mutatis mutandis can be applied to our model with small cached memory. In Conclusion we discuss some open questions.

2 How BMRV-scheme works.

Let us explain the main ideas of the proof of Theorem 1 in [START_REF] Buhrman | Are bitvectors optimal? Siam[END_REF]. The construction is based on highly unbalanced expanders. We use a standard notation: for a vertex v we denote by Γ(v) the set of its neighbors; for a set of vertices A we denote by Γ(A) the set of neighbors of A, i.e., Γ(A) = ∪ v∈A Γ(v). So, the definition of expanders claims that for all small enough sets A of vertices in the left part of the graph, |Γ(A)| ≥ (1 -δ)d|A| (the maximal size of |Γ(A)| is obviously d|A|, since degrees of all vertices on the left are equal to d). The argument below is based on the following combinatorial property of an expander: Lemma 1 (see [START_REF] Capalbo | Randomness Conductors and Constant-Degree Lossless Expanders[END_REF]) Let ε be a positive number, and G be an (m, s, d, k, δ)expander with δ ≤ ε/4. Then for every subset

A ⊂ L such that |A| ≤ k/2, the number of vertices x ∈ L \ A such that |Γ(x) ∩ Γ(A)| ≥ εd is not greater than |A|/2.
Let G be a (m, s, d, k, δ)-expander with δ < ε/4. The storage scheme is defined as follows. We identify a set A ⊂ {1, . . . , m} of size n (n ≤ k/2) with a subset of vertices in the left part of the graph. We will represent it by some labeling (by ones and zeros) on the vertices of the right part of the graph. We do it in such a way that the vast majority (at least (1 -ε)d) of neighbors of each vertex v from the left part of the graph correctly indicate whether v ∈ A. More precisely, if v ∈ A then at least (1 -ε)d of its neighbors in R are labeled by 1; if v ∈ L \ A then at least (1 -ε)d of its neighbors in R are labeled by 0. Thus, querying a random neighbor of v will return the right answer with probability > 1 -ε.

It remains to explain why such a labeling exists. In fact, it can be constructed by a simple greedy algorithm. First, we label all neighbors of A by 1, and the other vertices on the left by 0. This labeling classifies correctly all vertices in A. But it can misclassify some vertices outside A: some vertices in L \ A can have too many (more than εd) neighbors labeled by 1. Denote by B the set of all these "erroneous" vertices. We relabel all their neighbors, i.e., all vertices in Γ(B) to 0. This fixes the problem with vertices outside A, but it can create problems with some vertices in A. We take the set of all vertices in A that became erroneous (i.e., vertices in A that have at least εd neighbors in Γ(B)), and denote this set of vertices by A ′ . Then, we relabel all Γ(A ′ ) to 1. This operation create new problems in some set of vertices B ′ ⊂ B, we relabel Γ(B ′ ) to 0, etc. In this iterative procedure we get a sequence of sets To organize a storing scheme (and to estimate its size) for a set A of size n in the universe of size m, we should construct an (m, s, d, k = 2n, δ = ε/4)expander. Parameters m, k, δ of the graph are determined directly by the parameters of the desired scheme (by the size of A and the universe and the allowed error probability ε). We want to minimize the size of the left part of the graph s, which is the size of the stored data. Existence of expanders with good parameters can be proven by probabilistic arguments: Given the parameters m, n, ε, we can find an (m, O( n log m ε 2 ), log m ε , n, ε)-expander by brute force search. This can be done by a deterministic algorithm in time 2 poly(m/ε) . Hence, we can construct the bit-probe structure defined above in exponential time. Moreover, when the structure is constructed and we want to answer a query "x ∈ A?", we need to read only one bit from the stored bit string. But to select the position of this bit we need again to reconstruct the expander graph, which requires exponential computations. We could keep the structure of the computed graph in "cache" (compute the graph once, and then re-use it every time a new query should be answered). However, in this case the size of the "cached data" (the size of the graph) becomes much greater than m, which makes the bit-probe scheme meaningless (it is cheaper to store A as a trivial m-bits array).

A ⊃ A ′ ⊃ A ′′ ⊃ . . .
In [START_REF] Guruswami | Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes[END_REF] a nice and very powerful explicit construction of expanders was suggested: Theorem 7 ( [START_REF] Guruswami | Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes[END_REF]) Fix an ε > 0 and δ > 0. For all integers m, n there exists an explicit (m, s = n 1+δ • poly(log m), d = poly(log m), n, ε)-expander such that for an index of a vertex v from the left part (a binary representation of an integer between 1 and m) and an index of an outgoing edge (a binary representation of an integer between 1 and d), the corresponding neighbor on the right part of the graph (an integer between 1 and s) can be computed in time polynomial in log m.

Also, the following effective decoding algorithm exists. Given a set of vertices T from the right part of the graph, we can compute the list of vertices in the left part of the graph that have at least (4εd) neighbors in T , i.e.,

S = {v : |Γ(v) ∩ T | ≥ 4εd}, in time poly(|S|, n, log m).
Theorem 4 is proven by plugging the expander from Theorem 7 in the general scheme explained above, see details in [START_REF] Guruswami | Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes[END_REF].

3 Proof of Theorem 5.

Refinement of the property of ε-reduction.

The construction of a bit-probe scheme for a set A of size n in the m-elements universe (with probability of an error bounded by some ε) explained in the previous section involves an (m, s, d, k, δ)-expander with s = O( n ε 2 log m) and d = O( 1 ε log m). Such a graph contains dm edges (degree of each vertex on the left is d). The list of all its edges can be specified by a string of dm log s bits: we sort all edges by their left ends, and specify for each edge its right end. Denote the size of the description of this graph by N = dm log s.

In what follows we will assume that number s is a power of 2 (this will increase the parameters of the graph only by a factor at most 2). So, we may assume that every string of N (m, s, d) = dm log s bits specifies a bipartite graph with m vertices on the left, s vertices on the right and degree d on the left. Lemma 2 claims that most of these bits string of length N describe an (m, s, d, k, δ)-expander. By Lemma 1, if a graph is an expander with these parameters, then for ε = 4δ and for every set A ⊂ L of size less than k/2 the following reduction property holds:

Combinatorial Property 1 (ε-reduction property) For every subset A ⊂ L such that |A| ≤ k/2, the number of vertices x ∈ L \ A such that |Γ(x) ∩ Γ(A)| ≥ εd is not greater than |A|/2.
This property was the main ingredient of the BMRV-scheme. In our bit-probe scheme we will need another variant of Property 1:

Combinatorial Property 2 (strong ε-reduction) Let G = (L, R, E) be a bipartite graph, and A ⊂ L be a subset of vertices from the left part. We say that the strong ε-reduction property holds for A in this graph if for all x ∈ L \ A • the property of strong ε-reduction holds for the set A (we identify it with a subset of vertices in left part of the graph).

|Γ(x) ∩ Γ(A)| ≤ εd.
Moreover, the property of strong ε-reduction for A holds for the majority of graphs with the parameters specified above.

The order of quantifiers is important here: we do not claim that in a random graph the strong ε-reduction property holds for all A; we say only that for every A the strong ε-reduction is true in a random graph.

Proof of lemma: Let v be any vertex in L \ A. We estimate probability that at least εd neighbors of x are at the same time neighbors of A (assuming that all edges are chosen at random independently). There are d εd choices of εd vertices among all neighbors of v. Hence,

Prob[|Γ(v) ∩ Γ(A)| ≥ εd] ≤ d εd • |Γ(A)| |R| εd ≤ d εd • dn 2d 2 n εd = 1 2 2 log m
This probability is less than 1/m 2 (for each vertex v). So, the expected number of vertices v ∈ L such that |Γ(v) ∩ Γ(A)| ≥ εd, is less than 1/m < 1/2. Hence, the strong ε-reduction property holds for A for more than 50% of graphs.

Testing the property of strong ε-reduction.

Lemma 3 implies that a graph with the strong reduction property for A exists.

Given A, we can find such a graph by brute force search. But we cannot use such a graph in our bit-probe scheme even if we do not care about computation complexity: the choice of the graph depends on A, and the size of the graph is too large to embed it into the scheme explicitly. We need to find a suitable graph with a short description. We will do it using pseudo-random bits generators ('pseudo-random' graphs will be parameterized by the seed of a generator). Property 2 is a property of a graph and of a set of vertices A in this graph. We can interpreted it as a property of an N -bits string (that determines a graph) and some A ⊂ {1, . . . , m}. Lemma 3 claims that for every A, for a randomly chosen graph (a randomly chosen N -bits string) with high probability the strong reduction property is true. We want to show that the same is true for a pseudorandom graph. At first, we observe that the strong reduction property can be tested by an AC 0 circuit (a Boolean circuit of bounded depth, with polynomial number of gates and, or with unbounded fan-in, and negations).

Indeed, we need to check for each vertex v ∈ L \ A that the number of vertices in Γ(v) ∩ Γ(A) is not large. For each vertex w in the right part of the graph we can compute by an AC 0 -circuit whether w ∈ Γ(A):

u∈A i≤d [ the i-th neighbor of u is w ] (the condition in the square brackets is a statement about one edge in a graph, i.e., it is a conjunction of O(log N ) bits and negations of bits from the representation of this graph). So, for each v ∈ L \ A and for i = 1, . . . , d we can compute whether the i-th neighbor of v belongs to Γ(A):

b v,i = w∈R ([ the i-th neighbor of v is w ] & [ w ∈ Γ(A) ])
It remains to 'count' for each v ∈ L \ A the number of neighbors in Γ(A) and compute the thresholds

Th(b v,1 , . . . , b v,d ) = 1, if b v,1 + • • • + b v,d ≥ εd, 0, otherwise.
In AC 0 we cannot compute thresholds with linear number of inputs (e.g., the majority function is not in AC 0 , see [START_REF] Håstad | Almost optimal lower bounds for small depth circuits[END_REF]). However, we need threshold functions with only logarithmic number of inputs. Such a function can be represented by a CNF of size 2 O(d) = poly(N ). Then, we combine together these thresholds for all v ∈ L \ A, and get an AC 0 -circuit that tests the property of strong ε-reduction.

Pseudo-random graphs.

We need to generate a pseudo-random string of N bits that satisfies the strong ε-reduction property (for some fixed set A). We know that (i) by Lemma 3, for a uniformly distributed random string this property is true with high probability, and (ii) this property can be checked in AC 0 . It remains to choose a pseudorandom bits generator that fools this particular AC 0 -circuit. There exist several generators that fools such distinguishers. Below we mention three different solutions.

Remark: We can test by an AC 0 -circuit Property 2 for every fixed set A but not for all sets A together.

The first solution: the generator of Nisan and Wigderson. The classic way to fool an AC 0 circuit is the Nisan-Wigderson generator: Theorem 8 (Nisan-Wigderson generator, [START_REF] Nisan | Hardness vs Randomness[END_REF]) For every constant c there exists an explicit family of functions G m : {0, 1} poly(log N ) → {0, 1} N such that for for any family of circuits C N (with N inputs) of polynomial in N size and depth c, the difference

|Prob y [C N (y) = 1] -Prob z [C N (G m (z)) = 1]| tends to zero (faster than 1/poly(N )).
The generator is effective: generator's value G m (x) can be computed from a given x in time poly(log N ).

From this theorem and Lemma 3 it follows that for each A ⊂ {1, . . . , m} of size at most n, for most values of the seed of the Nisan-Wigderson generator G m , a pseudo-random graph G m (x) satisfies the strong ε-expansion property for A.

The second solution: polylog-independent strings. M. Braverman proves that all polylog-independent functions fool AC 0 -circuits: (for some absolute constant κ). Then C cannot distinguish between the uniform distribution U and any D-independent distribution µ on its inputs:

|Prob µ [C(x) accepts a µ-random x] -Prob U [C(x) accepts a U -random x]| < ε.
It follows that instead of the Nisan-Wigderson generator we can take any (log c n)-independent function (for large enough constant c). The standard way to generate r-independent bits (in our case we need r = log c n) is a polynomial of degree r over a finite field of size about N . Seeds of this 'pseudo-random bits generator' are coefficients of a polynomial. Also, other (more computationally effective) constructions of polylog-independent functions can be used. E.g., the construction from [START_REF] Siegel | On universal classes of fast high performance hash functions, their time-space trade-off, and their applications[END_REF][START_REF] Siegel | On universal classes of extremely random constant time hash functions and their time-space tradeoff[END_REF] provides a family of (log c n)-independent functions with very fast evaluation algorithm, and each function is specified by poly(log n) bits (so, the size of the seed is again poly-logarithmic).

The third solution: the generator of Nisan. The property of strong ε-reduction can be tested by a Turing machine with logarithmic working space. Technically we need a machine with

• advice tape: read-only, two-way tape, where the list of elements of A is written;

• input tape: read-only tape with random (or pseudo-random) bits, with logarithmic number of passes (the machine is allowed to pass along the input on this tape only O(log N ) times);

• index tape: read-only, two-way tape with logarithmic additional information;

• work tape that is two-way and read-write; the zone of the working tape is restricted to O(log N ).

We interpret the content of the input tape as a list of edges of a random (or pseudo-random) graph G = (L, R). The content of the index tape is understood as an index of a vertex v ∈ L \ A. The machine reads the bits from the 'input tape' (understood as a list of edges of a random graph) and checks that the vast majority of neighbors of v does not belong to the set of neighbors of A. The machine needs to read the input tape 2d = O(log N ) times (where d is degree of v): on the first pass we find the index of the first neighbor of v; on the second pass we check whether this neighbor of v is incident to any vertex of A; then we find the second neighbor of v, check whether it is is incident to any vertex of A, etc. The machine accepts the input if |Γ(v) ∩ Γ(A)| < εd.

We can use Nisan's generator [START_REF] Nisan | Pseudorandom generators for space-bounded computation[END_REF] to fool this machine. Indeed, this checking procedure fits the general framework of [START_REF] Sivakumar | Algorithmic derandomization via complexity theory[END_REF], where Nisans generator was used to derandomize several combinatorial constructions. The only nonconventional feature in our argument is that the input tape is not read-once: we allow to read the tape with random bits logarithmic number of times 1 . But we can apply Nisan's technique for a machine that reads random bits several times. David, Papakonstantinou, and Sidiropoulos observed (see [START_REF] David | How strong is Nisan's pseudorandom generator?[END_REF]) that a log-space machine with logarithmic (and even poly-logarithmic) number of passes on the input tape is fooled by Nisan's generator with a seed of size poly(log N ). Now we are ready to prove Theorem 5. We fix an ε > 0 and a set A ⊂ {1, . . . , m} of size m. Let G m be one of the pseudo-random bits generators discussed above. For all these generators, for most values of the seed z the values G m (z) encodes a graph such that the strong ε-reduction property holds for A. Let us fix one of such seeds. We label by 1 all vertices in Γ(A) and by 0 all other vertices in R in the graph encoded by the string G m (z).

The seed value z makes the "auxiliary word" C, and the specified above labeling of the right part of the graph makes the bit string B. To answer a query "x ∈ A?" we take a random neighbor of x in the graph and check its label. If the label is 1, we answer "x ∈ A"; otherwise "x ∈ A".

If x ∈ A, then there are no errors, since all neighbors of A are labeled by 1. If x ∈ A, then probability of an error is bounded by ε because of the strong ε-reduction property. We can answer a query in time poly(log m) since the generators under consideration are effectively computable.

Complexity of encoding

The disadvantage of this construction is non-effective encoding procedure. We know that for most seeds z the corresponding graph G m (z) enjoys the strong ε-reduction property. However, we need the brute force search over all vertices v ∈ L \ A (polynomial in m but not in log m) to check this property for any particular seed. Thus, we have a probabilistic encoding procedure that runs in expected time poly(m): we choose random seeds until we find one suitable for the given A.

In the next section we explain how to make the encoding procedure more effective (in expected time poly(n, log m)) for the following price: we will need a slightly greater size of the data storage, and we will take 2 bit probes instead of one at each query.

The decoding procedure works as follows. Given x ∈ {1, . . . , m}, we take its random neighbor in both constructed graphs and look at their labels (bits from B 1 and B 2 respectively).

• if the first label is 0, we say that x ∈ A;

• if the first label is 1 and the second bit is 0 then we say that x ∈ A.

• if both labels are is 1 then we say that x ∈ A.

If x ∈ A∪W , then by the definition of W we know that the procedure above with probability > (1 -ε) returns the correct answer. If x ∈ A, then by construction, both labels are equal to 1, and the procedure returns the correct answer with probability 1. If x ∈ W , then we have no guarantee about labels in B 1 ; but from the restricted strong reducibility property it follows that with probability > (1 -ε) the second label is 0. Thus, we have one-sided error probability bounded by ε.

5 A lower bound for schemes with cached memory.

In [START_REF] Buhrman | Are bitvectors optimal? Siam[END_REF] the lower bound Ω(n 2 log m) was proven for one-probe schemes with one-sided errors. This result cannot be applied to schemes with small "cached" memory dependent on A. In fact, our scheme of size Ω(n log m) with a cache of size poly(log m) bits (from Theorem 5) is below this bound for n ≫ log O(1) m.

On the other hand, the proof of the lower bound Ω( n ε log(1/ε) log m) (theorem 2 in [START_REF] Buhrman | Are bitvectors optimal? Siam[END_REF]) with minimal changes works for schemes with cached data if the size of the pre-computed and cached information is much less than n log m: Theorem 10 We consider randomized schemes that store sets of n elements from a universe of size m, with two-parts memory (the cached memory of size poly(log m) and the main storage).

For all constant ε < 1, if poly(log m) ≪ n ≪ 3 √ m, then any such scheme with error probability ε (possibly with two-sided errors) that answers queries using cached memory of size poly log(m) and one bit probe to the main storage, must use space Ω( n ε log(1/ε) log m).

Proof: We follow the arguments from theorem 2 in [START_REF] Buhrman | Are bitvectors optimal? Siam[END_REF] (preserving the notation). Consider any randomized scheme with two-parts memory. Denote by C the cached memory (of size poly(log m)) and by B the main part of the memory of size s (the scheme answers queries with one bit probe to C). Our aim is to prove a lower bound for s.

The proof is based on the bound for the size of cover-free families of sets proven by Dyachkov an Rykov [START_REF] Dyachkov | Bounds on the length of disjunctive codes[END_REF]. Let us remind that a family of sets F is called called r-cover-free if f 0 ⊆ f 1 ∪ . . . ∪ f r for all distinct f 0 , . . . , f r ∈ F . such that all sets from the family F ′ share in our scheme the same value C of the cached memory. Further, we repeat word for word the proof of theorem 2 from [START_REF] Buhrman | Are bitvectors optimal? Siam[END_REF] with substitute F ′ instead of F .

Conclusion.

In this paper we constructed an effective probabilistic bit-probe scheme with one-sided error. The used space is close to the trivial information-theoretic lower bound Ω(n log m). The scheme answers queries "x ∈ A?" with a small one-sided error and requires only poly-logarithmic (in the size of the universe) cached memory and one bit (two bits in the version with effective encoding) from the main part of the memory. For reasonable values of parameters (for n ≫ poly(log m)) the size of our scheme O(n log 2 m) with a cache of size poly(log m) is below the lower bound Ω(n 2 log m) proven in [START_REF] Buhrman | Are bitvectors optimal? Siam[END_REF] for one-probe schemes with one-sided errors without cached data dependent on A. The gap between our upper bounds and the trivial lower bound is a (log m)-factor.

The following questions remain open: How to construct a bit-probe memory scheme with one-sided error and effective encoding and decoding that requires to read only one bit from the main part of memory to answer queries? What is the minimal size of the cached memory required for a bit-probe scheme with one-sided error, with space of size O(n log m)?

The author thanks Daniil Musatov for useful discussions, and anonymous referees of CSR2011 for deep and very helpful comments.

Definition 1 A

 1 bipartite graph G = (L, R, E) (with left part L, right part R and set of edges E) is called (m, s, d, k, δ)-expander if L consists of m vertices, R consists of s vertices, degree of each vertex in L is equal to d, and for each subset of vertices A ⊂ L of size at most k the number of neighbors is at least (1 -δ)d|A|.

  whose neighbors are relabeled to 1 on steps 1, 3, 5, . . . of the algorithm, andB ⊃ B ′ ⊃ B ′′ ⊃ . . .whose neighbors are relabeled to 0 on iterations 2, 4, 6, . . . respectively. Lemma 1 guarantees that the number of the erroneous vertices on each iteration reduces by a factor of 2 (|B| ≤ |A|/2, |A ′ | ≤ |B|/2, etc.). Hence, in log m steps the procedure terminates.

Lemma 2 (

 2 [START_REF] Buhrman | Are bitvectors optimal? Siam[END_REF]) For all integers m, n and real ε > 0 there exists an (m,s = O( n log m ε 2 ), d = log m ε , n, ε)-expander. Moreover,the vast majority of bipartite graphs with n vertices on the left, s = 100n log m ε 2 vertices on the right, and degree d = log m ε at all vertices on the left are such expanders.

Lemma 3

 3 Fix an ε > 0. For all integers m, n, for every A ⊂ {1, . . . , m} of size n there exists a bi-partite graph G = (L, R, E) such that • |L| = m (the size of the left part ); • |R| = 2d 2 n = O(n log 2 m) (the size of the right part ); • degree of each vertex in the left part is d = 2 log m ε = O(log m);

Theorem 9 (

 9 [START_REF] Braverman | Poly-logarithmic Independence Fools AC 0 Circuits[END_REF]) Let C be a Boolean circuit of depth r and size M , ε be a positive number, andD = log M ε κr 2

First we take a large enough 1 ε 2 = 2

 122 -cover free family F of sets of size n from the universe {1, . . . , m}. The construction from[7, theorem 3.1] guarantees that there exists a family F such that εn log m n 2 +O(log m) .By assumption, each set f ∈ F can be represented in our scheme by some pair (B, C) (the main storage and the cached memory). Notice that|F | = 2 εn log m n 2 +O(log m) ≫ 2 |B| = 2 poly(log m) .Hence, the exists some value C and some F ′ ⊂ F of size |F ′ | ≥ |F |/2 poly(log m) = 2 Ω(εn log m) .

Proof of theorem 6: effective encoding.To obtain a scheme with effective encoding and decoding we combine two constructions: the explicit expander from[START_REF] Guruswami | Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes[END_REF] and a pseudo-random graph from the previous section.[START_REF] Bloom | Space-time trade-offs in hash coding with allowable errors[END_REF] The same argument can be presented in a more standard framework, with a read-once input tape and an index tape of poly-logarithmic size. However, we believe that the argument becomes more intuitive when we allow many passes on the input tape.

* Supported in part by grants ANR EMC ANR-09-BLAN-0164-01 and NAFIT ANR-08-EMER-008-01.

We fix an n-element set A in the universe {1, . . . , m}. Now we construct two bipartite graphs G 1 and G 2 that share the same left part L = {1, . . . , m}. The first graph is the explicit (m, s = n 1+δ • poly(log m), d = poly(log m), n, ε)expander G 1 = (L, R 1 , E 1 ) from [START_REF] Guruswami | Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes[END_REF] with an effective decoding algorithm. We do the first two steps from the encoding procedure of the BMRV-scheme explained in Section 2. At first we label all vertices in Γ(A) by 1 and other vertices by 0. Denote the corresponding labeling (which is a n 1+δ • poly(log m)-bits string) by B 1 . Then, we find the list of vertices outside A that have too many 1-labeled neighbors:

We do not re-label neighbors of W , but we will use this set later (to find W effectively, we need the property of effective decoding of the graph).

Let v ∈ L be a vertex in the left part of the graph. There are three different cases:

• if v belongs to A then all neighbors of v are labeled by 1;

• if v does not belong to A∪W , then a random neighbor of x with probability > (1 -ε)d is labeled by 0;

• if v belongs to W , we cannot say anything certain about labels of its neighbors.

Thus, if we take a random neighbor of v and see label 0 in B 1 , then we can say that this point does not belong to A. If we see label 1, then a more detailed investigation is needed. This investigation will involve the second part of the scheme, which we define below. Now our goal is to distinguish between A and W . To this end, we take a pseudo-random graph G 2 = (L, R 2 , E 2 ) specified by a value of a pseudo-random bits generator G m (z) (any of the generators discussed in the previous section is suitable). We need a restricted on W version of the strong ε-reduction property:

For every v ∈ W , at most εd vertices in Γ(v) belong to Γ(A).

Set W is of size at most |A|/2 (Lemma 1), and it can be effectively computed from A (effective decoding property of the graph G 1 ). Hence, for a given z we can check the property above in time poly(n, log m). We know that for the majority of seeds z, the graph G m (z) satisfies the strong ε-reduction property, i.e., all vertices outside A have at most εd neighbors in Γ(A). Though we cannot effectively check this general property (we cannot check it effectively for all vertices in the universe), we are able to check its restricted version (i.e., only for vertices in W ).

Thus, in average time poly(n, log m) we can probabilistically find some seed z such that the restricted (on W ) version of the strong ε-reduction property is true. In the corresponding graph G 2 we label by 1 all vertices in Γ(A), and by 0 all vertices of the right part of the graph outside Γ(A). We denote this labeling (a O(m log 2 n)-bits string) by B 2 and take it as the second part of the data storage. The corresponding seed value z is taken as 'cached' memory.


A Le Gall

R West

L E Bonnefoy

C Leyrat

M A Janssen

E Lellouch

R Sultana

The geological history of Saturn's icy moons and their interaction with the rings as revealed by the Cassini Radar

While it was initially designed to examine the surface of Titan through the veil of its opticallyopaque atmosphere, the Cassini Radar was occasionally used to observe airless Saturn's icy moons, generally from long ranges. In this paper, we give an overview of the Cassini radar and radiometry distant observations of Mimas, Enceladus, Tethys, Dione, Rhea, Iapetus and Phoebe and describe what they have taught us about the geological history of these objects and their interaction with Saturn and its rings.

Introduction

For more than 13 years, the Cassini spacecraft has explored the Saturnian system and revealed the wealth of Saturn's moons providing dramatic images of their surfaces. The mission, which ended less than a year ago, has revolutionized our understanding of these icy objects and taught us that they cannot be regarded as frozen worlds anymore (e.g., [1,2]).

However, the collective formation of these moons and subsequent evolution remains an outstanding problem. All of them are composed largely of water ice [START_REF] Clark | Satellites[END_REF] but their respective history and near environment have led to different regolith composition and structure.

Microwave observations can provide unique insights into the endogenic and exogenic processes that have affected Saturn's moons by putting constrains on the thermal, physical and compositional properties of their subsurfaces. In particular, the Cassini radar, by operating at a wavelength of 2.2 cm [START_REF] Elachi | [END_REF]5], has expanded the observation of the Saturnian icy satellites to a new and revealing length scale, complementary to that probed by the Cassini's Composite Infrared Spectrometer (CIRS) instrument and ground-based radar systems such as the 12.6-cm wavelength Arecibo observatory.

Cassini radar and radiometry distant observations of icy moons

Typical distant Cassini radar observations of Saturn's moons occur at ranges between 50,000 km and 500,000 km where the antenna beamwidth is comparable to or greater than the apparent angular extent of the target's disk. These experiments were designed largely for disk-integrated albedo (measured in the instrument active mode) and average brightness temperature albedo (measured in passive mode) calculation. Ostro et al. (2006Ostro et al. ( , 2010) ) [6,7] report on the distant observations of Saturn's major airless satellites measured at the beginning of the mission. Since then the observational database has significantly increased to a number of 80 active radar distant observations and 40 distant radiometry observations. Though unresolved, Cassini distant radar and radiometry observations have revealed intra-and inter-satellites variabilities which bring clues on what is common and what is specific to the history of each of Saturn's airless icy satellites.

Results

The near-surface emissivity, and the microwave albedo, of Saturn's moons are primarily controlled by the degree of purity of the water-ice regolith [6,7].

At first order, the satellite-to-satellite variabilities and the hemispheric dichotomies shown in Fig. 1 thus reflect subsurface contamination variations resulting from the competition between several effects, including (i) the coating effect of the E-ring (by clean ice) (ii) the coating effect of the vast debris ring from Phoebe (by non-ice compounds) (iii) the geological history of the satellite; and (iv) the efficiency of space weathering at its position within Saturn's magnetosphere.

EPSC Abstracts

Vol. 12, EPSC2018-519- For instance, around Enceladus, the E-ring guarantees the deposition at the surface of extremely clean water ice that may also be structurally complex and thus very favorable to volume scattering. The decrease in radar brightness and concurrent increase in emissivity from Enceladus outward would then be due to the outward decrease in E-ring flux [8] and hence the endowment of the satellite surface with less ultraclean ice.

In this paper, we will examine the microwave signature of each Saturnian moon at 2.2 cm as a testimony of its individual evolution. When possible, these observations will be analyzed in light of observations at other wavelengths or by comparison with radio observations of other icy objects. Our overarching goal is to investigate the age and evolution of Saturn's system which is still a muchdebated subject (e.g., [9]).

Figure 1 :

 1 Figure 1: Radar albedo and emissivity of Mimas, Enceladus, Tethys, Dione, Rhea, Iapetus and Phoebe derived from Cassini radar and radiometry unresolved observations at 2.2-cm wavelength. The emissivities were estimated dividing the measured disk-integrated brightness temperatures by an equilibrium temperature as described in [5]. For each satellite, when available, values are shown separately for the leading and trailing sides. The locations of the E-ring and the vast debris ring from Phoebe are indicated.

Acknowledgements

The authors wish to thank the Cassini-Huygens (NASA/ESA/ASI) team for the design, development, and operation of the mission. This project is supported by CNES.


Arthur Bongrand
email: arthur.bongrand@subatech.in2p3.fr

Samuel Duval
email: samuel.duval@ai4r.comwww

Jérôme Donnard

Julie Champion

A 1 (1h) A 2 (1h)

A 2 (7h)

[…]

→

  InteractionS with Matter and ApplicationsBasic and applied research around 3 main scientific expertise's with potential strong societal impacts: RaMI → Radionucléides Médicaux Innovants -Innovative Medical Radionuclides ✓Health ✓Nuclear medicine ✓Radionuclides IRMa → Interaction Rayonnement Matière -Radiation-Matter Interaction ✓Ion Beam Analysis, materials → IBA platform: visible, X, 𝛾 ✓Non Destructive Testing → Nuclear data X, 𝛾: PIXE/PIGE -High Resolution X-Ray Tomography System ✓Detector development and characterization → profilers, diamond detectors, dosimeters… HB → HadronBiologie -HadronBiology ✓Health, Radiobiology, Dosimetry, Flash Hadrontherapy → In-situ dose monitoring Irradiation platform: proton and α Allows to study and locate in 2D the radioactivity emanating from a sample → Area of interest located at the surface (≈10 µm deep) • Applications → Pre-clinical (oncology + drug discovery) Visualization of molecules or fragments of molecules labeled with radioactive elements → Geology (study of uraniferous rocks, environmental pollution...) • Samples → "Thin" (<1 cm thick) ≈ size of a small sugar square → Can be electroplated on a glass slide, a "sugar", a metal foil… • Specificities of the BeaQuant → Real-time direct counting ✓ Quantification ✓ Tracking Technology Direct gaseous counter Performance •Spatial: α (alpha) 20 µm -β (Beta) 20 µm -High energy β or β + 50 µm •Linearity over 5 orders of magnitude •Sensitivity: 0.0005 cpm/mm 2 (≈ mBq) •Large Field Of View 20x20 cm² Uranium ore sample ( 238 U, 235 U, 234 U) Spatial resolution: 20 µm the contributions of the different elements of the decay chain? The activity of the different α isotopes can be determined at any time! Digital image + Exploitation of time data ↓ localized Identification of the different α isotopes of the decay chain Simultaneously combining autoradiography with a time spectral measurement →

✓

  Promising in the acquisition of nuclear data for the production of radionuclides for nuclear medicine applications like quality control of radiopharmaceuticals ! ✓ A precise tool to understand the temporal behavior of a chain of labeled isotopes ✓ Precise image & quantification from mBq to kBq Arthur BONGRAND More experiments ! → Perform simultaneous comparisons with standard quality control methods → Perform multiple quality controls of the same batch simultaneously using the BeaQuant


Dang Phong Bach

Ludovic Cauvin
email: ludovic.cauvin@utc.fr

Delphine Brancherie
email: delphine.brancherie@utc.fr

Djimédo Kondo
email: djimedo.kondo@sorbonne-universite.fr

SARAJEVO, BOSNIA -HERZEGOVINA MODELING THE SIZE EFFECT IN THE MECHANICAL BEHAVIOR OF NANOCOM-POSITES

Introduction

With the development of smart materials [START_REF] Hamdi | Improvement of the electrical conductivity of carbon fiber reinforced polymer by incorporation of nanofillers and the resulting thermal and mechanical behavior[END_REF] and the constant search for mass reduction, the use of nanocomposites is constantly growing. Indeed, for very low volume fraction of reinforcements and contrary to classical composites, nanocomposites offer remarkable properties, especially mechanical ones. These remarkable properties can be explained by a size effect induced by the nanometric dimension of the reinforcements. The local phenomena present at the matrix-inclusion interface, which are negligible in the case of classical composites, are no longer so in nano-reinforced materials where the ratio (matrixinclusion interface surface) / (material volume) becomes much larger. However, taking into account the size effect in the modeling of the behavior of nanocomposites remains a great challenge at the present time. In the context of linear elasticity, many works, taking into account a size effect of nano-fillers, have been carried out by means of analytical approaches [START_REF] Duan | Size dependent effective elastic constants of solids containing nano-inhomogeneities with interface stress[END_REF][START_REF] Brisard | Hashin-shtrikman bounds on the bulk modulus of a nanocomposite with spherical inclusions and interface effects[END_REF][START_REF] Brisard | Hashin-Shtrikman bounds on the shear modulus of a nanocomposite with spherical inclusions and interface effects[END_REF] using micromechanical models. Compared to classical micromechanical model like the Mori-Tanaka scheme or the Hashin-shtrikman bounds, a coherent interface is introduced on the matrix-inclusion interface and the equilibrium of this interface is taken into account. The behavior of this interface is generally governed by an elastic law as presented by Bottomley et al [START_REF] Bottomley | T Alternative to the Shuttleworth formulation of solid surface stress[END_REF]:

σ s = C s : ε s (1)
where C s is the surface stiffness tensor of the interface, σ s is the surface tangent stress on the interface and ε s is the surface strain tensor on the interface given by :

ε s = P.ε.P (2)
P is the second order projection operator on the interface :

P = I -n ⊗ n (3)
In addition to the classical bulk equilibrium, these analytical approaches take account the equilibrium of the interface through the generalized Young-Laplace equation on the matrix-inclusion interface [START_REF] Povstenko | Theoretical investigation of phenomena caused by heterogeneous surface tension in solids[END_REF][START_REF] Gurtin | A general theory of curved deformable interfaces in solids at equilibrium[END_REF][START_REF] Chen | A general theory of curved deformable interfaces in solids at equilibrium[END_REF]:

div s σ s + σ • n = 0 ∀x ∈ Γ ; Γ being the matrix-inclusion interface. ( 4
)
Because of analytical difficulties, micromechanical models accounting for the size effect of the nanoinclusions are limited to spherical or cylindrical inclusions. To overcome this limitations, numerical strategies have been developed [START_REF] Yvonnet | An xfem/level set approach to modelling surface/interface effects and to computing the size-dependent effective properties of nanocomposites[END_REF][START_REF] Javili | Micro-to-macro transition accounting for general imperfect interfaces[END_REF][START_REF] Bach | Size effect in nanocomposites: Xfem/level set approach and interface element approach[END_REF][START_REF] Bach | An embedded-FEM approach accounting for the size effect in nanocomposites[END_REF]. In this communication, we will present the finite element models we propose in the context of both elastic and non-linear behaviors. Here we consider a bounded domain Ω ⊂ R d (d = 2 or 3) with boundary ∂Ω (∂Ω = ∂Ω F ∪ ∂Ω u and ∂Ω F ∩ ∂Ω u = ∅). ñ is the outward unit normal to ∂Ω. The domain Ω is made of of two phases Ω (1) and Ω (2) corresponding respectively to the inclusion and the matrix. These 2 domains are separated by an imperfect interface Γ (Fig. 1). We note n the unit normal vector to Γ, chosen from Ω (1) to Ω (2) . As considered in analytical micromechanical model accounting for the size effect of nano-inclusions, the interface is assumed to be coherent, which means that the surface stresses are related to the jump of the traction vector across the interface. The equilibrium of the 2 phases Ω (1) and Ω (2) is given by the equation:

Problem definition

divσ (l) + b = 0 in Ω (l) , l = 1, 2 , (5)
where σ is the bulk Cauchy stress tensor and b is a volume force. The Neumann and Dirichlet boundary conditions are applied on ∂Ω:

σ • ñ = F sur ∂Ω F et u = ū sur ∂Ω u , (6)
The equilibrium of the coherent interface Γ is governed by the gereneralized Young-Laplace equation written in eq. ( 4).

Linear and non-linear behavior estimations

Using eq. ( 5) to eq. ( 4), assuming Γ closed and without any debonding between matrix and inclusions, the weak form of the problem presented in section 2. can be expressed:

∀δu Ω\Γ ∇ s δu : σdΩ + Γ ∇ s s δu |Γ : σ s dΓ - Ω\Γ δu • bdΩ - ∂Ω δu • σ • ñdS = 0 . (7)
where On a Representative Volume Element (RVE) (fig. 2) corresponding to the two-phase material problem presented in section 2., using finite element method in plane strain with interface elements, Xfem/level set method or embedded-FEM, the weak form given in eq. ( 7) will be solved by considering linear and non-linear behaviors in the bulk and elastic behavior on the matrix-inclusion interface. Different diameters of the cylindrical inclusions will be considered to study the impact of their size on both macroscopic and microscopic response of the material. These results and first developments considering several physics will be presented during the conference.

∇ s s {•} = ∇ s {•}P, ∇ s {•} being the symmetric gradient operator.

Figure 1 :

 1 Figure 1: Two-phase material with imperfect matrix-inclusion interface.

Figure 2 :

 2 Figure 2: Representative Volume Element (in plan (e 1 , e 2 ) )


Arthur Bongrand

Samuel Duval

Jérôme Donnard

Julie Champion

A digital real-time high-resolution imaging system to quantify and identify all emitted charged particles

→ an accurate up-to-date emission imaging technique !

✓ Allows to study and locate in 2 dimensions the radioactivity emanating from a surface sample at scales until 10 micrometer. ✓ Well suited for pre-clinical TAT: allows understanding and quantifying biodistributions in tissues at high spatial resolution and low activity.

R.O.I. 1D projection

In nuclear decay physics, a radioactive equilibrium exists when a radioactive nuclide decays at the same rate as it is produced.

Bateman equation (general explicit formula)

→ The concentration of daughter nuclei in the radioactive equilibrium can be modeled at any time using the Bateman equation provided that the characteristics of the decay chain and if the initial concentrations are known. → For our application, as these initial concentrations are unknown, we have developed a method to calculate these concentrations from the evolution of the measured count rate.

Count mode

Mean Time mode

Mouse kidney labelled with 225 Ac-PSMA

Mouse kidney labelled with 227 Th (α) 1mm

→ Usually the quality controls are made from a 1D projection where we can distinguish the free 225 Ac which remains on the deposit spot from the labelled 225 Ac which migrates. To limit interpretation errors, the analysis must be performed at secular equilibrium (~7h).

→ The STSAA reduces the time needed for a quality control after elution to only one hour allowing both isotope localization and identification. Thus, the purity is deduced from the ratio of free to labeled 225 Ac.

Digital autoradiography combined with a temporal spectroscopy method allows the quick and accurate identification of different radioisotopes and to observe their localization.

The increased robustness of this method comes from its low dependence on the operator's choices compared to 1D method.

From the results, we can observe the contribution of a radioisotope called "free 213 Bi". Clearly visible on the migration front, free 213 Bi corresponds to 213 Bi which is not radiolabeled and whose parent, 217 At, has not decayed locally. The most probable hypothesis is that the free 213 Bi comes from the mother solution. This free 213 Bi has also been observed in biological samples. Studies are underway to understand its biological impact. A 1 (1h)

Results

Discussion

A 1 (7h) A 2 (1h) […] A 2 (7h) […]

✓✓

  Digital autoradiography → Ability to analyze and reanalyze endlessly the digital data acquired! ✓ Variety of applications: Oncology, Neuroscience, Radio-TLC, Geological Studies, Radio Toxicology… 𝑁 𝑛 𝑡 = 𝑁 1 𝑖 𝑁 𝑖 𝑡 + 𝜆 𝑖-1 𝑁 𝑖-1 𝑡 𝑑𝑁 𝑘 𝑡 𝑑𝑡 = 𝜆 𝑘-1 𝑁 𝑘-1 𝑡 Vancouver, Canada; 4-11 November 2023 2023 IEEE Nuclear Science Symposium (NSS), Medical Imaging Conference (MIC) & Room Temperature Semiconductor Detector (RTSD) A digital real-time high-resolution imaging system to quantify and identify all emitted charged particles A. BONGRAND 1 , S. DUVAL 2 , J. DONNARD 2 , J. CHAMPION 1 1: Laboratoire Subatech, IMT Atlantique, Nantes Université, CNRS/IN2P3, France 2: S.A.S. Ai4R, France arthur.bongrand@subatech.in2p3.fr Currently, the characterization of the nature and spatial distribution of radionuclides in a sample is time consuming and fastidious. Indeed, it necessarily requires the use of two distinct analytical techniques and detectors of different nature. Moreover, the spatial resolutions of the two methods are often detector dependent, which makes it difficult to integrate and interpret these two measurements together. Can we perform a fast and accurate quality control of radiopharmaceuticals with a single system? References [1] N. Gillings et al., EANM guideline on the validation of analytical methods for radiopharmaceuticals, EJNMMI Radiopharmacy and Chemistry, 2020. [2] C.B.L. Victorio et al., TSPO expression in a Zika virus murine infection model as an imaging target for acute infection-induced neuroinflammation, Eur J Nucl Med Mol Imaging, p. 742-755, 2023. [3] H. Lefeuvre et al., « Spectroscopic autoradiography of alpha particles using a parallel ionization multiplier gaseous detector », Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment, vol. 1035, p. 166807, 2022. Promising in the acquisition of nuclear data for the production of radionuclides for nuclear medicine applications like quality control of radiopharmaceuticals ! ✓ A precise tool to understand the temporal behavior of a chain of labeled isotopes. ✓ Precise image & quantification from mBq to kBq. More experiments ! → Develop standard methods for quality control.→ New field of application, source control, contamination, environmental studies.→ Set up of AIDA Lab, a common laboratory with Inserm U982.

Acknowledgments

We thank the GIP Arronax for providing of their facilities and a 225 Ac-PSMA source, especially Dr. Cyrille Alliot for his excellent expertise in the field of radiopharmaceutical quality control.