B Cretu

D Boudier

E Simoen

A Veloso

N Collaert

C Claeys

Improved physics-based analysis to discriminate the flicker noise origin at very low temperature and drain voltage polarization

Keywords: GAA NW FETs, low frequency noise, flicker noise, cryogenic temperature, mobility fluctuations, carrier number fluctuations

Low frequency noise study is performed at deep cryogenic temperature of 10 K in p-channel gate-all-around (GAA) nanowire (NW) FETs. As expected, the carrier number fluctuations mechanism explains the flicker noise origin for conventional fixed applied drain bias. At very low applied drain biases step-like effects impact the drain current transfer characteristics. Noise measurements performed at a fixed very low drain voltage as a function of the applied gate bias show that the gate voltage flicker noise behavior follows a 3/ 2 2 DS m Ig law. It was already proved that this dependency may be modeled considering classical transport theory, in the framework of the mobility fluctuations mechanism from Coulomb scattering interactions. The noise measurements performed at fixed gate voltage as a function of the applied drain bias show that the gate voltage 1/f noise levels present a deviation from the 3/ 2 2 DS m Ig law. In order to explain this behavior, an improved model is proposed mainly considering some additional hypotheses: the inversion charge dependency on the applied drain bias and the fact that the impact of the drift component of the drain current may be neglected when measurements are made at low fixed gate voltage biases for very low applied drain voltages.

The results show that for the lower drain biases considered in this work, the flicker noise behavior may be explained using physical-based models derived from classical transport considerations for cryogenic temperatures by the mobility fluctuations mechanism originating from Coulomb scattering interactions. This may be surprising, and suggests that even if step-like effects impact the DC measurements, there is a polarization interval in which they do not impact the 1/f noise.

I. INTRODUCTION

The interest in very low temperature operation of CMOS devices and circuits is well known [START_REF] Balestra | Device and circuit cryogenic operation for low temperature electronics[END_REF][START_REF] Simoen | Freeze-out effects on NMOS transistors characteristics at 4.2K[END_REF]. Additionally, growing interest to use nanometric technologies to design and implement quantum computing control systems together with the qubits are evoked recently [START_REF] Reilly | Engineering the quantum-classical interface of solid-state qubits[END_REF][START_REF] Charbon | Cryo-CMOS for quantum computing[END_REF]. It is important to have a thorough insight in the carrier transport and in particular in the low frequency noise at these deep cryogenic temperatures.

An analytical expression for the drain current 1/f noise power spectral density S id in strong inversion, taking into account the mobility fluctuations mechanism is reported in [START_REF] Hafez | Flicker noise in MOS transistors operated at room and liquid helium temperatures[END_REF]. As this expression needs to estimate additional parameters in particular the threshold voltage (V th ) and the low-field mobility attenuation factor ( it ), it works only from moderate to strong inversion operation. However, this expression cannot be used when step-like effects are present in the drain current transfer characteristic because the parameter estimation cannot be performed properly, in particular for V th and  it . Concerning carrier number fluctuations, it is specified that the flat-band voltage noise fluctuations (S vfb ) are assumed to be constant with bias and so the general expression [START_REF] Ghibaudo | Improved analysis of low frequency noise in field-effect MOS transistors[END_REF] should be still valid at very low temperature operation.

An original approach concerning the mobility fluctuations (µ) model and carrier number with correlated mobility fluctuations model (n + µ) valid at very low temperature operation was proposed in [START_REF] Nafaa | Low-frequency noise measurements at liquid helium temperature operation in ultra-thin buried oxide transistors -Physical interpretation of transport phenomena[END_REF]. It takes into account the mobility law that governs the carrier transport for temperatures lower than 40 K in classical transport considerations, i.e., the Coulomb scattering at low vertical fields and surface roughness at high vertical fields [START_REF] Ghibaudo | Modelling of ohmic MOSFET operation at very low temperature[END_REF][START_REF] Jeon | MOSFET electron inversion layer mobilities-A physically based semi-empirical model for a wide temperature range[END_REF]. However, this model is valid only in moderate inversion operation.

A more detailed analysis was made in [START_REF] Boudier | Discussion of the flicker noise origin at very low temperature and polarisation operation[END_REF] and the methodology presented in [START_REF] Nafaa | Low-frequency noise measurements at liquid helium temperature operation in ultra-thin buried oxide transistors -Physical interpretation of transport phenomena[END_REF] is extended from weak to moderate inversion. Additional to the mobility law considered, assuming as usual that the inversion charge from weak to moderate inversion presents an exponential dependency with the applied drain bias, the expressions for the µ and n + µ models developed from weak to moderate inversion operation are reminded in where the c4_dn and c6_dµ are constant coefficients defined in [START_REF] Boudier | Discussion of the flicker noise origin at very low temperature and polarisation operation[END_REF].

In this work, the 1/f noise behavior for p-channel GAA NW FETs is investigated at 10 K operation. To avoid misunderstanding, as p-channel devices are studied in this work, for all further equations, all applied voltages and current are presented in absolute value.

The presence of step-like effects is evidenced in the drain current and transconductance behavior with the applied gate voltage at fixed very low drain bias.

The methodology to extract the 1/f and Lorentzian noise parameters, developed in [START_REF] Boudier | Low frequency noise analysis on Si/SiGe superlattice I/O n-channel FinFETs[END_REF], is further described through a noise spectrum example. The evolution of the 1/f noise versus the applied gate voltage follows the

3/ 2 2 DS m
Ig as in [START_REF] Boudier | Discussion of the flicker noise origin at very low temperature and polarisation operation[END_REF] (see (2) reminded here), suggesting that the mobility fluctuation mechanism dominates the 1/f noise. Moreover, this indicates that the µ model proposed in [START_REF] Boudier | Discussion of the flicker noise origin at very low temperature and polarisation operation[END_REF] explains 1/f noise evolution with the applied gate voltage for both n-and p-type GAA NW FET channels, even if the devices are biased in operation conditions for which step-like behavior occurs in the transfer characteristics. However, when the measurements are made as a function of the applied drain voltage at fixed low gate bias, the developed model in [START_REF] Boudier | Discussion of the flicker noise origin at very low temperature and polarisation operation[END_REF] cannot conveniently explain the 1/f noise magnitude behavior. This trend was already observed for ntype channel in [START_REF] Boudier | Discussion of the flicker noise origin at very low temperature and polarisation operation[END_REF].

Improved analysis is made and a novel model is constructed. The additional hypotheses compared to those considered in [START_REF] Boudier | Discussion of the flicker noise origin at very low temperature and polarisation operation[END_REF] are: the inversion charge dependency on the applied drain bias is taken into account using as usual a trapezoidal approximation; the impact of the drift component of the drain current may be neglected when measurements are made at fixed V GS if V DS is very low and V DS << V GS . Finally, without any other assumptions on the origin of the step-like effect on the drain current, the proposed model explains the flicker noise behavior at very low applied drain voltages in the framework of mobility fluctuations. This surprising result suggests that the 1/f noise mechanism is different from the one responsible for the step-like behavior.

II. RESULTS AND DISCUSSION

Low frequency noise (LFN) measurements were performed at wafer-level on p-channel GAA NW FETs fabricated at imec on 300 mm wafers. The process description may be found in [START_REF] Veloso | Gate-all-around nanowire FETs vs. triple-gate FinFETs: on gate integrity and device characteristics[END_REF]. Details on the measurement set-up are given in [START_REF] Boudier | Low frequency noise assessment in nand p-channel sub-10 nm triple-gate FinFETs: Part I: Theory and methodology[END_REF]. The LFN study was focused at very low temperature (i.e., 10 K) for a fixed gate length of 60 nm.

A. DC measurements, step-like transport evidence

