Juan Pablo Timpanaro
email: juanpablo.timpanaro@inria.fr

Isabelle Chrisment
email: isabelle.chrisment@loria.fr

Olivier Festor
email: olivier.festor@inria.fr

on Peer-to-Peer Computing Monitoring Anonymous P2P File-Sharing Systems

Keywords: Distributed monitoring, Large scale monitoring, I2P, anonymous networks

I. MOTIVATION

Anonymous communications have been exponentially growing [START_REF] Festor | The home for NetDB statistics[END_REF], [START_REF]Tor Metrics Portal[END_REF], where more and more users are shifting to a privacy-preserving Internet and anonymising their peer-topeer communications [START_REF] Stevens | One bad apple spoils the bunch: exploiting P2P applications to trace and profile Tor users[END_REF]. Anonymous systems allow users to access different services while preserving their anonymity. We aim to characterise these anonymous systems, with a special focus in the I2P network [START_REF]The I2P network[END_REF].

Current statistics service for the I2P network [START_REF] Festor | The home for NetDB statistics[END_REF] do not provide values about the type of applications deployed in the network nor the geographical localisation of users. Our objective is to determine the number of users in the network, the number of anonymous applications, and the type of those applications. We also explore the possibility of inferring which group of users is responsible for the activity of an anonymous application. Thus, we improve the current I2P statistics and get better insights of the network.

II. I2P MONITORING APPROACH

The information about an I2P node1 is grouped in a structure called routerinfo, which includes its contact information (IP address and port), encryption keys, among others. The information regarding an I2P application is gathered in a structure called leaseset. Therefore, an I2P user running two anonymous applications has one routerinfo and two leasesets.

The I2P network guarantees the unlinkability between a routerinfo (defining a user) and a leaseset (defining an applications). We propose a correlation analysis between the behaviour of users and applications. This analysis can allow us to assert in which measure a particular set of users contributes to the overall activity of an anonymous applications.

The I2P network uses a Kademlia-based distributed hash table, called netDB, to store network metadata, that is, every routerinfo and leaseset. This database is formed by normal I2P nodes with high bandwidth rates, called floodfill nodes. These I2P nodes, or floodfill nodes, participate in the network as every other node, and additionally store network metadata. In the current I2P network, these floodfill nodes account for We exploit the netDB and place a set of floodfill nodes. These nodes allow us to collect a vast amount of network metadata, which is analysed to characterise I2P users (by analysing routerinfos) and I2P applications (by analysing leasesets).

Figure 1 depicts our monitoring architecture. Monitoring floodfill nodes are deployed in the I2P's netDB, analysing every routerinfo and leasesets they retrieved. The result of these analyses are stored, for a later correlation analysis. Finally, the aggregation of these results are displayed in our statistics web site 2 .

Our monitoring architecture is completely flexible. Due to the autonomous nature of floodfill nodes, we can increase the number of monitoring floodfill nodes on demand, improving the amount of network metadata we receive, thus enhancing our monitoring results.

III. EXPERIMENTS

This section presents the number of users and the number of anonymous file-sharing applications during our measurements. We additionally present a correlation analysis to determine in which extent the users from Moscow contribute to the I2P's anonymous file-sharing activity.

A. Experimental setup

We deployed our monitoring architecture for a period of one week, from 2013-03-15 CEST to 2013-03-21 CEST. We use seventy monitoring floodfill nodes, which in the current

C. Countries & Cities analysis

Figure 3 presents the most active countries in the I2P network: Russia, The United States, Germany and France. Russia was the most active country in the network, with an average of 3500 users. During the entire one-week experiment, we detected 159 countries and 13547 cities. That indicates that the I2P network is widely deployed and distributed all over the world.

D. Correlation analysis

Our goal is to determine in which measure the users detected contributed to the anonymous file-sharing activity. We are dealing with data of type ratio [START_REF] Stevens | On the Theory of Scales of Measurement[END_REF], where Pearson's correlation coefficient is adequate. For the correlation analysis we extended our period of analysis on one week, from 2013-03-15 CEST to 2013-03-30 CEST. We consider that three weekends is a good time window to detect a longlived correlation between a particular city and a particular application. We took into account the top detected city, Moscow, and the top detected file-sharing application, I2PSnark. Figure 5 plots the data with the number of users from Moscow in the x-axis and the number of detected I2PSnark applications in the y-axis. The plotted data complies with Pearson's data requirements (data normality, linearity, and homoscedasticity). The correlation value is r = 0.4901 and indicates a strong correlation, where the coefficient of determination3 is r 2 = 0.2401 and indicates that users from Moscow contributed to the 24% of the total I2P's file-sharing activity for the fifteen-day period.

Fig. 1 .

 1 Fig. 1. Monitoring architecture

Fig. 3 .Figure 4

 34 Fig. 3. Top four active countries

Fig. 4 .

 4 Fig. 4. Top active cities

Fig. 5 .

 5 Fig. 5. Correlation analysis for Moscow

  Figure 2 displays the individual number of active filesharing applications during the duration of our analysis, forIMule and I2Phex clients. We can observe that IMule and I2Phex clients hardly presented any activity, and I2PSnark was the most deployed file-sharing client. We can additionally observe that the use of I2PSnark clients increased during the weekend (from 16/03 to 17/03).

					13-th IEEE International Conference on Peer-to-Peer Computing
	netDB, account for nearly the 12% of the total number of
	floodfill nodes.
	B. I2P's file-sharing applications
		300	I2PSnark	Imule		I2Phex
		250
		200
	Apps	150
		100
		50
		0
		15/03	16/03	17/03	18/03	19/03	20/03	21/03
		Fig. 2. Detection of I2P's file-sharing applications
								2 Accessible at www.i2pstats.loria.fr.
	978-1-4799-0521-8/13/$31.00 c 2013 IEEE		1

An I2P user runs an I2P node. We employ I2P user and I2P node indistinctively throughout this document.

The coefficient of determination explains the variance of the data, i.e. how much of the variance of the y-axis can be explained from the variance of the x-axis.978-1-4799-0521-8/13/$31.00 c 2013 IEEE


Bertrand Simon
email: bertrand.simon@uha.frolivier.haeberle@uha.fr

Olivier Haeberlé

Multi-kernel deconvolution applied to confocal fluorescence microscopy with engineered point spread function

Keywords: point spread function engineering, multi-kernel deconvolution, confocal fluorescence microscopy

Multi-kernel deconvolution applied to confocal fluorescence microscopy with engineered point spread function

Introduction

At the end of 19 th century, Ernst Abbe [1] introduced for conventional microscopy his resolution criterion as: R Abbe = 0.5λ/NA , (1) with λ being the wavelength of observation and NA being the numerical aperture of the objective, defined as NA = n sinα. In this formula, n represents the index of refraction of the observation medium, and α is the maximum angle of collection of the objective. The Abbe resolution criterion is in fact nothing else than the Full Width at Half Maximum (FWHM) of the detection Point Spread Function (PSF) of the objective, calculated using the scalar approximation of diffraction. For decades, the resolution limit was explained by the Abbe formula. However, the Abbe limit assumes that all points of an object emit light in the same manner.

One had to wait the invention of the confocal microscope by Marvin Minski [2] to get a first breakthrough. In a confocal microscope, the specimen is not anymore uniformly illuminated, but using a focalized beam, and a detection pinhole cutting most of the out-of-focus light.

A probabilistic interpretation of the detection process gives a simple explanation of the improved resolution in confocal microscopy. In a wide-field microscope, the probability for a photon to reach the detector is given by the product of the probability of the photon to be created (equal to one, because of the uniform excitation) by the probability for the photon to be detected P d , which is described by the detection PSF det . In a confocal microscope, the probability of excitation P e is modeled by the excitation PSF exc , so that the confocal PSF is in first approximation simply given by multiplying the illumination PSF ill by the detection PSF det (the detection PSF det being even wider because of the Stokes shift).

Multiplying both PSFs leads to a lateral resolution improvement of about 40%, for an infinitely small pinhole. However in practice, in order to efficiently collect fluorescence photons, one must open the pinhole to a size similar to the Airy disk. As a consequence, the gain in lateral resolution is usually much smaller, the main interest of the confocal setup being its better optical sectioning capabilities, compared to a wide field microscope.

Mats Gustafsson has proposed [3,4] another technique called structured illumination, which permits to improve the lateral resolution by a factor of two in a wide field microscope, so even beating confocal microscopy. Confocal microscopy may in fact also be considered as a structured illumination technique, the illumination being reduced to a focalized excitation spot. Structured illumination however is a widefield technique using a sinusoidally modulated excitation, and does not require a detection pinhole. As a consequence, it also has the advantage (compared to confocal microscopy) that no emitted fluorescence is discarded. Structured illumination however requires taking several images of the same specimen (typically 7 to 9 for two dimensional imaging [3]) to recompose a resolution-improved image, which may be a drawback for bleaching-sensitive dyes.