From Fig. 1, it may be observed that the drain current normalized by the applied drain bias does not superpose for lower V DS values and presents step-like effects. The effect is more clearly represented in Fig. 2, showing the transconductance for two different drain biases. Using the method presented in [START_REF] Boudier | Low frequency noise analysis on Si/SiGe superlattice I/O n-channel FinFETs[END_REF], the conditions to observe quantum transport are fulfilled, i.e., a E higher than the energy induced by the drain voltage (q|V DS |) and higher than the thermal energy (about 862 µeV at 10 K). Indeed, from the minima of the oscillations in the transconductance behavior, the subband energy spacing E between the successive energy subbands may be estimated [START_REF] Morimoto | Fabrication and transport properties of silicon quantum wire gate-all-around transistor[END_REF][START_REF] Boudier | Detailed characterisation of Si Gate-All-Around Nanowire MOSFETs at cryogenic temperatures[END_REF][START_REF] Boudier | Discussion on the 1/f noise behavior in Si gate-all-around nanowire MOSFETs at liquid helium temperatures[END_REF]; it is found that the estimated E is between 0.9 -2 meV.

B. Low frequency noise measurements

Typical drain current noise power spectrum is shown in Fig. 3. In order to estimate the low frequency noise parameters, the same methodology presented in as in [START_REF] Nafaa | Low-frequency noise measurements at liquid helium temperature operation in ultra-thin buried oxide transistors -Physical interpretation of transport phenomena[END_REF][START_REF] Boudier | Discussion of the flicker noise origin at very low temperature and polarisation operation[END_REF][START_REF] Boudier | Low frequency noise analysis on Si/SiGe superlattice I/O n-channel FinFETs[END_REF][START_REF] Boudier | Low frequency noise assessment in nand p-channel sub-10 nm triple-gate FinFETs: Part I: Theory and methodology[END_REF][START_REF] Boudier | Detailed characterisation of Si Gate-All-Around Nanowire MOSFETs at cryogenic temperatures[END_REF][START_REF] Boudier | Discussion on the 1/f noise behavior in Si gate-all-around nanowire MOSFETs at liquid helium temperatures[END_REF] is applied, assuming that the white noise, flicker noise and generation-recombination noise are non-correlated noise sources. The LF noise is given by the general expression [START_REF] Boudier | Low frequency noise assessment in nand p-channel sub-10 nm triple-gate FinFETs: Part I: Theory and methodology[END_REF]:

2 2 0 0 () 1 g N f id i v n i m i K S A S f W g f f f            (3)
where S vg is the input-referred voltage noise, W n is related to the white noise level, K f /f  gives the flicker noise with a frequency exponent , and the last term of the equation presents a sum of Lorentzian components, with A i the plateau value and f oi the characteristic frequency. The estimated 1/f noise levels were made using the methodology detailed in [START_REF] Boudier | Low frequency noise analysis on Si/SiGe superlattice I/O n-channel FinFETs[END_REF]: the flicker noise level may be estimated considering the mean values of the ()

g v S f f  at
different frequencies f for which the white noise contribution may be neglected and f/f 01 << 1. If these conditions are fulfilled, the relative error of the K f level estimation is less than about 15% considering frequencies lower than f 258 Hz. Of course, if f/f 01 << 1 is no longer true, the method loses accuracy and the relative error increases. The measurement error is less than 10%. This strategy was used to estimate all the 1/f noise levels of the studied noise spectra.

Table 2

Estimation of Kf using a first order approximation of equation ( 1) (e.g. In Fig. 4 the drain current behavior in the time domain representation corresponding to the noise power spectral density represented in Fig. 3 is plotted. The observed RTS events seem to be randomly distributed and no clear correlation may be made with the Lorentzian contribution observed from the frequency domain representation. This suggests that the Lorentzian contribution observed in Fig. 3 is not related to an RTS event, but to a general generationrecombination mechanism.

()

g vf S f f K A f     (i.e. (3) of [11]) f (Hz) () g v S f f  (V²) K f (10

1) 1/f noise behavior versus V GS for a conventional applied drain bias ( V DS = 50 mV)

The estimated input referred gate voltage 1/f noise levels (K f_vg ) for a conventional applied drain voltage of V DS = 50 mV are plotted in Fig. 5. One can note that K f_Vgs is almost constant; suggesting that the carrier number fluctuations due to carrier trapping in the oxide layer prevails on the 1/f noise at this applied V DS . This assumption is confirmed by the good agreement between the normalized drain current 1/f noise (K f_Sids ) and the (g m /I DS )² ratio [START_REF] Ghibaudo | Improved analysis of low frequency noise in field-effect MOS transistors[END_REF]. The flat-band noise S vfb is estimated at about 0.9•10 -9 V 2 /Hz. 2) 1/f noise behavior versus V GS at fixed low drain bias ( V DS = 500 µV)

The K f_vg as a function of the applied gate voltage for a fixed applied V DS of 500 µV is represented in Fig. 6.

Using the model of ( 1) for carrier number correlated to mobility fluctuations (n+µ) the K f_vg behavior cannot be explained. However, for sufficiently high V GS (higher than about 0.8 V) the K f_vg present little variations, which may suggest that the carrier number fluctuations may explain the 1/f level behavior. The estimated S vfb is about 15•10 -9 V 2 /Hz, in contradiction with the value estimated from measurements executed at a V DS of 50 mV.

However, for all applied V GS the experimental noise behavior is fully explained using the µ model of ( 2). This result suggest that Coulomb scattering fluctuations dominate the flicker noise and explain the 1/f noise levels evolution with the applied gate voltage at very low applied drain bias, as in the case of n-type channel [START_REF] Boudier | Discussion of the flicker noise origin at very low temperature and polarisation operation[END_REF]. Fig. 6. Input referred 1/f noise levels as a function of the applied VGS at a fixed VDS of 500 µV and at 10 K operation. Good agreement between experimental data and the µ model of (2) may be observed.

3) 1/f noise behavior versus V DS at a fixed gate bias ( V GS = 0.7 V)

The estimated flicker noise levels as a function of the applied drain voltage at a fixed V GS of 0.7 V are plotted in Fig. 7.

The behavior of the K f_vg level shows initially a slight increase with the increase of V DS , followed by a quick decrease of about one decade with the further increase of the applied V DS in the range of about 3 mV -30 mV. For V DS higher than about 30 -40 mV up to 100 mV, the K f_vg levels present a very slight increase.

From Fig. 7 it is obvious that the n+µ model of ( 1) is in disagreement with the experimental data. Assuming the carrier number fluctuations mechanism leads to consider a flat-band noise independent on the applied drain voltage at fixed V GS . This implies that the behavior of the 1/f noise levels versus V DS presented in Fig. 7 cannot be explained in the framework of the carrier number or mobility fluctuations correlated to number fluctuations mechanisms for all applied V DS range. However, for V DS higher than about 30 mV, a very slight increase of the K f_vg levels around values of 1.8 -2.6•10 -9 V 2 /Hz can be observed. These values are in the same range with the S vfb obtained from measurements as a function of V GS at fixed V DS of 50 mV. This suggests that when measurements are made as a function of V DS , for sufficiently high V DS , (i.e. > about 30 -40 mV) the carrier number fluctuations can explain the 1/f noise.

The µ model of equation ( 2) leads to a decrease of the 1/f noise with the increase of V DS , but it cannot conveniently explain the 1/f noise behavior.

In order to explain the flicker noise evolution with the applied drain voltage for V DS lower than about 30 -40 mV, a novel physical-based model is constructed in the next section. Fig. 7. Input referred 1/f noise levels as a function of the applied VDS bias at a fixed VGS of 0.7 V and at 10 K operation. To construct models of ( 1) and (2), the same noise parameters as obtained from measurements as a function of the applied gate voltage at fixed VDS of 500µV were used.. The model of (1) is definitively not in agreement with the data; the model of (2) even if it seems to reproduce the same tendencies cannot conveniently explain the flicker noise behavior.

III. THEORETICAL APPROACH

A. Inversion charge

In a general manner, because the barrier of the electrons seen at the drain is V DS larger than the barrier at the source, one can write [START_REF] Grotjohn | A parametric short-channel MOS transistor model for subthreshold and strong inversion current[END_REF]:

  ( ) 0 exp DS B qV n L n kT       (4)
where n(L) and n(0) represent the charge density close to the drain, and close to the source, respectively. k B is the Boltzmann constant, T is the temperature and q is the elementary charge.

Considering as usual a trapezoidal approximation (as for (1.3.23) of [START_REF] Tsividis | Operation and modelling of the metal-oxide semiconductor transistor[END_REF]), one can write:

(0) ( ) (0) 1 exp 22

DS s i B qV qN n n L n Q WL k T               (5)
where Q i is the inversion charge density at arbitrary V GS and N s is the total free carrier number.

B. Total free carrier number

Considering a source referenced model, the drain current for a transistor with effective channel gate width W and length L may be written as (e.g. (4.3.5) of [START_REF] Tsividis | Operation and modelling of the metal-oxide semiconductor transistor[END_REF]]):

  (0) ( ) s B DS eff eff i kT W I µ n n L µ W Q L q x      (6)
where µ eff is the effective mobility, ψ s is the surface potential and x represent the position in the channel measured from the source end. The first term of ( 6) represents the diffusion component of the drain current, while the second term the drift one, respectively.

It may be assumed that when measurements are made at a fixed applied gate voltage and for very low applied V DS respecting also that V DS << V GS the drift component may be neglected (i.e. ∂ψ s / ∂x ≈ 0).

Considering this hypothesis, (6) becomes:

  (0) ( ) B DS eff kT W I µ n n L Lq  (7)
For temperatures lower than 40 K the effective mobility µ eff may be expressed by [START_REF] Ghibaudo | Modelling of ohmic MOSFET operation at very low temperature[END_REF][START_REF] Jeon | MOSFET electron inversion layer mobilities-A physically based semi-empirical model for a wide temperature range[END_REF]:

2 m eff im mi µ µ QQ QQ   (8)
where µ m is the maximum of the effective mobility and Q m is the corresponding inversion charge density. This expression represents a simplified description of the scattering law including Coulomb and surface roughness scattering processes [START_REF] Jeon | MOSFET electron inversion layer mobilities-A physically based semi-empirical model for a wide temperature range[END_REF].

It can be easily demonstrated that in weak to moderate inversion when the approximation Q i < Q m may be considered, the effective mobility will read:

2 i eff m m Q µµ Q  (9)
Assuming ( 6) and ( 9), the drain current expressed in ( 7) can be derived as:

2 (0) 1 exp DS m B DS mB qV µ kT W I Q n L q Q k T           (10)
Finally from [START_REF] Boudier | Discussion of the flicker noise origin at very low temperature and polarisation operation[END_REF] and ( 5) one obtains:

  2 2 2 2 (0) 1 exp DS m B DS mB qV µ kT WN Iq L q Q k T WL           (11)
where N(0) represent the number of free carriers at the source.

From [START_REF] Boudier | Low frequency noise analysis on Si/SiGe superlattice I/O n-channel FinFETs[END_REF] and ( 5) one can obtain the expression for the total free carrier number:

1 exp (12) 2 2 1 exp m DS mB s DS B DS B LQ q qV Wµ k T WL N I q k T qV kT                   C.

1/f noise improved equations

Considering only the inversion charge correction, the carrier mobility fluctuations mechanism (µ) [START_REF] Hooge | 1/f is no surface effect[END_REF] reads using ( 5) in (2): Considering [START_REF] Veloso | Gate-all-around nanowire FETs vs. triple-gate FinFETs: on gate integrity and device characteristics[END_REF], µ fluctuations in the empirical law of Hooge [START_REF] Hooge | 1/f is no surface effect[END_REF] can be derived as:

Using ( 5) and ( 9) the carrier number with correlated mobility fluctuations model (n + µ) [START_REF] Hafez | Flicker noise in MOS transistors operated at room and liquid helium temperatures[END_REF][START_REF] Ghibaudo | Improved analysis of low frequency noise in field-effect MOS transistors[END_REF] can be expressed as:

2 3/ 2 2 1 exp 1 ( 15
)
1 exp 14) and ( 15), combined with those expressed in Table 1 with respect of (5), will allow to have a complete equation based methodology in order to correctly identify the flicker noise origin at very low temperature from weak to moderate inversion, even in conditions in which the drift component of the drain current may be neglected, i.e. at very low applied drain voltages.

d fb DS B D m i m v C ox m B m DS B qV kT I Lµ q S g S C WQ k T g qV kT                         Equations (

IV. DISCUSSION

The inversion charge given by ( 5) will not affect the interpretation of the experimental data if the measurements are made at fixed V DS . The advantage of using ( 5) is that it permits to take into account the impact of the applied drain voltage when the measurements are made as a function of V DS at fixed applied V GS .

Using [START_REF] Boudier | Low frequency noise assessment in nand p-channel sub-10 nm triple-gate FinFETs: Part I: Theory and methodology[END_REF] for measurements as a function of V GS will lead to a c6_dµ_corr given by : 2 6 _ 6 _ _

1 exp DS B c dµ c dµ corr qV kT             (16)
As V DS is fixed at 500 µV, a value of c6_dµ_corr of about 1.25•10 -10 A -1/2 is obtained. The results by using this value in Eq. ( 11) for measurements as a function of V DS are plotted in Fig. 8. A reasonable agreement may be observed between the model and the data in 10-30 mV V DS range. However, the trend provided by the model using [START_REF] Boudier | Low frequency noise assessment in nand p-channel sub-10 nm triple-gate FinFETs: Part I: Theory and methodology[END_REF] for V DS lower than 10 mV does not agree well with the experimental data. A good agreement between the model of ( 14) and the data can be observed in Fig. 9 in particular for V DS lower than about 20 mV, namely in polarization conditions for which the hypotheses assumed in (14) apply. For much higher V DS the impact of the applied drain voltage on the surface potential may play a role. As the model of ( 13) which considers the drift component of the drain current is in agreement with data in the 10 -30 mV V DS range, all this suggests that the mobility fluctuations are responsible for the 1/f noise behavior for V DS lower than about 30 mV -40 mV. Fig. 9. Input referred 1/f noise levels as a function of the applied VDS bias at fixed VGS of 0.7 V and at 10 K operation. For VDS lower than about 10 mV, good agreement between experimental data and the µ model of ( 12) may be observed.

Taking into account the results from noise measurements as a function of the applied gate voltage for V DS = 500 µV, it may be suggested that the mobility fluctuations through the Coulomb scattering mechanism may explain the 1/f noise evolution at very low applied V DS , while for V DS higher than about 30 -40 mV the carrier number fluctuations will prevail.

In Fig. 10, it may be observed that the developed model explains also the behavior of 1/f noise levels as a function of the applied drain bias at fixed gate voltage for the n-type channel. No additional mobility mechanism was considered in the mobility law for the constructed 1/f noise models of ( 14) and [START_REF] Boudier | Detailed characterisation of Si Gate-All-Around Nanowire MOSFETs at cryogenic temperatures[END_REF]. The agreement between the developed model (i.e. ( 14)) and the results from n-type and p-type channel devices suggests that at this deep cryogenic temperature and in the low polarization range investigated the 1/f noise behavior could be interpreted through mobility fluctuations using equations derived from classical carrier transport considerations.

The drain current and the transconductance oscillations behavior with the applied gate voltage at very low applied drain biases and temperature clearly present step-like effects (Figs. 1 and2, as in [START_REF] Nafaa | Low-frequency noise measurements at liquid helium temperature operation in ultra-thin buried oxide transistors -Physical interpretation of transport phenomena[END_REF][START_REF] Boudier | Discussion of the flicker noise origin at very low temperature and polarisation operation[END_REF]). This presumes the impact of an additional mobility mechanism than considered in the low frequency noise models developed in [START_REF] Nafaa | Low-frequency noise measurements at liquid helium temperature operation in ultra-thin buried oxide transistors -Physical interpretation of transport phenomena[END_REF][START_REF] Boudier | Discussion of the flicker noise origin at very low temperature and polarisation operation[END_REF] and here, e.g. inter/intra subband scattering mechanisms. However, to assume an additional mobility mechanism influencing the 1/f noise models is in disagreement with the results presented here and in [START_REF] Nafaa | Low-frequency noise measurements at liquid helium temperature operation in ultra-thin buried oxide transistors -Physical interpretation of transport phenomena[END_REF][START_REF] Boudier | Discussion of the flicker noise origin at very low temperature and polarisation operation[END_REF], because in this case the gate voltage flicker noise behavior will not follow a This hypothesis may corroborate with results of [START_REF] Cobden | Random telegraph signals from liquid helium to room temperature[END_REF]: the RTS noise may be generated by the atomic movement of a defect in SiO 2 giving rise to a change in the fixed charge position and could give mobility fluctuations without carrier trapping. A summation of such RTSs will also give rise to 1/f noise, not related to carrier number fluctuation but associated with a change in scattering (on a slow time scale by the atomic displacements) and, hence, with mobility fluctuations.

V. CONCLUSION

It was found that for conventional applied drain voltages (i.e. higher than about 30 -40 mV) the carrier number fluctuations always explain the flicker noise behavior. An original theoretical approach is constructed, leading to improved expressions which demonstrates that the experimental flicker noise behavior may be completely explained through the Coulomb scattering mechanism at very low drain biases, suggesting that in the investigated polarization interval, the 1/f noise mechanism may have a different origin than for the step-like behaviors observed in the drain current transfer characteristics. The proposed model leads to a full diagnostic tool from weak to moderate inversion in order to discriminate the origin of the 1/f noise for temperatures lower than 40 K and at very low drain bias operation if no step-like effects occur.

Fig. 1

 1 Fig. 1 Drain current normalized by the applied drain bias characteristic as a function of the applied gate voltage for different drain biases.

Fig. 2

 2 Fig. 2 Normalized transconductance as a function of the applied gate voltage from two different drain biases, i.e., VDS = 100 mV and 500 V.

Fig. 3

 3 Fig. 3 Typical application of noise parameters estimation.

Fig. 4

 4 Fig. 4 Drain current versus time for VDS = 1 mV and VGS = 0.7 V. RTS switching may be observed but no clear correlation with the Lorentzian observed from the noise frequency domain representation can be made.

Fig. 5

 5 Fig. 5 Input referred 1/f noise levels as a function of the applied gate voltage at fixed VDS of -50 mV and at 10 K operation. In inset: normalized drain current noise versus the drain current.

Fig. 8 .

 8 Fig. 8. Input referred 1/f noise levels as a function of the applied VDS bias at fixed VGS of 0.7 V and at 10 K operation.

Fig. 10 .

 10 Fig. 10. Input referred 1/f noise levels as a function of the applied drain bias at fixed VGS of 0.5 V and at 10 K operation for a n-channel device.

  suggests that the responsible transport mechanism for 1/f noise and for the step-like current behavior observed may have different origins. Moreover, the RTS observed in Fig.4firstly suggests that the 1/f noise should be related to carrier trapping/detrapping. This hypothesis is contradicted by the experimental evolution of the flicker noise with a is related to the mobility fluctuation mechanism.

Table

Table 3

 3

of

[START_REF] Boudier | Discussion of the flicker noise origin at very low temperature and polarisation operation[END_REF]

]:

Table

Summary of µ and n+µ models as a function of IDS and gm weak to moderate inversion

	n+µ	S	3/2 m   1 4 _ D I c dn g    FB vv gs S   	2	(1)
									3/2
	µ		S	v	gs		6_ c dµ	I	DS	2	(2)
							fg
									m

ACKNOWLEDGMENT

This work was accomplished in the framework of a collaboration agreement between imec and GREYC. The devices have been processed in the frame of imec's Core Partner Program on Nanowire Logic Devices.


Sergio Cabello
email: sergio.cabello@fmf.uni-lj.si

Colin De Verdière
email: eric.colindeverdiere@u-pem.fr

Hardness of Minimum Barrier Shrinkage and Minimum Installation Path

Keywords: installation path, activation network, barrier problem, NP-hardness

In the Minimum Installation Path problem, we are given a graph G with edge weights w(•) and two vertices s, t of G. We want to assign a non-negative power p : V → R ≥0 to the vertices of G, so that the activated edges {uv ∈ E(G) | p(u) + p(v) ≥ w(uv)} contain some s-t-path, and minimize the sum of assigned powers. In the Minimum Barrier Shrinkage problem, we are given, in the plane, a family of disks and two points x and y. The task is to shrink the disks, each one possibly by a different amount, so that we can draw an x-y curve that is disjoint from the interior of the shrunken disks, and the sum of the decreases in the radii is minimized.

We show that the Minimum Installation Path and the Minimum Barrier Shrinkage problems (or, more precisely, the natural decision problems associated with them) are weakly NP-hard.

Introduction

Let X be a subset of the plane, let x and y be points in X, and let SS be a family of shapes in the plane. An x-y curve is a curve in R 2 with endpoints x and y. We say that SS separates x and y in X if each x-y curve contained in X intersects some shape from SS. Let D(c, r) denote the open disk centered at c with radius r.

In this work we show that the following two decision problems are weakly NP-hard. This means that in our reduction we will use numbers that are exponentially large, but have polynomial length when written in binary.

Minimum Barrier Shrinkage.

Input: a family {D(c i , r i ) | i = 1, . . . , n} of n open disks; two points x, y ∈ R 2 ; a real number C.

Output: Whether there exist shrinking values δ 1 , . . . , δ n ≥ 0 such that their cost i δ i is at most C and the family of open disks {D(c i , r i -δ i ) | i = 1, . . . n} does not separate x and y in R 2 .

Minimum Installation Path.

Input: a graph G = (V, E) with positive edge weights w : E → R >0 ; two vertices s and t of G; a real number C. Output: Whether there exists an assignment of powers p : V → R ≥0 to the vertices such that its cost v∈V p(v) is at most C and the activated edges E(p) = {uv ∈ E | p(u)+p(v) ≥ w(uv)} contain an s-t-path.

We next discuss the motivating and closest related work.

Minimum barrier shrinkage. Kumar, Lai and A. Arora [START_REF] Kumar | Barrier coverage with wireless sensors[END_REF] introduced the following barrier resilience problem in the plane. The input is specified by a domain X ⊆ R 2 , a family D of disks in R 2 , and two points x and y in X. The task is to find an x-y curve in X that intersects as few disks of D as possible, without counting multiplicities. An alternative statement is that we want to find a minimum cardinality subfamily D ⊆ D such that D \ D does not separate x and y in X. The intuition is that we have sensors detecting movements from x to y, and we want to know how many sensors can suffer a total failure and still any agent moving from x to y within X is detected by some of the remaining sensors.

Kumar, Lai and A. Arora [START_REF] Kumar | Barrier coverage with wireless sensors[END_REF] showed that the problem can be solved in polynomial time when the domain X is a vertical strip bounded between two vertical lines and , the point x lies above and the point y lies below all disks of D. Let us call this scenario the rectangular scenario. The main insight is to consider the intersection graph G defined by D ∪ { , } and to note that the solution is the maximum number of -internally vertex-disjoint paths in G. Thus, the problem can be solved in polynomial time by solving maximum flow problems. The same argument works for any family of shapes SS, not just disks, as far as each shape of SS is connected.

Despite the claim in the preliminary version [START_REF] Kumar | Barrier coverage with wireless sensors[END_REF] of [START_REF] Kumar | Barrier coverage with wireless sensors[END_REF], we do not know whether the barrier resilience problem can be solved exactly in polynomial time when the domain X is all of R 2 . In fact, we know that when X = R 2 and the family D of disks is replaced by some other family SS of shapes, the problem is NP-hard [START_REF] Alt | Minimum cell connection in line segment arrangements[END_REF][START_REF] Korman | On the complexity of barrier resilience for fat regions and bounded ply[END_REF][START_REF] Kuan-Chieh | On barrier resilience of sensor networks[END_REF]. The difference between the strip and the whole plane is that in the former case we can use Menger's theorem to relate the number ofpaths in the intersection graph of SS ∪ { , } to the -vertex connectivity, but no such statement applies to cycles that "separate" x and y. The computational complexity of the barrier problem in the plane for (unit) disks and (unit) squares is a challenging open problem, and several approximation algorithms have been devised [START_REF] Bereg | Approximating barrier resilience in wireless sensor networks[END_REF][START_REF] Yu | Approximating barrier resilience for arrangements of non-identical disk sensors[END_REF][START_REF] Korman | On the complexity of barrier resilience for fat regions and bounded ply[END_REF].