The aim of this work is to show how the same gain of a factor of two in lateral resolution (compared to Abbe's limit) may be obtained in a confocal microscope, with a technique using three laterally interfering excitation PSF ill in order to decrease the spatial extension of the total PSF along one spatial direction, and a recombination of typically four images of the same sample, observed with different orientations of the narrowed PSF.

Structured illumination in fluorescence microscopy

Several techniques to use structured illumination in fluorescence microscopy have been proposed in the literature. We here briefly recall them, in order to highlight their common features and differences.

Axially structured illumination: wide-field interfering beams

In a standing wave fluorescence microscope, the excitation consists of two counter propagating plane waves, which form by interference a standing wave [5,[START_REF] Bailey | Proc SPIE[END_REF]. The axial modulation produces a Moiré pattern, which mixes axial high space frequencies (normally lost into the so-called "missing cone") into the limited set of special frequencies one can usually acquire with a given objective. In order to demodulate this mixed information, one must acquire three different images with different phases of the standing wave [5,[START_REF] Bailey | Proc SPIE[END_REF]. However, a set of intermediate frequency is not mixed into the observation space by the Moiré effect, which makes 3-D reconstructions problematic in some cases [START_REF] Krishnamurthi | Proc SPIE 2655[END_REF][START_REF] Nagorni | [END_REF].

A variant of standing wave illumination is the so-called I 3 M or incoherent interference illumination microscopy [START_REF] Gustafsson | Proc SPIE[END_REF], which uses two opposing objectives in order to focus illumination light. It is also a widefield technique, and provides better axial sectioning capabilities than standing wave microscopy. However, I 3 M still presents missing frequencies along the optical axis [START_REF] Nagorni | [END_REF].

Axially structured illumination: focused interfering beams

An alternate to I 3 M is to use a coherent, focused illumination from two opposing objective, in a configuration called 4Pi microscopy of type A [START_REF] Hell | [END_REF]. In order to improve the imaging capabilities of the 4Pi microscope of type A, one usually couples the 4PiA illumination scheme with a coherent detection of the fluorescence through both opposing objectives (4Pi type B) in a configuration called 4Pi type C [11].

The main advantage of 4Pi microscopies is that being scanning techniques, the reconstruction of the observed object is straightforward, the remaining side lobes being removed by a simple inverse filtering technique [START_REF] Hell | Increasing the resolution of far-field fluorescence light microscopy by point-spreadfunction engineering[END_REF]. Being a scanning technique, it may however be slower than wide-field techniques like

I 3 M.
The most noticeable feature to be remembered is that these optical set-ups (I 3 M, 4Pi) do not in fact provide a gain in lateral resolution compared to a regular confocal microscope when used at its optimum.

Laterally structured illumination: wide-field interfering beams

It is also possible to improve the lateral resolution in wide-field microscopy by the technique of structured illumination, using two interfering illumination beams [START_REF] Gustafsson | [END_REF] or with a diffraction grating [START_REF] Heintzmann | Proc. SPIE[END_REF]. In this technique, a Moiré effect is used to code normally undetected information, carried by high frequency spatial components, into the detectable region of spatial frequencies. As for standing wave or I 3 M, one has to take several images of the specimen in order to decode the information. The technique has been demonstrated in 2-D, and it has been shown that the lateral resolution limit (Abbe criterion) can be surpassed by a factor of two [3,4].

The main advantage of this technique is that no light is discarded by a pinhole, so that it is very efficient. Being a wide-field technique, it also permits fast acquisition. The mathematical processing of the images is also fast compared to deconvolution techniques. However, in order to obtain a gain in resolution in all direction, typically 9 images of the same specimen of the specimen must be taken and processed [3]. Similarly, a 2-D spatial modulation may be used [START_REF] Frohn | Proc. Natl. Acad. Sci[END_REF].

Laterally structured illumination: focused interfering beams

In Ref. [START_REF] Haeberlé | [END_REF], we have described various schemes, which permit to decrease the lateral extension of the illumination PSF ill in a confocal microscope. We here briefly recall the main points of a technique, which is, compared to laterally structured illumination with wide-field interfering beams what 4PiA is, compared to I 3 M, to axially structured illumination.

We consider for computing PSF ill the vectorial model of Haeberlé, as described in Refs. [17][18][19]. The detection PSF det is computed using the vectorial dipole model of Haeberlé et al. [20,21]. When using a xpolarized incident beam, the three components of the electromagnetic field at point P(x,y,z) in the specimen are given by (with φ p in spherical polar coordinates):

E x = -i(I 0ill + I 2ill cos2φ p ) , E y = -i(I 2ill sin2φ p ) , E z = -2I 1ill cosφ p . (2)
A detailed description of how to compute the three diffraction integrals I 0 , I 1 and I 2 , is given in

Refs. [17][18][19][20][21][22].

Figure 1 describes the considered configuration, with three x-polarized incident beams giving rise to three PSF ill slightly shifted along the y-axis. As explained in Ref. [START_REF] Haeberlé | [END_REF], a substantial narrowing of the central Airy disk may be obtained by properly shifting and dephasing both lateral spot.

Figure 2 shows the computational results for an illumination wavelength λ ill = 400 nm, using a special NA=1.65 objective combined with a special preparation of the 2-D sample, as explained in Ref. [START_REF] Haeberlé | [END_REF]. It is important to note that with this three-beam illumination configuration, the confocalization process does not significantly improve the resolution along the y-axis, as illustrated by Figure 3, which shows PSF ill , PSF det and PSF conf computed for a more conventional NA=1.2 water immersion objective, considering λ ill = 400 nm and λ det = 500 nm, and using a standard (170 µm thickness, n=1.525) cover glass, and imaging into a watery specimen. The central spot of PSF ill has a y-width of 104 nm while the Abbe criterion gives 208 nm for this configuration. This shows that a factor two in resolution can be expected from a confocal microscope, compared to the Abbe limit, using a structured point spread function. This is the same factor two that was already demonstrated in classical fluorescence microscopy using a wide-field structured illumination [3]. Confocalizing then only marginally improves the resolution, and PSF conf has a FWHM of 100 nm. The remaining side-lobes may induce the apparition of ghost images surrounding the main image, as for example in 4Pi-confocal microscopy [START_REF] Hell | [END_REF]. It has however been shown that fast linear filtering is sufficient to effectively remove these ghost images [START_REF] Hell | Increasing the resolution of far-field fluorescence light microscopy by point-spreadfunction engineering[END_REF].

However, with this three-beam illumination scheme, the asymmetry of PSF conf remains important, as can be noticed on Fig. 2(d). As a consequence, images acquired with such a structured PSF ill will present an optimally improved resolution along the y-axis only, which is unfavorable in practice. Only for 1-D specimens, like for example DNA fragments or microtubules deposited on a glass slide could such a mono-axis gain in resolution be really helpful.

We show in the next section how the combination of several images improved along one different axis each may permit to obtain a true 2-D resolution improvement, and apply the image processing approach we propose to this later case of confocal PSF engineering.

Image processing: multikernel deconvolution

In the previous section, we have shown the possibility to improve the lateral resolution in confocal fluorescence microscopy using an interfering three-beam illumination. We have seen that the gain in resolution is up to a factor of two, but along one direction only. One may however take several images of the same specimen, with improved resolution along different directions. Data fusion techniques can then be used to recombine these images in order to benefit from the resolution enhancement along all spatial directions. Another approach is deconvolution. One may first deconvolve individually each image, and then recombine them. We propose to use a combined approach, called multi-kernel deconvolution.

Each recorded image I(X) can be described by the following convolution equation:

I(X) = H(X -X 1 )O(X 1 -∞ +∞ ∫ )dX 1 ⊕ b(X) (3)
where X and X 1 are 3-D coordinates, H(X) describes the Point Spread Function (PSF) of the acquisition system and O(X) is the original object. The term b(X) represents a combination of noise sources due to the fluorescence process and the acquisition electronics. In the frequency domain this equation can be rewritten as:

ˆ I (ω x ,ω y ) = ˆ O (ω x ,ω y ) × ˆ H (ω x ,ω y ) + ˆ b (ω x ,ω y ) . ( 4
)
In the frequency domain, the Optical Transfer Function (OTF) ˆ H behaves as a filter, which only partly transmits the object spatial frequencies. The resolution improvement along the y-axis when using a three-beam confocal PSF can be interpreted as a better transmission of higher frequencies along this axis by the microscope. Better transmission means that the support of the transmitted frequencies is larger (because of the confocalization effect when comparing to a wide-field microscope), and within this extended support, the attenuation of higher frequencies is lower when using a three-beam illumination than when using a regular confocal illumination. Making several acquisitions with different orientations of the three-beam illumination will result in several images showing differently orientated enhanced details. which is indeed obtained when using x-polarized beams, while y-polarized beams (θ=90°) permit a better resolution along the x-axis, so that vertical details are more noticeable, as for example the letter λ is more visible in Fig. 4(g) than in Fig. 4(e).

In order to simultaneously deconvolve several images keeping the best of each, Ghiglia [23] proposed a multikernel deconvolution approach. This technique permits to take into account the diversity of information obtained during the acquisition of a series of image of a same object with several transfer functions. More over, it makes it possible to be released from an important constraint of the deconvolution process related to the fact that the transfer function of an imaging system contains zeros, which implies the loss of certain object spatial frequencies. Indeed, in our case, each transfer function presents zeros, which are located in different directions, and a part of the frequencies lost in one image is theoretically recoverable from another image.

Goudail et al [24] studied multikernel deconvolution with the aim of quantifying the efficiency and the robustness of such a technique. They adapted a Thikonov regularized deconvolution filter to the multikernel deconvolution problem. We propose to use their approach in the case of the laterally compressed PSF. We consider the acquisition of a series of k images of a same scene O convolved by the k kernels resulting from k successive rotations of the direction of polarization of the three-beam excitation PSF. Reeves et al. [25] write the classical Thikonov regularized deconvolution operator as:

ˆ ′ O (ω x ,ω y ) = ˆ H k (ω x ,ω y ) × ˆ I k (ω x ,ω y ) k=1 n ∑ ˆ H k (ω x ,ω y ) 2 k=1 n ∑ + λ L(ω x ,ω y ) 2 , ( 5
)
where Ô' represents the estimated Fourier transform of the object, L is the transfer function of a classical Laplacian filter, and λ is a scalar variable that makes it possible to balance the effect of L, ˆ H k and ˆ I k being the successive OTFs (or kernels) and images, respectively.

We applied this multikernel deconvolution method on different series of numerically simulated images. Figure 5 shows the same binary object than Figure 4 Another important limiting parameter for image deconvolution is noise. Indeed, catastrophic amplification of noise may occur, which may render the deconvolution result useless. An important point in order to get optimal results is to determine the optimal level of regularization of the deconvolution process with respect to the noise present in the image [26].

The case of multikernel deconvolution is slightly more favourable. Indeed, it can be considered that each image of the series is perturbed by an independent noise realization. Goudail et al. [24] studied the advantage of the multikernel approach with respect to the robustness to noise in the case of two-kernel deconvolution. Their conclusions highlight the positive effect of noise averaging permitted by this approach: because the algorithm is based on the addition of several processed images (see Eq. ( 5)). As a consequence, one may expect an increase of the robustness of the inversion process with respect to the noise by taking a larger number of images with different kernels. So the benefit of multikernel deconvolution with narrowed PSFs is double, permitting not only a better final resolution by combining several views of the same specimen, but also a lower sensitivity to noise.

In Figs. To perform these monokernel deconvolutions, one simply uses Eq. ( 5) with n=1. In order to provide a fair comparison, Figs. 6(h)-(j) are obtained averaging 4 monokernel deconvolutions, in order to minimize the effect of noise, as the multikernel algorithm does.

In each case, the result of a 4-kernel deconvolution is of higher quality than that based on monokernel deconvolution. While not always clearly visible by eye (a thorough examination shows that Fig. 6(i) obtained for 20 dB SNR of noise monokernel deconvolution has similar quality than Fig. 6(g), obtained with multikernel deconvolution, but for a 3 dB SNR), the use of a quantitative measurement between the original object and the reconstructed one clearly shows this property of multikernel deconvolution. In order to highlight these better restoration capabilities of multikernel deconvolution combined with narrowed three-beam PSF conf acquisitions compared to monokernel deconvolution with regular PSF conf acquisitions, we show on Fig. 7 the quadratic error computed between the original and the restored objects, and plotted as a function of the filtering parameter λ, for 4-kernel deconvolutions (solid line) and for monokernel deconvolutions (dashed line), with a SNR of 20 dB (Fig. 7(a)) and 3 dB (Fig. 7(b)). The results presented on Fig. 6 indeed correspond to optimal deconvolutions obtained at the minimum of these curves.

The optimal level for the filtering parameter λ is different for each case, but the quadratic error at the optimum is lower, for both levels of noise, when considering 4-kernel deconvolution compared to monokernel deconvolution (Same conclusion holds when considering multi-and monokernel deconvolutions without noise in the images).

Furthermore, the quadratic error for multikernel deconvolution is lower than the absolute minimum for monokernel deconvolution, and this over a large range for the filtering parameter λ (as shown by the dotted rectangles), showing that multikernel deconvolution, even if not performed at its best, gives better results than monokernel deconvolution. This may be of importance in practical cases, because biologists are often not specialists of image processing techniques, but multikernel deconvolution would then offer a supplemental margin of error in the choice the filtering parameter. The results we obtain confirm in the case of asymmetric PSFs those obtained by Goudail et al. [24] who considered multikernel deconvolution with symmetric PSFs, but of different sizes.

Another important property of multikernel deconvolution, which was enlighten by Goudail et al. [24] is the robustness of this technique with respect to the exact knowledge of the PSFs, which are used for deconvolution. In our case, taking several images of the sample would require a precise rotation of this sample. We studied the effect of angular errors, which may affect the actual angular positions of the sample with respect to the ideal ones, in the case of 4-kernel deconvolutions, wich are supposed to be taken at angle 0°, 45°, 90° and 135°, respectively. We have applied a systematic angular shift to the PSFs used for deconvolution compared to the PSFs used to simulate the images. Figure 8(a) shows the quadratic error computed between the original image and the deconvolved image as a function of the parameter λ, for a SNR of 3 dB and for increasing angular errors. One can notice that, except for low values of the regularization parameter λ, for which multikernel deconvolution fails to give satisfactory results, the residual error in image reconstruction is always much lower for multikernel deconvolution with kernel misalignments than for monokernel deconvolution, even if slightly higher than for multikernel deconvolution with correct kernels. This is true even for a very large kernel misalignment of 20°.

This a priori surprising result may however be easily explained if one considers the "equivalent" PSFs, first PSF eq obtained by simply adding, the 4 narrowed PSFs used for acquisition simulations, then PSF eq-err adding the 4 narrowed PSFs with orientation errors. Figure 8(a) recalls the original narrowed PSF. Figures 8(b) and 8(d) display PSF eq for 2-kernel and 4-kernel deconvolution, respectively. The summation process clearly supports the central regions of each narrowed PSF, which add up, while the extensions are angularly regularly distributed, and as a result, of much lower intensity than the central peak (typically 4 times lower for 4-kernel deconvolution). As a consequence, PSF eq for 4 kernels is almost circular symmetric. Obviously, same conclusion holds for the "equivalent" OTF, which is used in the Thikonov equation (5). When the narrowed PSF used for multikernel deconvolution are by inadvertence rotated, the tails are also rotated, but the central region, where the PSFs sum up, is in fact almost identical. As a consequence, not only is multikernel deconvolution still possible, but furthermore, the high frequency content of this "equivalent" PSF being still enhanced, compared to a regular PSF, better results are obtained with multikernel deconvolution, even with large kernel estimation errors.

Note that for a 2-kernel deconvolution, not only are the results of lower quality than for a 4-kernel deconvolution (see Fig. 5), but it also would be more sensitive to angular rotation errors, as the "equivalent" PSF is not circular symmetric (see Fig. 8(c)).

Interestingly, the lower error obtained for multikernel deconvolution is again possible over a large range over the filtering parameter λ (but narrower than with no error on the kernel), which shows that multikernel deconvolution is robust to simultaneously kernel evaluation errors and the filtering parameter choice.

Again, this result about the robustness to errors in estimation of kernels, obtained in the case of asymmetric PSFs, recalls those obtained by Goudail et al. [24] who considered multikernel deconvolution with symmetric PSFs, but of different sizes, and confirms, for confocal fluorescence microscopy, the advantage that multikernel deconvolution with different engineered PSFs would have over averaging deconvolutions performed with a regular PSF, or over multikernel deconvolutions with the same regular PSF.

Discussion

We now detail some advantages and drawbacks of our approach, compared to other, more better established, methods to improve the resolution in fluorescence microscopy, and conclude by mentioning some types of fluorescence microscopies, which may benefit from multikernel deconvolution.

Advantages and drawbacks of the proposed method

In a previous paper, we demonstrated that lateral interfering excitation beams permit to narrow the excitation PSF ill by a factor two in a confocal microscope. This gain is however along one axis only, because of the polarization properties of focalized beams. We have shown that combined with multikernel deconvolution, it is possible to recover an enhanced resolution along both the x-and y-axes.

The axial resolution however is not enhanced with this technique, which is adapted to very shallow specimens. But the lateral interference scheme we consider may be combined with longitudinal interferences appearing when propagating beams passing through two opposing lenses interfere, as in the 4Pi microscope of type A. λ det = 500 nm, considering x-polarized excitation beams, and unpolarized detection). Note that the lateral lobes are better suppressed than the longitudinal ones. However, efficient filtering techniques to remove the ghost images due to these remaining longitudinal lobes have already been developed [START_REF] Hell | Increasing the resolution of far-field fluorescence light microscopy by point-spreadfunction engineering[END_REF]. This result shows that it should be possible to obtain an improved resolution along the z-axis and along the y-axis, simultaneously. Then multiple acquisitions combined with a multikernel deconvolution should permit to obtain the same resolution gain in the third dimension.

We have in fact shown that three-beam excitation confocal microscopy may offer the same lateral resolution than linear structured illumination, which also uses a multiple images acquisition process.

Structured illumination has the important advantage that, being a wide-field technique, it induces no loss of photons, which is precious in case of bleaching sensitive dyes. Also, non-linear (saturated) structured illumination has proven to deliver an even better resolution [START_REF] Gustafsson | Proc. Natl. Acad. Sci[END_REF]. The method we propose has the drawback of possibly increased bleaching (because of the intense lobes of the excitation PSF ill ), but has the advantage that it may be used with two-photon sensitive dyes, which indeed cannot be used with structured illumination, because the high intensity needed to induce two-photon fluorescence renders the use of focalized beams mandatory. Furthermore, the use of two-photon excitation in fact induces a loss in lateral resolution, because doubling the wavelength imposes a widening of the Airy disk, which is not compensated by the non-linear squaring of the illumination PSF to take into account the two-photon process. As a consequence, our method has the important advantage that it may permit to compensate for this inevitable loss in lateral resolution in two-photon microscopy. In particular, available 4Pi microscopes are currently used in combination with two-photon excitation in order to minimize the secondary longitudinal lobes, and therefore may potentially benefit from our technique.

Possible extensions of the proposed method

The best results in STED microscopy in terms of resolution have been in fact obtained with an asymmetric PSF, resulting from an excitation PSF depleted by a STED beam presenting a one-direction valley of depletion [START_REF] Wesphal | [END_REF]. With this method, a physical resolution of 40 nm has been obtained, which could even be improved to 28 nm by deconvolution. This spectacular result was however possible along one direction only. If one could obtain with this technique several images of the same specimen, with different orientations of the 1-D valley of depletion, then the method we propose may permit to reconstruct a 2-D specimen with the unsurpassed resolution, which was obtain in 1-D.

Another technique, which may benefit from multikernel deconvolution, is Multiple Imaging Axis Microscopy (MIAM) [29]. Usually, to image large specimen, one has to use low numerical aperture-, long working distance objectives. The images present a bad resolution along the optical axis, because the PSF of such objectives is strongly elongated along this axis, resulting in a marked anisotropy in resolution. In the MIAM approach, 4 such objectives are used in a tetrahedral configuration to image the large fluorescent specimen under 4 different directions. The 4 resulting 3-D images are then recombined (in fact simply summed-up in the original paper [29]), in order to compensate the low resolution along the optical axis of each objective by the good transverse resolution from the three other objectives. This situation is a direct extension in 3-D of the method we propose in this paper for 2-D specimens. The 3-D extension of the multi-kernel algorithm we consider (Eq. ( 5)) is indeed straightforward.

Similarly, the confocal microscope, even at high NA, suffers from an anisotropic resolution. If one could succeed in obtaining several 3-D images from the same microscopic specimen (for example, using a micro-glass tube like in Ref. [30], but rotating the tube, instead of using 2 imaging devices), multikernel deconvolution could then permit to reconstruct an improved-, isotropic-resolution 3-D image of this specimen.

Selective Plane Illumination Microscopy [31] is another technique developed to image large specimen with a high resolution. With this technique, numerous images of the same sample are taken using a rotating stage, and recombined in 3-D using Fourier space data fusion. The resolution with a low numerical aperture, long working distance objective is quasi-isotropic, thanks to a sectioning of the detection PSF by a planar sheet of light for illumination. A slight anisotropy may however still remain, depending on the thickness of the light sheet, which is used, and the numerical aperture of the objective.

This technique may therefore also benefit from multikernel deconvolution techniques, which would permit to obtain a true isotropic resolution while probably also allow to decrease the number of images to be taken.

Figure Captions

Figure 2 (

 2 Figure 2(a) shows the illumination PSF ill for a "regular" confocal microscope with x-polarized illumination. Figure 2(b) shows the corresponding confocal PSF, modeled by the product of the illumination PSF ill and the detection PSF det , when observing at λ det = 500 nm (for example considering the Bis-ANS (B153) tubulin from Molecular Probes). The detection PSF det is computed considering random polarization emission.

Figure 2 (

 2 Figure 2(c) shows the PSF ill computed using the three-beam illumination scheme we propose. The central spot is much narrower than the spot on Fig. 2(a), as expected, but the presence of two strong lateral lobes renders confocalization mandatory to suppress them (see Figure 2(d)).

Figure 4

 4 Figure4illustrates this behaviour with simulations. In this section, all computations are performed considering a NA=1.2 water immersion objective, with λ ill = 400 nm and λ det = 500 nm. The object O represents the famous Abbe formula (Fig.4(a)). Figures4(b-d) represent three-beam confocal PSFs from interfering beams linearly polarized at θ=0°, 45° and 90° with respect to the x-axis, respectively,

  , whose acquisitions have been simulated for n=2 and θ=0° and 90°, n=4 and θ=0°, 45°, 90° and 135°, and finally for n=8 in steps of 22.5°. The results of the multikernel deconvolution are shown on Figs. 5(b) to 5(d), respectively. Note that if, as expected, a large number of acquisitions (8 for Fig.5(d)) permits an excellent reconstruction of the original object, even with only four different acquisitions, one can perfectly recognize the original formula in Fig.5(c). It is indeed important in practice to keep the mandatory number of acquisitions as low as possible, because of photobleaching effects, induced phototoxicity, or simply speed of acquisition for live specimens, which may slightly move over a long period of observation. If a priori information about the specimen is given, for example the orientation of fibres, DNA fragment or microtubules, one may choose the polarization orientation so as to minimize the number of acquisitions by orienting the PSF along the directions of the significant spatial frequencies needed to properly reconstruct the object.

  6(b)-(d) we show the simulation of acquisitions of Fig. 6(a) taken with different signal to noise ratios, respectively no noise, 20 db and 3 dB SNR and for a three-beam-excitation confocal kernel oriented at θ=90°. Figs. 6(e)-(g) show the results of 4-kernel deconvolutions, based on 4-image series acquired with kernels oriented at θ=0°, 45°, 90° and 135°, and with no noise, 20 db and 3 dB SNR respectively. For comparison, Figs. 6(h)-(j) show the results of monokernel deconvolutions of the simulated images, which would have been obtained for a conventional x-polarized confocal PSF with same noise ratios.

  Figures 9(a) and 9(b) display lateral and longitudinal sections through the confocal PSFs for a regular confocal microscope and a 4Pi type A confocal microscope, respectively.

Figure 9 (

 9 Figure 9(c) shows the excitation PSF ill of a 4Pi type A tribeam microscope, and Fig. 9(d) displays its confocal PSF (all figures are computed for a NA=1.2 water immersion objective, with λ ill = 400 nm and

Fig. 1 :

 1 Fig. 1: Scheme to construct interferences between three point spread functions, resulting from three xpolarized beams, and slightly shifted along the y-axis. Both lateral PSFs are dephased by π relatively to the central one. At points M and M', destructive interferences occur, which results in a narrower central PSF.

Fig. 2 :

 2 Fig. 2: (a) Illumination PSF ill for a x-polarized one-beam illumination. (b) corresponding confocal PSF conf . (c) Illumination PSF ill for a three-beam illumination as described in Fig. 1. (d) corresponding confocal PSF conf . The side-lobes are suppressed. For all figures: N.A. = 1.65, λ ill = 400 nm, λ det = 500 nm. The (x-y) arrows are 200 nm long.

Fig. 3 :

 3 Fig.3: Profiles along the y-axis for: the excitation PSF ill with a three-beam illumination (solid line), the unpolarized detection PSF det (dashed line), and the final confocal PSF conf (dotted line). The lateral lobes of the illumination PSF ill are largely suppressed by confocalization.

Fig. 4 :

 4 Fig. 4: Simulated images with a rotating 3-beam PSF. (a): original numerical object. (b-d): three-beam confocal PSFs from interfering beams linearly polarized at θ=0°, 45° and 90° with respect to the x-axis,

Fig. 5 :

 5 Fig. 5: Multikernel deconvolution for the same binary object (a) than Figure 4, whose acquisitions have been simulated for (b): n=2 and θ=0° and 90°, (c): n=4 and θ=0°, 45°, 90° and 135°, and finally for (d): n=8 in steps of 22.5°.

Fig. 6 :Fig. 7 :

 67 Fig. 6: Comparison of multikernel deconvolutions with rotating narrowed PSF at excitation and monokernel deconvolutions with a regular PSF for different SNR: no noise, 20 dB and 3 dB (a): original object. (b)-(d): simulations of acquired images with a three-beam-excitation confocal kernel oriented at

Fig. 8 :

 8 Fig. 8: (a): Quadratic error curves computed between orignal and reconstructed objects as a function of the regularization parameter λ and angular error on the kernel estimations, with 3 dB SNR. Thick red curve: monokernel deconvolution. Thick black curve: 4-kernel deconvolution without angular error. Solid line: 5° angular error. Dotted line: 10° angular error. Dashed line: 15° angular error. Dotted-Dashed line: 20° angular error. (b): original narrowed PSF. (c): 2-kernel equivalent PSF. (d): 4-kernel equivalent PSF.

Fig. 9 :

 9 Fig. 9: Application of 3-beam excitation to 4Pi type A microscopy. (a): regular confocal PSF. (b): 4Pi type A confocal PSF. (c) 3-beam-excitation 4Pi illumination. (d) 3-beam-excitation 4Pi type A confocal PSF. (NA = 1.2, λ ill =400 nm, λ det =500 nm).

φ 2 =

 2 and O. Haeberlé, "Multi-kernel deconvolution applied to ……" Figure1and O. Haeberlé, "Multi-kernel deconvolution applied to ……" Figure2

  x

  and O. Haeberlé, "Multi-kernel deconvolution applied to ……" Figure4

  and O. Haeberlé, "Multi-kernel deconvolution applied to ……" Figure5and O. Haeberlé, "Multi-kernel deconvolution applied to ……" Figure8

  and O. Haeberlé, "Multi-kernel deconvolution applied to ……" Figure9

B. Simon and O. Haeberlé, "Multi-kernel deconvolution applied to ……" Figure3

B. Simon and O. Haeberlé, "Multi-kernel deconvolution applied to ……" Figure7

Aknowledgements:

The authors gratefully acknowledge Philippe Réfrégier and Bruno Colicchio for enlightening discussions about multi-kernel deconvolution and image restoration techniques.


Hugo Férée

Mathieu Hoyrup

Higher-order complexity in analysis

We present ongoing work on the development of complexity theory in analysis.

Kawamura and Cook recently showed how to carry out complexity theory on the space C [0, 1] of continuous real functions on the unit interval. It is done, as in computable analysis, by representing objects by first-order functions (from finite words to finite words, say) and by measuring the complexity of a second-order functional in terms of second-order polynomials.

We prove that this framework cannot be directly applied to spaces that are not σ-compact. However, representing objects by higher-order functions (over finite words, say) makes it possible to carry out complexity theory on such spaces: for this purpose we develop the complexity of higher-order functionals. At orders above 3, our class of polynomial-time computable functionals strictly contains the class BFF of Buss, Cook and Urquhart.

Introduction

Computability theory was initiated with the definition of a computable function from N to N. The theory has been extended in several directions, among which we mention higher-order computability theory and computable analysis. The first one is concerned with the definition and study of computable functionals of higher-order types (taking functions as inputs). The second one is concerned with the definition and study of computable objects that are encountered in mathematical analysis (real numbers, open sets, linear operators, etc.).

Extending complexity theory to higher-order types or in analysis are much more difficult tasks that have been only partially carried out. The class bff 2 of Basic Feasible Functionals from N → N to N → N, introduced in [START_REF] Mehlhorn | Polynomial and abstract subrecursive classes[END_REF] and characterized in [START_REF] Kapron | A new characterization of mehlhorn's polynomial time functionals (extended abstract)[END_REF] is considered to be the natural class of polynomial-time computable type-two functionals. Basic Feasible Functionals above order 2 have been defined and characterized [START_REF] Samuel | The polynomial hierarchy and intuitionistic bounded arithmetic[END_REF][START_REF] Cook | Functional interpretations of feasibly constructive arithmetic[END_REF][START_REF] Cook | Characterizations of the basic feasible functionals of finite type[END_REF][START_REF] Seth | Turing machine characterizations of feasible functionals of all finite types[END_REF][START_REF] Irwin | On characterizations of the basic feasible functionals[END_REF] but there is less evidence that they should be considered as the class of polynomial-time functionals. In analysis, Ko and Friedman's work, mostly gathered in [START_REF] Ker | Complexity Theory of Real Functions[END_REF], is a reference for complexity theory on the real numbers. Abstract approaches, applicable to any space in some classes of topological spaces, have been developed by Weihrauch [?] and Schröder [START_REF] Schröder | Spaces allowing type-2 complexity theory revisited[END_REF] and very recently by Kawamura and Cook [START_REF] Kawamura | Complexity theory for operators in analysis[END_REF]. These approaches differ in the following way. In the first approach, the polynomials measuring the execution time are ordinary (i.e., first-order) polynomials: while the input objects are infinite, their size has to be measured by a single natural number. This technical restriction imposes the space under consideration to be compact or σ-compact. The novelty of Kawamura and Cook's approach is to adopt the ideas of higher-order complexity, allowing for second-order polynomials: the size of an infinite object is a function from N to N and the execution time is a second-order function of the size function of the input. Their approach allows to have a sound complexity theory on larger spaces that are not σ-compact, as the space C [0, 1] of continuous real functions over the unit interval.

In [START_REF] Kawamura | On function spaces and polynomial-time computability[END_REF] it is asked whether complexity theory can be carried out to other spaces, in particular functions spaces. In this ongoing work, we provide both a negative and a positive result. The first one is that Kawamura and Cook's framework cannot be applied to larger spaces. Namely, if X is a Polish space that is not σ-compact then there is no representation of C (X, R) that is acceptable from a complexity perspective (Theorem 3.1). The positive result is that it is possible to overcome this limitation, at the price of increasing the order type of the functions used to represent objects. To summarize, our results tend to show that, while first-order functions admissibly represent objects from many spaces from a topological and computability-theoretic point of view, allowing to use higher-order functions is necessary and sufficient to admissibly represent objects from a complexity perspective.

In Section 2 we present the spaces on which we work: the QCB-spaces, on which computability and topology are closely related. In Section 3 we recall Kawamura and Cook's recent framework, which applies second-order complexity theory to analysis, and show the limitations (Theorem 3.1) of restricting to order 2, which suggests to develop complexity theory at higher orders. We present an outline of this development in Section 4. In Section 5 we apply this framework to analysis.

Computable analysis

Different directions have been followed to develop computability theory on other spaces. The most famous ones are domains [START_REF] Abramsky | Domain theory[END_REF] and represented spaces [START_REF] Weihrauch | Computable Analysis[END_REF]. We will use the second approach. While originally the theory was developed for countably-based topological spaces only, it has been later extended to quotients of topological spaces, which happen to be exactly the spaces admitting admissible representations [START_REF] Schröder | Extended admissibility[END_REF]. Definition 2.1. A QCB-space is the topological quotient of a countably-based topological space.

Every QCB-space is sequential, i.e. a function from a QCB-space to another topological space is continuous if and only if it is sequentially continuous (i.e., maps converging sequences to converging sequences and commutes with the limit operation). The category QCB of QCB-spaces with continuous functions as morphisms enjoys remarkable properties. We will only be concerned with the fact that this category is cartesian closed. Precisely, the product and exponentiation are performed as follows:

• if X, Y are QCB-spaces then the cartesian product X × Y is a QCB-space with the topology induced by the following notion of convergence: (x i , y i ) converge to (x, y) if x i converge to x and y i converge to y. The topology on X × Y is stronger than the product topology;

• if X, Y are QCB-spaces then the set C (X, Y ) of continuous from X to Y is a QCB-space with the topology induced by the following notion of convergence:

f i converge to f if for every sequence x i converging to x, f i (x i ) converge to f (x).
QCB-spaces happen to be exactly the spaces on which computability theory can be extended. B denotes the Baire space of functions from N to N with the product topology. Definition 2.2 ( [START_REF] Weihrauch | Computable Analysis[END_REF][START_REF] Schröder | Extended admissibility[END_REF]). A representation of a set X is a partial surjective map δ X ⊆: B → X.

A representation δ X of a topological space (X, τ ) is admissible if:

• δ X is continuous,
• δ X is projective in the sense that for every partial continuous map f : B → X there exists a partial continuous map F : B → B such that f = δ • F .

Theorem 2.1. [START_REF] Schröder | Extended admissibility[END_REF] The QCB-spaces are exactly the topological spaces that admit an admissible representation.

On QCB-spaces X, Y endowed with admissible representations δ X , δ Y , the continuous functions are exactly the functions f : X → Y that have a continuous realizer, i.e. a partial continuous function F : B → B such that f • δ X = δ Y • F . Hence the computable functions are automatically continuous and the continuous functions are exactly the functions that are computable relative to some oracle.

Higher-order functionals

Here we present an important class of QCB-spaces.

We define the finite types as follows:

τ = N | τ 1 × . . . × τ n → N
We interpret each type as a QCB-space, inductively on the structure of the type: N is interpreted as the set of natural numbers with the discrete topology and the QCB-space associated to τ 1 × . . . × τ n → N is obtained by applying the product and exponentiation in the category QCB.

The elements of these QCB-spaces are exactly the Kleene-Kreisel continuous functionals (see [START_REF] Normann | Chapter 8 the continuous functionals[END_REF]).

Complexity in analysis

The class bff 2 of Basic Feasible Functionals defined by Mehlhorn [START_REF] Mehlhorn | Polynomial and abstract subrecursive classes[END_REF] is considered as the natural class of polynomial-time computable type-two functional from Σ * → Σ * to Σ * → Σ * , as it enjoys many desirable properties and admits several characterizations [START_REF] Kapron | A new characterization of mehlhorn's polynomial time functionals (extended abstract)[END_REF][START_REF] Kapron | A new characterization of type-2 feasibility[END_REF][START_REF] Irwin | On characterizations of the basic feasible functionals (part i)[END_REF]. Kawamura and Cook [START_REF] Kawamura | Complexity theory for operators in analysis[END_REF] made use of this class to define the notion of polynomial-time computable function between represented spaces.

For technical reasons, they use as representation space the subspace Reg of length-monotonic functions from Σ * to Σ * (where Σ is a finite alphabet). For the purpose of the current section, it makes no difference. For us a representation starts from B. The size of n ∈ N is the length of its binary expansion and the size of f :

N → N is |f |(n) = max |p|≤|n| |f (p)|. Definition 3.1. Let (X, δ X ) and (Y, δ Y ) be represented spaces. A function f : X → Y is polynomial-time computable if there is a polynomial-time computable functional F : B → B such that f • δ X = δ Y • F .
Working on compact or σ-compact spaces allows for the development of firstorder complexity theory, i.e. where the complexity of functions is expressed in terms of ordinary, first-order polynomials [START_REF] Schröder | Spaces allowing type-2 complexity theory revisited[END_REF][START_REF] Kunkle | Some examples of non-metrizable spaces allowing a simple type-2 complexity theory[END_REF]. The novelty of [START_REF] Kawamura | Complexity theory for operators in analysis[END_REF] was to develop complexity theory on spaces that are not σ-compact, like C ([0, 1], R). Kawamura [START_REF] Kawamura | On function spaces and polynomial-time computability[END_REF] asks to which spaces X, Y (in place of [0, 1] and R respectively) their approach can be extended. More precisely, for which spaces X and Y is there an admissible representation of C (X, Y ) which makes Eval X,Y : C (X, Y )× X → Y polynomial-time computable and that "polynomially reduces" to any such representation. Here we show that even a weakening of the first condition cannot be satisfied when X is a Polish space that is not σ-compact: for any representation of C (X, Y ), the time complexity of Eval X,Y is not even welldefined! Definition 3.2. Let X, Y be QCB-spaces together with admissible representations. A computable function f : X → Y has well-defined time complexity if there is an oracle Turing machine M and a total continuous function T : B × N → N such that for each representation s of some x ∈ X, M s computes a representation of f (x), and M s (u) runs in time bounded by T (|s|, |u|).

Observe that if f is polynomial-time computable then its time-complexity is well-defined: T is a second-order polynomial. In a similar way, one could define exponential-time computable functions: any such function would have well-defined time complexity. Theorem 3.1. Let X be a Polish space that is not σ-compact and Y = R. There is no representation of C (X, R) making the time complexity of Eval X,R :

C (X, R) × X → R well-defined.
Proof. Let δ ⊆: B → C (X, R) be such a representation. The composition of Eval with δ gives partial continuous function form B → C (X, R) which is bounded by a total continuous function T : B → C (X, R). We define a continuous function F : X → R which is not in the image of δ. By a theorem of Hurewicz ([13], Theorem 7.10, p. 39) and the assumption on X, B is homeomorphic to a closed subset C of X, let Φ : B → C be such an homeomorphism. We first define F on C by F (Φ(s)) = T (s)(Φ(s)) + 1 and extend it to X by the Tietze extension theorem. If F = δ(s) for some s then F (Φ(s)) ≤ T (s)(Φ(s)) which contradicts the definition of F .

Particular examples of such spaces X are the Baire space B and the space C ([0, 1], R). Even if the complexity of continuous functions from X to R can be defined, it does not seem possible to carry out a complexity theory where these objects are first-class citizens, i.e. are objects of some represented space C (X, R).

Intuitively, the Baire space is not large enough to represent objects of larger spaces in a way that respects the size of the objects. An object contains so much information that when encoding it into a sequence of natural numbers, one has to postpone the information very far in the sequence so the time needed to reach a piece of information is arbitrarily larger than the size of the representation, and cannot be bounded by a continuous function of the size of the representation. Observe that replacing B with Σ * → Σ * or Reg does not solve the problem, as 3.1 can be adapted to those cases.

We now show that allowing larger representation spaces, namely higher-order functions spaces over N, one can carry out complexity theory for larger spaces.

Higher-order complexity

As mentioned in the introduction, there is already a notion of polynomial-time computable functional at any finite type, namely the Basic Feasible Functionals (bff i ). However this class is unsatisfactory in the sense that it misses functionals that are intuitively feasible, which is illustrated by the following example taken from [START_REF] Irwin | On characterizations of the basic feasible functionals[END_REF] (Appendix A).

Example 1. Let f ∞ be the zero function of type N → N, and for all x ∈ N, f x the function of same type such that f x (2 x ) = 1 and f x (y) = 0 otherwise. Now we can define two functionals of order 3:

Φ(F, x) = 0 if F (f x ) = F (f ∞ ) 1 otherwise. Ψ(F, x) = 0 if F (f x ) = F (f ∞ ) 2 x otherwise.
First, note that f x is polynomial time computable, even relatively to x. So evaluating these two functionals is just a matter of evaluating F on two polynomial time computable functions and comparing the results, so this comparison is feasible. Indeed, Φ is a basic feasible functional. On the other hand, Ψ is not in bff 3 since the size of the answer is exponential in the size of |x| and the computation time of Ψ cannot be bounded by a polynomial in the size of x and the size of F (as a function). Nevertheless, Ψ is intuitively feasible (as pointed out by the authors of [START_REF] Irwin | On characterizations of the basic feasible functionals[END_REF]). The idea is that if F distinguishes f (x) and f ∞ , then during these evaluations, F had to ask for the value of its argument at input 2 x (since it is the only point where they differ). In this case, the time taken for this computation is at least 2 x , so writing 2 x as an output at most doubles the computation time between Φ and Ψ. The reason why Ψ is not in bff 3 (and other previous notions of higher order feasibility) is that the evaluation of |F | is seen as a black box where only the size of the input and the output matters whereas the modulus of continuity is not taken into account. We will show in example 7 that the Ψ functional is indeed polynomial time computable in our sense.

This behavior also appears in computable analysis and the following example describes a real functional which is also intuitively feasible for similar reasons.

Example 2. Γ(F, n) = 0≤i≤2 n (1 + |F (h i,n )|)
where h i,n is the peak function of height 1 and width 2 -n . This functional might not seem feasible since it requires to evaluate F on an exponential number of points. This idea is reinforced by the fact that Γ cannot be realized by a bff 3 functional (which will be made formal in Section 5). Indeed, if we set F to be the infinite norm ||.|| ∞ , the size of Γ(||.|| ∞ , n) = 2 2 n is not bounded by a polynomial in ||.|| ∞ and n.

However, there is a feasible way of computing Γ. Here are a sketch of this procedure and partial justifications for its feasibility. Compute F on the zero function (say, with precision 2 -2n ). During this computation, F only makes a finite number of queries to its argument. Then, if a function h is small at these points, then F (h) is small too. This way, we only need to compute F on the h i which are close to these points to compute Γ. The evaluation of F on the zero function and on each h i can be made in polynomial time. The only reason for this procedure not to be feasible is the number of h i to evaluate, but this number already appears during the computation of F on the zero function. Then, roughly speaking, the time to compute Γ(F ) is about the time to compute F (0) multiplied by the time to compute F on one of the h i , which is polynomial in the computation time of F . In particular, if F is polynomial time computable, then the number of h i to evaluate is bounded by a polynomial in n.

Notations & definitions

We define the level of finite types as follow: N has level 0, and

τ 1 × • • • × τ n → N has level 1+max i level(τ i ).
In the following we may write, by abuse of language, that τ has type n instead of level n.

|.| will denote the size of the binary encoding of integers or finite words. We will further need to denote each occurrence of N in τ 1 × • • • × τ n → N: The only occurrence in N is denoted by the empty word ε. If a is a code for an occurrence in τ i , then this occurrence is denoted by i.a in

τ 1 × • • • × τ n → N. Definition 4.1. The rightmost occurrence of N in τ 1 × • • • × τ n → N is posi- tive, and any positive (resp. negative) occurrence of N in τ i is negative (resp. positive) in τ 1 × • • • × τ n → N.
Note that it is equivalent to say that an occurrence is positive if and only if its code is a list of even length.

Example 3. In the type (N × N → N) → N, the occurrences are: ε, 1, 1.1 and 1.2.

In the following we will use indexed occurrences: if i 0 . . . i k is an occurrence in τ , and n 0 , . . . n k are integers, then i n0 0 . . . i n k k is an indexed occurrence. For simplicity, we might omit the indexes when they are equal to 0.

Higher order strategies

A type 1 machine (i.e., a classical Turing machine) takes integers as input, so a type 2 machine must be able to evaluate its type 1 argument by providing it with integers. This is precisely the idea behind the oracle Turing machine model defined in [START_REF] Kapron | A new characterization of type-2 feasibility[END_REF] for type 2 functionals. It can be seen as a mechanism where the machine asks questions and waits for the device computing its argument to answer.

Then, naturally, a type 3 machine should be able to evaluate its type 2 argument the same way. Thus this argument should be, in turn, able to ask questions and wait for the machine to answer them. This way, we can see the interaction between a machine of arbitrary type with its arguments as a dialogue where both can ask and answer questions to each other.

We describe the dialogue between a function of type τ 1 ו • •×τ n → N and its arguments of type τ 1 , . . . , τ n as a game, inspired by the Game of Higher Types, used by Hyland and Ong [START_REF] Hyland | On Full Abstraction for PCF: I, II, and III[END_REF] to provide a full abstraction for PCF. Definition 4.2. A move in the game τ is either a question ? a or an answer ! a (v), where a is an indexed occurrence in τ and v an integer.

A play is a list of moves, with a few restrictions:

• The moves at even (resp. odd) position are called the opponent's (resp. player's) moves.

• The first move of a game is always ? ε .

• Each player's (resp. opponent's) move (except the first one) must be justified by a previous opponent's (resp. player's) question this way:

a question ? a.i n is justified by a previous open question ? a and n must be minimal such that ? a.i n does not appear previously in the play an answer ! a (v) is justified by a question ? a and we then say that this question is closed

• We say that the game is over if the last move answers the initial ? ε question (it is then of the form ! ε (v)).

Note that the player (resp. opponent) only asks questions at negative (resp. positive) occurrences and answers to positive (resp. negative) questions. Definition 4.3. A strategy s is a partial function which, given a play p of odd length, outputs a valid move s(p), i.e. such that (p, s(p)) is still a valid play. We write s(p) = ⊥ when the strategy is not defined.

Definition 4.4. Within type τ 1 × • • • × τ n → N, if 1 ≤ i ≤ n and k ∈ N, view k i
is defined this way on plays:

• view k i (p, ? i k .a ) = view k i (p), ? a • view k i (p, ! i k .a (v)) = view k i (p), ! a (v) • view k i (p, m) = view k i (p) otherwise.
In other words, we take the moves in p concerning an indexed occurrence beginning with i k and remove i k from this numbered occurrence.

More generally, we define view(h) as view k i (h) if h ends with a move concerning i k (i.e. ? i k .a or ! i k .a ). Definition 4.5. A game is the interaction between several strategies. If s is a strategy for τ 1 × • • • × τ n → N and for all i, s i is a strategy for τ i , then the game between s and s 1 , . . . , s n is defined this way:

The initial play is p =? ε . While s has not answered the initial question (i.e the last element of p is of the form ! ε (v)), look at the next move s(p) of s and add it to the play (p becomes p, s(p)). If s(p) concerns i k , then look at the next move of the i th argument (namely s i (view(p, s(p)))). If it is a question ? a , add ? i k .a to the play and if it is an answer ! a (v), add ! i k .a (v) to the play.

When an answer of the form ! ε (v) appears, the game terminates and v is called the result of the game and is denoted by s[s 1 , . . . s n ]. If at some point s(p) = ⊥ or view(p, s(p)) = ⊥, the game is interrupted and the result is undefined. s[] is then a partial function mapping strategies to integers.

The final play is called the history of the game and is denoted by H(s, s 1 , . . . , s n ).

In this definition, we use view to build the argument of a strategy. Thus we have to prove that in this case, the provided argument is a valid play. Proposition 4.1. At each step of the game, the current play p is valid for the game in τ , and for every (i, k), view k i (p) is a valid play for the game in τ i . Remark 4.1. There are two ways for a game not to terminate: one of the strategies cannot play (is not defined) or there are an infinite number of moves.

We define the representability of a function with a strategy by induction on the order of the function. This implies that an integer k, as a function of level 0, is represented by the only strategy s verifying s(? ε ) =! ε (k) and undefined otherwise.

• s(? ε ) =? 1 • s(? ε , ? 1 , ! 1 (v)) =! ε (f (v)) Theorem 4.1. A function f : τ 1 × . . . × τ n → N is continuous if and only if it is represented by a strategy.
Proof idea. Strategies easily correspond to associates as defined by Kleene [START_REF] Sc Kleene | Countable functionals[END_REF]. The continuous functionals are exactly the functionals that admit an associate.

Here is another way to present strategies: Definition 4.7 (Execution tree). Given a strategy s, we define the associated execution tree as an infinite tree with labeled nodes and edges. The nodes are labeled with the strategy moves, and the edges with its possible opponent's moves:

• The root node has no label and leads to an edge labeled with ? ε

• If the path from the root to an edge is labeled with p, then the node at the end of the edge is labeled with s(p).

• If the path from the root to a node is labeled with p and the last move of p concerns i k , then the outputting edges from this node are labeled with all the possible moves of an opponent s i on view k i (p). We can also define the execution tree corresponding to a subset of opponent's strategies.

Remark 4.3. The interaction between s and its input strategies is always finite if and only if the corresponding execution tree has only finite branches.

Complexity

For type 1 functions, complexity is defined as the run time of a machine with respect to the size of the inputs. The inputs are now strategies, and we need to define their size before defining complexity.

Let us assume that we have a reasonable encoding enc of moves and plays as finite words. Then, a strategy can be seen as function from binary words to binary words, so we can say that a strategy is computable if is computable as a type 1 function, and that a functional is computable if it is represented by a computable strategy. Definition 4.8 (Size of a strategy). We define inductively the size of a strategy and the set of strategies of bounded type. The size of a strategy is a function of the same type. If s is a strategy over τ 1 × • • • × τ n → N, then its size is:

S s (b 1 , . . . , b n ) = max (s1,...sn)∈K b 1 ו••×K bn |enc(H(s, s 1 , . . . s n ))|
Where K b denotes the set of strategies s over type τ 1 × • • • × τ n → N whose size is bounded by b with respect to the pointwise ordering verifying: whenever s(p) is defined, then there exists strategies (s 1 , . . .

s n ) ∈ K τ1 × • • • × K τn such that p is a prefix of H(s, s 1 , . . . s n ) (where K τ is the union K b with b of type τ ).
Finally, call K the union of the K τ , for every finite type τ .

Remark 4.4.

• In particular, the size of a strategy of type N is (roughly) the size of the encoding of the integer it computes.

• For every strategy s in

K τ1ו••×τn→N , s[] is total on K τ1 × • • • × K τn and
s is entirely described by its behavior on

K τ1 × • • • × K τn .
In other words, the set of paths in the execution tree of s is exactly

{H(s, s 1 , . . . s n ) | (s 1 , . . . s n ) ∈ K τ1 × • • • × K τn } Theorem 4.2. S s (b 1 , . . . , b n ) is defined if and only if the execution tree of s restricted to strategies in K b1 × • • • × K bn is finite.
Remark 4.5. Note that the size of a strategy of type 0 representing an integer n is Size(? ε , ! ε (n)) = O(|n|). So the size of a strategy of type 0 is close to the size of the integer it computes. Simlarly, the size of a strategy computing a function of type 1 as described in remark 4.2 is roughly bounded by: n → n + max |k|≤n |f (k)|, which is almost the definition of the size used in bff (defined in [START_REF] Cook | Functional interpretations of feasibly constructive arithmetic[END_REF] and characterized in [START_REF] Cook | Characterizations of the basic feasible functionals of finite type[END_REF]).

The size of strategies of types 0 and 1 match in some sense the size of the functions they represent.

Example 4. Let Φ : ((N → N) → N) × N → N be defined by: Φ(F, n) = F (λx.n) A strategy to compute Φ is to query n, and then query F by playing the role of a strategy computing λx.n. An evaluation of this strategy could be ?ε, ? 2 , ! 2 (n), ? 1 , ! 1 (v), ! ε (v) if the strategy for F immediately answers v (thus F is constant), or of the form ?ε, ? 2 , ! 2 (n), (?

1 , ? 1.1 , ! 1.1 (n), ? 1.1 2 , ! 1.1 2 (n), . . . , ! 1 (v)), ! ε (v),
where the part between parenthesis corresponds to the evaluation of the strategy of F on the strategy of λx.n. The size of the latter is bounded by λy.|n| + C (for a constant C), so the size of this evaluation is bounded by |F |(λy.|n| + C) by definition. This also bound the size of the last answer (! ε (v)), so finally, the size of the strategy for Φ is bounded by λG.λx.2 * G(λy.x + C) + C ′ for some constant C ′ . Now that we have defined the size of our inputs, we need a notion of computation time. This can be achieved by defining a model of machines simulating strategies, generalizing the oracle Turing machine model (for type 2 functionals). For sake of simplicity, we only sketch this definition here. A higher order Turing machine over the finite type t is an oracle Turing machine with one special state for each occurrence of N in t and special tapes for indexes and answers. The machine can write to these tapes and enter the special states to simulate questions and answers for its arguments. Then, the corresponding argument strategy (or machine) can reply the same way. The cost of such an answer is the size of the simulated move. Finally, the complexity of such a machine is a bound on its computation time given a bound on the size of the input strategies.

Polynomial time complexity

To define a class of higher type feasible functionals we need a notion of polynomial bound for higher type time bounds. There is already such a bound to characterize the basic feasible functionals of type 2 with oracle Turing machines.

P := c | X | P + P | P × P | Y (P )
where X is a type 0 variable and Y is a type 1 one.

This notion has been extended to all finite types in [START_REF] Irwin | On characterizations of the basic feasible functionals[END_REF].

Definition 4.9 (Higher type polynomials ). The higher order polynomials are the terms of HT P , the simply-typed lambda calculus over N with special terms + and * of type N × N → N.

Definition 4.10. We say that a higher order functional is computable in polynomial time if it is computed by a machine whose running time is bounded by a higher order polynomial.

Example 5. The evaluation operator Eval : (τ 1 × . . . × τ n → N) × τ 1 × . . . × τ n → N is polynomial-time computable. Indeed, it can be computed by simulating the progress of the game between its arguments as follows: query the first argument on ? ε and while the game is not over, read the provided move, translate and copy it to the corresponding argument strategy, wait for its answer, and translate it back to the main strategy (as it is done in definition 4.5). The computation time is then about the size of the main strategy applied to the size of its arguments, that is to say T (t, t 1 , . . . , t n ) = t(t 1 , t n ). As a consequence, the class of polynomial time computable functionals is stable with respect to composition.

Example 6. This definition of higher type polynomials coincides with the usual polynomials at type 1 and with the second order polynomials (used in [START_REF] Kapron | A new characterization of mehlhorn's polynomial time functionals (extended abstract)[END_REF] to characterize bff 2 ). Additionally , the induced complexity class matches the standard classes at types 1 and 2 (that is fp=bff 1 and bff 2 ). More generally, every functional belonging to bff is polynomial-time computable, but as the next example shows, the other direction does not hold.

Example 7. Now that we have the formalism of strategies we can show that the Ψ functional of example 1 is indeed computable in polynomial time. Indeed, if a strategy computes some F which distinguishes f ∞ and f x , then the play against the strategy representing f x necessarily contains the question ?

Application to computable analysis

Now our goal is to use higher-order functionals to represent objects and to extend complexity notions from higher-order functionals to QCB-spaces.

Remind the types inductively defined by τ = N | τ 1 × . . . × τ n → τ . Remind that a type is interpreted as a QCB-space of hereditarily total continuous functions. However when representing objects one usually considers partial functions, which can be seen as total on their domains. Formally, wee define a particular class of QCB-spaces, the τ -spaces, which will serve as representation spaces.

Definition 5.1. Let τ be a finite type. A τ -space is defined inductively by:

• an N-space is a subset of N endowed with the discrete topology,

• given τ i -spaces A i and a τ -space A, a (τ 1 ×. . .×τ n → τ )-space is a subspace of the space C (A 1 × . . . × A n , A) of total continuous functions, with the induced topology.

Definition 5.2. A τ -representation of X is a partial surjective continuous function δ ⊆: A → X where A is a τ -space.

Observe that usual representations can be viewed as (N → N)-representations. In terms of topology and computability, τ -representations can be used in place of (N → N)-representations, as for any τ -space can be embedded in a τ ′ -space, for any τ, τ ′ such that τ ′ has depth at least 1 hence any admissible τ -representation induces an admissible τ ′ -representation.

The results presented in Section 3 can be formulated as follows: there is no admissible (N → N)-representation of C (X, Y ) which makes the time complexity of Eval : C (X, Y ) × X → Y well-defined, whenever (X, Y ) = (C (N, N), N) or (X, Y ) = (C ([0, 1], R), R).

One has to use τ -representations with arbitrary τ to carry out complexity theory on larger functions spaces. Definition 5.3. Let δ X be an admissible τ 1 -representation and δ Y an admissible τ 2 -representation. We define a (τ 1 → τ 2 )-representation δ X→Y of C (X, Y ) as: if f : X → Y is continuous and F : τ 1 → τ 2 is continuous and f

• δ X = δ Y • F then δ C (X,Y ) (F ) = f .
Observe that as δ X and δ Y are admissible, δ C (X,Y ) is a representation: it is onto and maps continuous functions to continuous functions. Proof. The first point is proved by the same arguments as in [START_REF] Weihrauch | Computable Analysis[END_REF][START_REF] Schröder | Extended admissibility[END_REF], adapted to τ -spaces.

Eval on X and Y is computed by Eval on τ 1 and τ 2 , which is polynomial-time computable (see Example 5).

We do not answer the question whether there exists a minimal representation of C (X, Y ), i.e. a representation that polynomially reduces to any representation that makes Eval polynomial-time computable. We leave that problem for future investigations. Another interesting problem is to study the categorical properties of spaces admitting a representation admissible form a complexitytheoretic perspective. The results presented here suggest that the underlying category may be cartesian closed.

Definition 4 . 6 .

 46 A partial function f of type τ 1 × • • • × τ n → N is represented by a strategy s if for (f 1 , . . . , f n ) inthe domain of f and for every strategies s 1 , . . . , s n representing f 1 , . . . f n respectively, s[s 1 , . . . s n ] = f (f 1 , . . . f n ).

Remark 4 . 2 .

 42 A function f : N → N can be represented by the following strategy:

Proposition 5 . 1 .

 51 The representation δ C (X,Y ) is admissible. Moreover, Eval : C (X, Y ) × X → Y is polynomial-time computable.

  2 x , which entails that |F |(|f x |) > 2 x . Then, in any case, the computation time of the machine computing Ψ (whose bahavior was shortly described in example 1) is about |F |(|0|) × |F |(|f x |), which is a third order polynomial in |F | and |x|, since |f x | is a polynomial.