Modeling the fact that sensors are less reliable further away from their placement, Cabello et al. [START_REF] Cabello | Minimum shared-power edge cut[END_REF] considered the problem of minimizing the total shrinkage of the disks such that there is an x-y curve disjoint from the interior of the disks. This is precisely the problem Minimum Barrier Shrinkage. Cabello et al. also provided an FPTAS for the rectangular scenario. The algorithm uses the connection to vertex-disjoint paths.

We believe that showing NP-hardness for the problem Minimum Barrier Shrinkage is interesting because of the computational complexity of two closely related problems, the barrier resilience problem for X = R 2 and the minimum barrier shrinkage problem in the rectangular scenario, are unknown.

Minimum installation path.

There is a rich literature on so-called Activation Network problems. The task is to assign a power p(v) to each vertex v of an edge-weighted graph G = (V, E) so that the activated edges satisfy a certain connectivity property, such as for example spanning the whole graph. Whether an edge uv is activated depends only on p(u) and p(v). In the most general scenario, one only assumes an oracle telling, given p(u) and p(v), whether u and v are activated, together with a natural monotonicity constraint: if some choice of p(u) and p(v) activates uv, then increasing the powers at u and v still leaves uv activated. In many cases, the following simplifying assumption is made: the possible powers at the vertices are discretized as a finite set of values, denoted by D (the domain). See the survey by Nutov [START_REF] Nutov | Activation network design problems[END_REF] for an overview of the area.

In this context, Panigrahi [13, Section 4.1] considered the Minimum Activation Path problem: the connectivity constraint is that the activated edges must include a path between two fixed vertices s and t of G. He provided an algorithm with running time O(poly(n, |D|)), where n is the number of vertices of G and D is the finite domain of values for the power assignments.

Compared to the problem studied by Panigrahi, our Minimum Installation Path has two differences. First, power assignments are not discretized and can be arbitrary nonnegative real numbers. Second, whether an edge uv is activated is simply determined by whether p(u) + p(v) ≥ w(uv). In this article, we show that the Minimum Installation Path is weakly NP-hard. We also provide a simple fully polynomial time approximation scheme (FPTAS) relying on the algorithm by Panigrahi [START_REF] Panigrahi | Survivable network design problems in wireless networks[END_REF].

Our weak NP-hardness result of the Minimum Installation Path problem is consistent with the result of Panigrahi. In our reduction, we use large integer weights: they have a polynomial bit length, but they are exponentially large. Taking D = Z ∩ [0, max uv w(uv)] in the algorithm of Panigrahi, one only gets a pseudopolynomial time algorithm for such instances. This is consistent with a weakly NP-hardness proof.

In a similar vein, we remark that Alqahtani and Erlebach [START_REF] Hasna | Minimum activation cost node-disjoint paths in graphs with bounded treewidth[END_REF] presented algorithms parameterized by the treewidth of the graph in the case where the goal is to activate k node-disjoint st-paths, or node-disjoint paths between k pairs of terminals. See also Lando and Nutov [START_REF] Lando | On minimum power connectivity problems[END_REF] and Althaus et al. [START_REF] Althaus | Power efficient range assignment for symmetric connectivity in static ad hoc wireless networks[END_REF].

Relation between the problems. We are not aware of any polynomial-time reduction from one problem to the other. Nevertheless, the NP-hardness proofs for both problems are very similar. The underlying connection between both problems is the following classical property: in a planar graph G = (V, E), a set of edges F ⊂ E is a minimum s-t cut if and only if, in the dual graph G * , the edges {e * | e ∈ F } form a shortest cycle separating the face s * from the face t * . This relation does not directly provide a reduction even in the case of planar graphs, but does inspire the adaptation we make. Actually, our hardness proof for Minimum Barrier Shrinkage reuses components of the hardness proof for Minimum Installation Path; we reformulate some special instances of Minimum Barrier Shrinkage in terms of graphs and then remark that each reformulated instance is equivalent to an instance of Minimum Installation Path.

Organization. It seems more convenient to present the NP-hardness of Minimum Installation Path first. We achieve this in Section 2, together with an FPTAS for this problem. Then, in Section 3, we show that the Minimum Barrier Shrinkage problem is NP-hard.

Minimum installation path

In this section we study the complexity of the Minimum Installation Path problem is NP-hard. We first provide a simple FPTAS for this problem, and then prove that it is weakly NP-hard.

A simple FPTAS

As a side note, we show that the main idea used by Cabello et al. [START_REF] Cabello | Minimum shared-power edge cut[END_REF] can be adapted to lead to a simple FPTAS for Minimum Installation Path. Let us consider an instance of that problem. Lemma 1. In polynomial time, we can compute the smallest value λ such that setting p(v) = λ for all vertices v of G activates at least one st-path.

Proof. Whether one st-path is activated by the power assignment p(v) = λ (for each vertex v) depends only on the set of activated edges. So, for some edge uv, the minimum value of λ activating at least one st-path is the minimum value of λ activating edge uv. In other words, the minimum value of λ is necessarily of the form w(uv)/2 for some edge uv. So, for each edge uv, we determine whether putting power w(uv)/2 to all vertices activates an st-path, and return the smallest value that does so. Lemma 2. Let OPT be the optimum value of the Minimum Installation Path instance. Then:

1. in an optimal solution, the power assigned to every vertex is at most nλ,

where n is the number of vertices of the input graph G; 2. λ ≤ OPT.

Proof.

1. OPT ≤ nλ because the definition of λ implies a feasible solution of cost nλ. This implies (1); 2. λ ≤ OPT because otherwise, some st-path would be activated by some powers strictly smaller than λ at each vertex, contradicting the definition of λ.

Proposition 3. Minimum Installation Path admits an FPTAS.

Proof. Let ε > 0 be given. We first compute λ using Lemma 1. Then we apply the algorithm by Panigrahi [13, Section 4.1] to the instance, in which the domain is defined by

D = {kελ/n | k = 0, . . . , n 2 /ε}.
By Lemma 2(1), we obtain a feasible solution to the original problem, the cost of which is within an additive error of at most ελ/n per vertex from OPT, hence with an additive error of at most ελ overall. By Lemma 2(2), this is at most εOPT. Clearly the running time is polynomial in n and 1/ε. We can readily extend this argument to more general activation functions. For example, assume that each edge uv is activated if and only if α(uv)p(u) + β(uv)p(v) ≥ w(uv), for some positive constants α(uv), β(uv), and w(uv). (Our setup corresponds to α(uv) = β(uv) = 1.) The same argument as above shows that this extended version of Minimum Installation Path admits an FPTAS.

Greedy solution in a path

In the rest of Section 2, we focus on proving NP-hardness of Minimum Installation Path. We first consider the particular case of a path.

Consider a graph G and a path π = v 0 , . . . , v n in G. We define greedily a power assignment p * π on the vertices of G to activate π, in a way that power is pushed forward along π as much as possible. Formally, the greedy power assignment along π is

p * π (v) =      0 if v does not belong to π or v = v 0 , 0 if v = v i , i > 0 and p * π (v i-1 ) ≥ w(v i-1 v i ), w(v i-1 v i ) -p * π (v i-1 ) if v = v i , i > 0 and p * π (v i-1 ) < w(v i-1 v i ).
(1) For a power assignment p, let cost(p) denote the total cost of p, namely, the sum of the powers at the vertices. For path π, let opt(π) be the cost of the minimum cost power assignment that activates π. The following lemma tells that the greedy power assignment along π has minimum cost to activate π.

Lemma 4. For each path π, cost(p * π ) = opt(π). Proof. It is clear that p *
π activates all the edges of π. Let p be another power assignment activating all edges of π. We have to show that cost(p * π ) ≤ cost(p). We can assume that p(v) = 0 at all vertices v outside π. Otherwise, we change p to have this property. This reassignment of power would decrease the cost and would keep activating the path π.

The strategy is to gradually transform p into p * π while keeping all edges of π activated and without increasing the value of cost(p). The property cost(p * π ) ≤ cost(p) is trivially correct if p = p * π . So assume p = p * π and let i be the smallest integer such that p(v i ) = p * π (v i ). Because all edges are activated, and by construction of p * π , we must have

p(v i ) > p * π (v i ). Let ∆ = p(v i ) -p * π (v i ) > 0.
There are two cases:

• Assume i ≤ n -1. Update p by decreasing p(v i ) by ∆ and increasing p(v i+1 ) by ∆. Since each edge of π is activated by p * π and by p before this transformation, each edge of π is still activated by the new p. Moreover, cost(p) is unchanged.

• Assume i = n. Update p by decreasing p(v n ) by ∆. Again, each edge of π is still activated. The cost has decreased by ∆.

This transformation does not increase the value of cost(p). Moreover, the new power assignment coincides with p * π on vertices v 0 , . . . , v i . Thus, after a finite number of steps, p = p * π . This proves the lemma.

For the path

π = v 0 , . . . , v n , let ϕ(π) = p * π (v n ) ≥ 0. That is, ϕ(π)
is the power assignment given by the greedy power assignment along π to the final vertex. Since p * π (v n ) depends on p * π (v n-1 ), we have the following. Lemma 5. Let π be the path v 0 , . . . , v n and let π be the path v 0 , . . . , v n , u. (Thus, π extends π by an additional edge

v n u.) Then ϕ(π ) = max{0, w(v n u) - ϕ(π)} and opt(π ) = opt(π) + ϕ(π ).
Proof. From the definition of the greedy power assignment along π and π , the power assignments p * π and p * π differ only at vertex u. We have:

ϕ(π ) = p * π (u) = max{0, w(v n u) -p * π (v n )} = max{0, w(v n u) -p * π (v n )} = max{0, w(v n u) -ϕ(π))}.
This proves the claim for ϕ(π ). Because of Lemma 4 for π and π we also get

opt(π ) = cost(p * π ) = cost(p * π ) + p * π (u) -p * π (u) = opt(π) + ϕ(π ) -0.
A consequence of Lemma 4 is the following integrality property.

L + 3a1 L + a1 L + 2a2 L + 2a2 L + 3a2 L + a2 L + 2a3 L + 2a3 L + 3a3 L + a3 L + 2a4 L + 2a4 L + 3a4 L + a4 2b

The reduction

Now we provide the reduction. The reduction is inspired by the reduction used to show that the restricted shortest path problem is NP-hard; this seems to be folklore and attributed to Megiddo by Garey and Johnson [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]Problem ND30]. We use the notation [n] = {1, . . . , n} and reduce from the following problem.

Subset Sum

Input: a sequence a 1 , . . . , a n of positive integers and a positive integer b. Question: is there a set of indices

I ⊆ [n] such that i∈I a i = b?
The problem Subset Sum is one of the standard weakly NP-hard problems that can be solved in pseudopolynomial time via dynamic programming [7, Section 4.2]. In particular, when the numbers a i are bounded by a polynomial in n, the problem can be solved in polynomial time.

Set L to be an integer strictly larger than 2 i∈[n] a i . Then, for each I ⊆ [n] we have 2 i∈I a i < L.

We construct a graph G = G(a 1 , . . . , a n , b) as follows (see Figure 1). G will include vertices s, t, u 1 , . . . , u n . Let us use the notation u 0 = s. For each i ∈ [n], we put between u i-1 and u i two paths, each of length two, one path with weights L + 2a i and L + 2a i , and the other path with weights L + a i and L + 3a i , as we go from u i-1 to u i . Finally, we put the edge u n t with weight 2b. This finishes the construction of G.

a i + i∈I a i .
Proof. Consider the two paths, each of length two, connecting u i-1 to u i . The upper choice at i is the path with weights L + 2a i ; similarly, the lower choice at i is the path with weights L + a i and L + 3a i . See Figure 2.

Assume that we have a path π that goes from s = u 0 to u i-1 with ϕ(π ) ≤ L. Let π u be the concatenation of π with the upper choice, and let π be the concatenation of π with the lower choice. Because of Lemma 5, we obtain that opt(π u ) = opt(π )+L+2a i and ϕ(π u ) = ϕ(π ), while opt(π ) = opt(π )+L+3a i and ϕ(π ) = ϕ(π ) + 2a i . See Figure 2. Here, the assumption ϕ(π ) ≤ L has been important to ensure that in using Lemma 5 the maximum defining ϕ(•) is not at 0. It easily follows by induction on i that, for each path π from s = u 0 to u i , we indeed have ϕ(π ) ≤ i j=1 2a i , and thus the hypothesis is fulfilled for each

lower choice upper choice L + 2a i L + 2a i L + 3a i L + a i L + 2a i L + 2a i c r L + 3a i L + a i L + a i -r c + L + a i -r c + L + 3a i r + 2a i u i-1 u i opt(π ) ϕ(π ) c + L + 2a i r L + 2a i -r c + L + 2a i -r c r
i ∈ [n].
The intuition here is that the lower choice has a larger cost, but keeps more power at the extreme of the prefix path for later use. See Figure 3 for a concrete example showing the values opt(π ) and ϕ(π ) for paths π from s = u 0 to u i . It also helps understanding the idea behind the reduction.

Consider now a path π from s = u 0 to u n . Let I be the set of indices i ∈ [n] where the path takes the lower choice at i. From the previous discussion and a simple induction we have

opt(π) = i∈[n]\I (L + 2a i ) + i∈I (L + 3a i ) = nL + i∈[n] 2a i + i∈I a i and ϕ(π) = 2 i∈I a i ≤ L.
Since all the paths from s to u n must follow the upper or lower choice at each i ∈ [n], the result follows.

Lemma 8. For any real numbers A and B we have We have to decide whether there is an assignment of power with cost nL+2 i a i +b = 115 that activates some s-t path. Bottom: pairs (opt(π ), ϕ(π )) for all the s-u i paths π .

A + max{2B -2A, 0} ≤ B =⇒ A = B.
Proof. We show that the instance for Subset Sum has a positive answer if and only if in the graph G = G(a 1 , . . . , a n , b) there is a power assignment with cost at most C := nL + 2 i∈[n] a i + b that activates some path from s to t.

Assume that the exists a solution for the instance to the Subset Sum problem. This means that we have some I ⊆ [n] such that i∈I a i = b. Because of Lemma 7, there exists a path π from s = u 0 to u n with optimal installation cost opt(π) = nL + 2 i∈[n] a i + i∈I a i = C and ϕ(π) = 2b. Because of Lemma 4, this means that the power assignment p * π has cost cost(p * π ) = C, activates all edges of π, and assigns power p * π (u n ) = ϕ(π) = 2b to vertex u n . Such power assignment p * π also activates the edge u n t because it has weight 2b = p * π (u n ). (In particular, the vertex t gets power 0.) Assume now that there is a power assignment p ≥ 0 with cost at most C that activates a path π from s to t. Let π be the restriction of π from s to u n . Because of Lemma 5 and using that the power assignment p activates π , we have opt(π

) + max{2b -ϕ(π), 0} = opt(π ) ≤ cost(p ) ≤ C. (2)
Because of Lemma 7, there exists some

I ⊆ [n] such that opt(π) = nL + 2 i∈[n] a i + i∈I a i and ϕ(π) = 2 i∈I a i .
Substituting in (2), for such I ⊆ [n] we have

nL + 2 i∈[n] a i + i∈I a i + max 2b -2 i∈I a i , 0 ≤ C = nL + 2 i∈[n] a i + b.
This means that

i∈I a i + max 2b -2 i∈I a i , 0 ≤ b.
Because of Lemma 8 we conclude that i∈I a i = b, and the given instance to Subset Sum problem has a solution.

Minimum Barrier Shrinkage

In this section, we show that the Minimum Barrier Shrinkage problem is NP-hard. The structure of the proof is very similar to the proof given in Section 2.3 for the NP-hardness of the problem Minimum Installation Path.

We first give the construction assuming that we can compute algebraic numbers to infinite precision. Then we explain how an approximate construction with enough precision suffices and can be computed in polynomial time. (Recall that disks are taken as open sets.) Thus, the penetration depth equals the minimum total shrinking of the disks so that a curve can pass between the two disks.

We reduce again from Subset Sum. Consider an instance I of Subset Sum given by a sequence a 1 , . . . , a n of positive integers and a positive integer b. Set L to be an integer strictly larger than 2 i∈[n] a i . Then, for each I ⊆ [n] we have 2 i∈I a i < L. Set C = nL + 2 i∈[n] a i + b and λ = 10C. We will construct an instance to Minimum Barrier Shrinkage problem such that it has a solution if and only if the instance I for Subset Sum has a solution.

Figure 5 shows the overall idea of the construction. Most of the action is happening around the filled (blue and green) disks. The remaining white disks create corridors to communicate from one side to the other of the filled disks. To provide a feasible solution of cost at most C, we have to indicate how to shrink the disks for a total radius of at most C and provide an x-y curve in the plane that does not touch the (interior of the) shrunken disks.

In our construction, no point of the plane will be covered by more than two disks. In such a case, the x-y curve can be described combinatorially by a sequence of pairs of disks such that, for each pair (D, D ), the curve passes between D and D , after shrinking.

If the penetration depth of two disks is at least λ = 10C, then, in any shrinking of the disks with total cost at most C, those two disks keep intersecting, which means that we cannot route the x-y curve between those two disks. More precisely, the segment connecting the centers of such disks cannot be crossed by the x-y curve. In the drawings we indicate this with a thick segment connecting the centers of the disks.

The main part to encode the instance, around the filled disks, consists of the following disks. See Figures 6 and7.

• For i = 0, . . . , n, a disk D i of radius 4λ centered at ((4λ) • 2i, 0);

• for each i ∈ [n], a disk D i of radius λ centered at ((4λ) • (2i -1), 0);
• for each i ∈ [n], a disk A i (for above) of radius 3λ placed such that the center is above the x-axis, and the penetration depth of (A i , D i-1 ) and (A i , D i ) is L + 2a i ; this means that the distance between center(A i ) and center(D i-1 ) is 7λ -(L + 2a i ), and the distance between center(A i ) and center(D i ) is 7λ -(L + 2a i );

• for each i ∈ [n], a disk B i (for below ) of radius 3λ placed such that the center is below the x-axis, the penetration depth of (B i , D i-1 ) is L+a i and the penetration depth of (B i , D i ) is L + 3a i ; this means that the distance between center(B i ) and center(D i-1 ) is 7λ -(L + a i ) and the distance between center(B i ) and center(D i ) is 7λ -(L + 3a i );

• a disk A n+1 of radius 3λ placed such that the center is above the x-axis, the x-coordinate of center(A n+1 ) is (4λ) • (2n + 1), and the penetration depth of (A n+1 , D n ) is 2b; A n+1 is one of the green disks in the figures;

• a disk B n+1 of radius 3λ placed such that the center is below the x-axis, the x-coordinate of center(B n+1 ) is (4λ) • (2n + 1), and the penetration depth of (B n+1 , D n ) is 2b; B n+1 is another of the green disks in the figures;

• for each i ∈ [n + 1], a disk A i of radius 3λ centered at ((4λ) • (2i -1), 8λ) and a disk B i of radius 3λ centered at ((4λ) • (2i -1), -8λ).

For i ∈ [n], the block B i consists of the disks D i-1 , D i , D i , A i , A i , B i and B i .
We also define the block B n+1 as the group of disks D n , A n+1 , A n+1 , B n+1 and B n+1 . Note that the blocks B i and B i+1 , for i ∈ [n], share the disk D i .

For each i ∈ [n + 1], we make a path of disks of radius 3λ, starting from A i and finishing with B i , where any two consecutive disks have penetration depth at least 3λ. The disks in these paths are pairwise disjoint for different indices i, and disjoint from the rest of the construction. The disks in each such path can be centered along a 5-link axis-parallel path, and it uses O(i) disks. See Figure 5. We denote the path of disks for the index i ∈ [n + 1] by Π i . For later use, we place a point y i in the "tunnel" between the paths Π i and Π i+1 . See Figure 5. Lemma 10. For each i ∈ [n], the disks D i , A i and B i are pairwise disjoint. Moreover, the penetration depth of the pairs

(D i-1 , D i ), (D i , D i ), (A i , A i ) and (B i , B i ) is at least λ.
For B n+1 , the disks A n+1 and B n+1 are disjoint and the penetration depth of the pairs (A n+1 , A n+1 ) and (B n+1 , B n+1 ) is at least λ.

Proof. We consider only the case i ∈ [n]. The arguments for B n+1 are similar. The penetration depth of the pairs (D i-1 , D i ) and (D i , D i ) is λ by construction.

Consider the disk Ãi of radius 3λ centered at ((4λ) • (2i -1), 5λ) and the disk Bi of radius 3λ centered at ((4λ) • (2i -1), -5λ). See Figure 8. We will compare B i to Bi ; note that they have the same size, just a different placement. The argument for A i is the same.

The penetration depth of the pairs ( Bi , D i-1 ) and ( Bi ,

D i ) is 3λ + 4λ -(5λ) 2 + (4λ) 2 = (7 - √ 41)λ ≈ 0.59687λ,
while the penetration depth of ( Bi , B i ) is exactly 3λ. The disk D i is at distance λ from Bi . Since the penetration depth of (B i , D i-1 ) and (B i , D i ) is at most L + 3a i ≤ C = λ/10, these penetration depths are smaller than the penetration depths of ( Bi , D i-1 ) and ( Bi , D i ), namely, between 0 and 0.59687λ. See Figure 9. As can be seen on the figure (and proved by a slightly involved computation), this implies that B i and D i are disjoint, and that the disk B i contains the center of B i . The latter fact implies that the penetration depth of (B i , B i ) is at least 3λ.

From Lemma 10 we conclude that, in any solution with cost under λ = 10C, the x-y curve cannot cross the segments connecting center(D i-1 ) and center(D i ), the segments connecting center(A i ) and center(A i ), nor the segments connecting center(B i ) and center(B i ), for each i ∈ [n + 1]. Furthermore, it cannot cross the path Π i connecting A i to B i , for each i ∈ [n + 1]. This implies that, at each block B i , we have to decide whether the x-y curve goes above (crossing A i before shrinking) or below (crossing B i before shrinking). See Figure 10 for one such choice.

So, in a nutshell, the strategy is to reformulate the problem in terms of graphs, and to note that the instance is equivalent to the Minimum Installation Path in that graph. Let X i = A i or X i = B i , depending on the choice of how to route the x-y curve. If X i = A i , then the x-y curve, after shrinking the disks, passes between D i-1 and A i , and also between D i and A i . If X i = B i , then the x-y curve, after shrinking the disks, passes between D i-1 and B i , and also between D i and B i . Note that we can assume that the x-y curve passes between two disks at most once. Moreover, for each disk D, the x-y curve passes between D and another disk at most twice. Once we decide the combinatorial routing of the x-y curve, that is, once we select X 1 , . . . , X n , X n+1 , then greedily shrinking the disks gives an optimal solution, similarly to Lemma 4: it pays off to push the shrinking towards disks that are crossed later by the x-y curve. That is, to pass between D 1 and X 1 , it pays off to do not shrink D 1 , as it is never crossed again, and shrink X 1 just enough to pass in between. Similarly, it pays off to shrink D 2 to pass between D 2 and X 1 , because X 1 will not be crossed again later on. In general, to pass between D i-1 and X i it pays off to reduce X i just enough to pass between them, taking into account how much D i-1 was already shrunken, and to pass between X i and D i it pays off to reduce D i just enough to pass between them, taking into account how much X i was already reduced.

Let D = D(I) be the set of all disks in the constructed instance. Proof. We construct a graph G as follows. We make a node for each connected component of R 2 \ D that may be crossed by the x-y curve after shrinking disks for a cost strictly smaller than λ = 10C. This means that we have the following nodes in the graph:

• a node for the cell containing x, which we call x also;

• a node for the cell containing y, which we call y also;

• a node called α i for the region bounded between the disks

D i-1 , D i , A i (i ∈ [n]);
• a node called β i for the region bounded between the disks

D i-1 , D i , B i (i ∈ [n]);
• a node for the cell that contains y i (i ∈ [n]), that is, the tunnel bounded by Π i and Π i+1 ; we call the node y i also.

We put an edge between two nodes whenever we can pass from one region to the other passing between two disks with penetration strictly below λ = 10C. See Figure 11 for the resulting graph, G . This graph G is essentially the graph G(a 1 , . . . , a n , b) used in Section 2.3. (The only difference is that, in G , we have two parallel edges from y n to y, instead of a single edge.)

We assign a weight to each edge of G equal to the penetration depth of the pair of disks that separate the cell. For example, the edges y i-1 α i and α i y i have weight L + 2a i (i ∈ [n]), the edge β i y i has weight L + 3a i (i ∈ [n]), and the two parallel edges y n y have weight 2b.

There is a simple correspondence between power assignments p(•) that give a feasible solution for Minimum Installation Path(G , x, y, C) and the reduction in radii for feasible solutions for Minimum Barrier Shrinkage(D, x, y, C), as follows:

• the decrease in radius of D i corresponds to the power p(y i ) (i ∈ [n]);

• the decrease in radius of A i corresponds to the power p(α i ) (i ∈ [n]);

• the decrease in radius of B i corresponds to the power p(β i ) (i ∈ [n]);

• the decrease in radius of D 0 corresponds to the power p(x);

• we may assume that at most one of the disks A n+1 and B n+1 is shrunken; the decrease in radius of A n+1 or B n+1 , whichever is larger, corresponds to the power p(y);

• we may assume that all other disks are not shrunken. The second part of the lemma follows from the above correspondence and from Lemma 6.

The disks D, as described, cannot be constructed in polynomial time in a Turing machine because the centers of the disks do not have integer (or rational) coordinates. More precisely, the centers of A i and B i (i ∈ [n + 1]) are solutions to a system of equations with degree-two polynomials. However, we can scale up the numbers involved in the construction, and then round the non-integer numbers, to obtain a polynomial-time construction, doable in a Turing machine: The centers of the disks in D \ {A 1 , . . . , A n+1 , B 1 , . . . , B n+1 } are integers bounded by O(λ) = O(nL). For each i ∈ [n + 1], we compute the centers of the disks A i and B i up to a precision of at least ε = 1 6(n+1) . Thus, the coordinates of the centers are multiples of ε. Let Âi and Bi be the resulting disks; they have the same radius, 3λ, but have been displaced by at most ε with respect to the original position in the construction. Let D be the set of disks obtained from D, where each A i , B i are replaced with Âi , Bi (i ∈ [n + 1]).

We consider instances of Minimum Barrier Shrinkage. If the instance (D, x, y, C) is positive, then the instance ( D, x, y, C + 1/3) is also positive (because each of the 2(n+1) disks are moved by at most ε, so the total displacement is at most 1/3), which implies that the instance (D, x, y, C + 2/3) is also positive (by the same argument), which in turn also implies that the instance (D, x, y, C) is positive (by Lemma 11). So, the instances (D, x, y, C) and ( D, x, y, C + 1/3) are equivalent.

Scaling all values in the construction of D (coordinates and radii) by 1/ε, we get a construction where the disks have centers with integer coordinates, the radii are integers, and the whole construction can be constructed in polynomial time.

Note that it is not clear whether the Minimum Barrier Shrinkage problem belongs to NP. Indeed, if some triples of disks intersect, a priori it seems that a solution may have to reduce the radius of some disks by non-rational numbers, and decisions at different parts depend on each other, which could increase the algebraic degree of the numbers telling how much to decrease the radii.

Remark. A similar statement can be done for axis-parallel squares. For this we have to place the overlapping squares in such a way that the overlap region, an axis-parallel rectangle, has width equal to the value we want to encode (L + a i , L + 2a i , L + 3a i or 2b). In such a case we do not run into the numerical issues with the centers because all the coordinates can be taken directly to be integers.

Lemma 6 .

 6 Assume that the weight function w : E(G) → R >0 takes only integer values, and that C is also an integer. Then, for any α ∈ [0, 1), Minimum Installation Path(G, w, s, t, C) has a positive answer if and only if Minimum Installation Path(G, w, s, t, C + α) has a positive answer. Proof. Assume that Minimum Installation Path(G, w, s, t, C + α) is has a positive answer. Consider a power assignment p corresponding to a feasible solution of minimum cost (at most C + α); let π be an s-t path activated by p. Because of Lemma 4 we have cost(p) = opt(π) = cost(p * π ). From the inductive definition (1) of p * π , we see that p * π assigns integral powers to all vertices, and thus cost(p * π ) = v p * π (v) is an integer, which is at most C. So Minimum Installation Path(G, w, s, t, C) has a positive answer.

Figure 1 :

 1 Figure 1: The graph G when n = 4.

Lemma 7 . 2 i∈I a i and c = nL + 2 i∈

 722 There exists a path π from s to u n in G with opt(π) = c and ϕ(π) = r if and only if there exists I ⊆ [n] such that r =

Figure 2 :

 2 Figure 2: Left: Upper and lower choice at i. Right: the change in opt(π ) and ϕ(π ) depending on whether the path is extended by the upper or the lower choice.

Proof.Theorem 9 .

 9 If A ≤ B, then B -A ≥ 0 and the assumption implies A+(2B -2A) ≤ B, which implies B ≤ A, and thus A = B. If A > B, then B -A < 0 and the assumption implies A + 0 ≤ B, which implies A ≤ B. Thus this cannot happen. The problem Minimum Installation Path is NP-hard.

Figure 3 :

 3 Figure3: Top: The graph G for n = 4 with a 1 , . . . , a 4 = 2, 3, 3, 2 and b = 7, when we take L = 22. We have to decide whether there is an assignment of power with cost nL+2 i a i +b = 115 that activates some s-t path. Bottom: pairs (opt(π ), ϕ(π )) for all the s-u i paths π .

The

  penetration depth of a pair (D(c, r), D(c , r )) of open disks D(c, r) and D(c , r ) is r + r -|c -c |, where |c -c | is the distance between the centers c and c . When no disk contains the center of the other disk, and they intersect, then the intersection D(c, r)∩D(c , r ) is a lens of width equal to the penetration depth. See Figure 4. If we shrink the disks to D(c, r -δ) and D(c , r -δ ), the disks intersect if and only if δ + δ is strictly smaller than the penetration depth.

Figure 4 :

 4 Figure 4: The penetration depth of the pair of drawn disks is the length of the arrow.

Lemma 11 .

 11 The instance I = (a 1 , . . . , a n , b) to Subset Sum has a solution if and only if the instance (D, x, y, C) to Minimum Barrier Shrinkage has a positive answer, where C = nL+2 i∈[n] a i +b. Furthermore, for any α ∈ [0, 1), Minimum Barrier Shrinkage(D, x, y, C) has a positive answer if and only if Minimum Barrier Shrinkage(D, x, y, C + α) has a positive answer.

  This correspondence transforms feasible solutions for Minimum Installation Path(G , x, y, C) into feasible solutions for Minimum Barrier Shrinkage(D, x, y, C), and conversely. So the instances Minimum Installation Path(G , x, y, C) and Minimum Barrier Shrinkage(D, x, y, C) are equivalent.

Theorem 12 .

 12 The Minimum Barrier Shrinkage problem is NP-hard. Proof. Consider an instance (a 1 , . . . , a n , b) for Subset Sum and the associated instance (D, x, y, C) for Minimum Barrier Shrinkage constructed above, with C = nL + 2 i∈[n] a i + b.

Figure 6 :Figure 8 :

 68 Figure 6: Block B i for 1 < i < n; the penetration depths are not to scale. Note that A i has the same overlap with D i-1 and D i , while B i is moved closer to D i . The center of B i is to the right of the (vertical) line through the centers of A i , A i , D i and B i .

Figure 9 :yFigure 10 : 2 Figure 11 :

 910211 Figure9: The gray region shows the position of the centers where the disk B i may be placed, more precisely, the positions for center(B i ) where the penetration depth of (B i , D i-1 ) and (B i , D i ) lies in the interval [0, 0.59687λ]. The blue mark denotes the center of Bi .

Acknowledgments

We would like to thank the reviewers for their careful reading of our manuscript, their suggestions, and pointing out the possibility to get the FPTAS discussed in Section 2.1. This research was partially supported by the Slovenian Research Agency (P1-0297, J1-8130, J1-8155). Part of the research was done while Sergio was invited professor at Université Paris-Est.