Alina Quereilhac
email: alina.quereilhac@inria.fr

Anshuman Kalla
email: anshuman.kalla@inria.fr

Thierry Turletti
email: thierry.turletti@inria.fr

Walid Dabbous
email: walid.dabbous@inria.fr

Easy Ccnx

Easy CCNx experimentation on PlanetLab

Keywords: Experiment management, evaluation, testbed

la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Demonstration

We will demonstrate how NEPI [START_REF] Quereilhac | NEPI: An Integration Framework for Network Experimentation[END_REF] can be used to automate the deployment of CCNx experiments on PlanetLab from a regular laptop computer. To this end, we present a use case scenario where we observe the effects of CCNx caching when simultaneously retrieving a video stream along about ten PlanetLab nodes, associated in series though UDP unicast FIB entries. CCNx source code is obtained from a user specified location, allowing code customization, and is automatically compiled and installed at each node. Nodes are provisioned following user specified criteria, and all CCNx configuration is performed without user intervention during deployment. We are interested in presenting both a poster and a video demonstration on the subject. Further information regarding the described scenario, including a video demo, can be found at: http://nepi.pl.sophia.inria.fr/wiki/nepi/CCNxOnPlanetLabEurope Regarding the topics of the program, we are particularly interested in "Use cases", "Testbed collaboration", and "CCN-related research issues such as naming, routing, security, resource management, etc."


Linking a Social Identity to an IP Address by Arnaud Legout and Walid Dabbous

Linking a social identity such as a name to an IP address is generally believed to be difficult for an individual with no dedicated infrastructure or privileged information. Although an individual's ISP has access to this information, it is kept private except in the case of a legal decision. Similarly, some big Internet companies such as Facebook and Google might be privy to this information but it will never be communicated as it is an industrial secret used for targeted advertisements. In the context of the bluebear project, we show that it is possible for an individual to inconspicuously make the link between social identity and IP address for all Skype users.

The privacy threat that exists online is a growing concern. Most academics and journalists focus on the threat posed by the huge amount of data collected by big companies such as Google or Facebook. However, the case of individuals, with no dedicated infrastructure or privileged information, trying to infringe Internet users' privacy is largely overlooked owing mainly to the misconception that it is impossible for a single individual to spy on Internet users at a large scale. The goal of the bluebear project, led by researchers at Inria in collaboration with researchers at the Polytechnic Institute of New York University (NYU-Poly), is to explore whether individuals can infringe Internet users privacy at a large scale.

In a first study, we have shown that an individual can monitor all BitTorrent downloads in real time for all Internet users without any dedicated infrastructure. To prove this, we collected 148 million IP addresses downloading more than one million contents for 103 days, and managed to identify 70% of users who first insert content in BitTorrent. We have also shown that using Tor, the anonymizing overlay, does not help; Tor does not protect against the exploitation of an insecure application (eg BitTorrent) to reveal the IP address of a TCP stream. Even worse, because Tor sends application data together over a single circuit, the IP address found for a given application can be associated with all other applications of the same circuit. Although profiling Internet users by IP addresses raises ethical concerns, it pales in comparison to profiling by social identity. Associating a social identity to a profile enables very severe privacy infringements that might lead to real world attacks such as blackmail or targeted phishing attacks. We used Skype as a case study to show that an individual can link a social identity and an IP address. In particular, we have shown that an individual can inconspicuously retrieve the IP address of any Skype user. As 88% of Skype users provide a name associated with the account and 82% provide additional information like a country or Web page, most Skype accounts can be directly associated with a social identity, thus making it possible to link social identity and IP address. In addition, we can follow the mobility of Skype users. Interestingly, on a sample of 10,000 random Skype users, we observed that over a two week period 4% of them moved from one country to another, 19% moved from one ISP to another, and 40% moved from one city to another. Therefore, we identified real mobility patterns for a regular Skype user.

Even more of a concern, by tracking the mobility of an Internet user along with the mobility of acquaintances (retrieved from a social network profile like Facebook or LinkedIn) it is possible to track social interactions, that is who an Internet user meets and where. This has worrying implications for both the personal and professional lives of Internet users.

The technique we use to map a social identity to an IP address is based on the identification of specific communication patterns that are inherent to any peer-to-peer system. Therefore, we do not rely on a specific bug in Skype that exposes the IP address, but on the intrinsic peer-to-peer architecture used by Skype and the lack of privacy of the IP protocol used on the Internet. As a consequence, the kind of attacks we have documented can be adapted to most systems that use a peer-to-peer architecture. In addition, it is extremely hard, without a major architectural change to Internet communications, to make such attacks impossible.

Our goal in the next few years is to participate in the design of a more secure, privacy preserving Internet communication infrastructure.

Link: http://planete.inria.fr/bluebear

Figure 1 :

 1 Figure 1: High-level description of the social identity and IP address linkage exploiting Skype.


Djemili Fatiha
email: fatiha.djemili@univ-annaba.dz

Tolba

Damien Magoni
email: magoni@labri.fr

Pascal Lorenz
email: lorenz@ieee.org

Wessam Ajib
email: ajib.wessam@uqam.ca

Energy-efficient power allocation algorithms for mobile wireless sensor networks

Keywords: Mobile wireless sensor networks, transmission power, energy consumption, k-neighborhood, network lifetime, connectivity

This paper proposes new distributed algorithms of adaptive transmit power allocation in wireless sensor networks for improving the efficiency of energy management. The proposed algorithms are based on two fundamental criteria namely: the distance between the sensor and the base station, and the distance between the sensor and its two-hop neighbors. Hence, each sensor can manage its own transmission power according to these two criteria in order to reduce its energy consumption. The proposed algorithms help both extending the network lifetime and reducing the work load of sensors that are located close to the base station. The used sensors are subject to premature battery exhaustion since they relay the traffic of other sensors toward the base station. We also consider the coverage constraint requiring that all regions (or at least some regions) must be always covered. This coverage constraint justifies the choice of two-hop neighbors criterion. Extensive simulation results show the gain obtained by the proposed algorithms in terms of network lifetime, energy consumption and packet delivery success rate.

Introduction

The ultimate goal of wireless sensor networks applied in monitoring fields is to transmit the sensing data from a given target area to a given base station with accepted (or sometimes high) fidelity. However, for extended operation of sensors, it is necessary to overcome the problem of the limitation of the residual energy. This constraint becomes strongly critical when it comes to the hostile environment (toxic or disaster area) because the replacing of the sensor battery is a difficult task. Another constraint that is inherent to mobile sensor networks is the connectivity which allows each sensor to reach the other ones in the network with the multihop technique despite the failure of one or several sensors which may cause a partial or full interruption of the network communication. Therefore, an energy saving plan that takes into account the coverage becomes necessary in order to improve the network lifetime.

We are motivated by the wireless sensor networks where all sensors are mobile. There are three main reasons to consume energy in sensor networks: data transmission, signal processing and hardware operation. In [START_REF] Lai | Reducing radio energy consumption of key management protocols for wireless sensor networks[END_REF], the authors show that 70 percent of the energy consumption is due to data transmission. Hence, to extend the network lifetime, the data transmission should be, energy-wise efficiently managed. The data can be transmitted using several levels of transmission power which allows reducing the energy consumption.

Coverage is a very important issue in sensor networks and one of the most active research fields. It is usually interpreted as how well a sensor network monitors a field of interest. It can be measured in different ways depending on the application as show in [START_REF] Ammari | Coverage in wireless sensor networks: A survey[END_REF]. Coverage is also important in sensor networks in order to maintain the connectivity, often to the neighbors of a node [START_REF] Tonguz | Ad Hoc Wireless Networks -A Communication-Theoretic Perspective[END_REF].

In this paper, we propose distributed algorithms to allocate the transmission power level of a given sensor depending on two criteria: a) its distance from the two-hop neighbors and b) its distance from the base station. The objective of the first criterion consists of preserving the sensor connectivity [START_REF] Sukhatme | Constrained coverage for mobile sensor networks[END_REF]. On the other hand, multi-hop communication introduces a significant amount of overhead for topology management and medium access control. Hence, direct communication is preferred if the sensor is close to the base station. In this case, it becomes more difficult (or even impossible) for these sensors to forward the data of other nodes which require a high rate of energy consumption. In addition, once the energy of the sensors close to the base station is exhausted, the network will be partitioned [START_REF] Qiao | Sensor-aided overlay deployment and relocation for vast-scale sensor networks[END_REF]. The proposed algorithms allow less energy consumption when the sensor reduces its transmission power, and consequently, the network lifetime is extended. The main purpose is to find a compromise between the energy consumption and connectivity. Also, the energy control should operate autonomously, i.e., changing its configuration on the fly as required.

The remainder of this paper is organized as follows. Section 2 is devoted to the related works. Section 3 presents the several models used in this paper and we list the assumptions taken into account. Section 4 describes the proposed algorithms. Section 6 presents and discuss the simulation results. The main conclusions are summarized in Section 7.

Related works

It is widely accepted that the energy conservation is a major issue in wireless sensor networks. In the last decade, several techniques has been developed to reduce the energy consumption. In this section, some significant works are presented.

An effective way to conserve the energy is an adequate transmission power control (TPC). This idea is explored in several papers [START_REF] Kubisch | Distributed algorithms for transmission power control in wireless sensor networks[END_REF] [START_REF] Lin | ATPC: adaptive transmission power control for wireless sensor networks[END_REF][START_REF] Correia | Transmission power control techniques for wireless sensor networks[END_REF]. The main goal of TPC is to reliably deliver the packets with minimum energy consumption and minimum interference. In the recent literature, several control-theoretic approaches have been proposed including robust topology control [START_REF] Hackmann | Robust topology control for indoor wireless sensor networks[END_REF], [START_REF] Alavi | Robust distributed active power control technique for IEEE 802.15.4 wireless sensor networks A quantitative feedback theory approach[END_REF] and model predictive control [START_REF] Witheephanich | Explicitly constrained generalised predictive control strategies for power management in ambulatory wireless sensor network systems[END_REF]. The idea behind robust topology control is the consideration of multi-path effects in the network environment. It is possible to form a network where each node has a robust link with the network. However, this approach is based on RSSI (Radio Signal Strength Indicator) measurements and thus it suffers from the same robustness issues. On the other hand, predictive control model assumes that the system is linear which may be difficult to derive in complex distributed systems. Moreover, linear system controllers fail when the transmission conditions change rapidly.

The literature mentions also another category of techniques that are aiming to achieve power-efficient communication using a sleep/wake-up model known as scheduling model [START_REF] Keshavarzian | Wakeup scheduling in wireless sensor networks[END_REF] [START_REF] Ghosh | Performance of a wireless sensor network MAC protocol with a global sleep schedule[END_REF]. Such type of techniques reduces the spent radio energy in idle state. This is due to the fact that the radio module is turned off when it is not used. An example of the scheduling model is the VBS (Virtual Backbone Scheduling) presented in [START_REF] Zhao | VBS: Maximum Lifetime Sleep Scheduling for Wireless Sensor Networks Using Virtual Backbones[END_REF]. VBS attempts to find an optimal schedule for maximizing the network lifetime. The main purpose is to schedule multiple backbone to work alternatively. TDMA (Time Division Multiple Access) is another scheduling model and it balances, for every node, the energy-saving and the end-to-end delay [START_REF] Pantazis | Energy efficiency in wireless sensor networks using sleep mode TDMA scheduling[END_REF]. In TDMA protocol, each group of nodes is assigned a TDMA slot for communication with the base station. Actually, this allows the nodes to schedule their wake-up slot and to concur with the other broadcasted packets. However, flexibility and scalability are strongly limited on these two last techniques. This is explained by the fact that some constraints in sensor networks are not taken into account, namely: topology changes caused by mobility, node failures, channel conditions, etc.

In [START_REF] Simarpreet | Power Saving MAC Protocols for WSNs and Optimization of S-MAC Protocol[END_REF], the authors propose a new protocol to improve the existing MAC, named S-MAC protocol (Sensor MAC ), in terms of energy efficiency, latency and throughput. Nevertheless, the S-MAC does not give any particular attention to the load balancing, i.e., some nodes are, often, more active than others. Accordingly, the connectivity and robustness can be influenced. Finally, other techniques attempt to reduce the energy consumption through routing protocols [START_REF] Al-Karaki | Routing techniques in wireless sensor networks: a survey[END_REF]. An example of these techniques is the protocol named LEACH (Low Energy Adaptive Clustering Hierarchy) [START_REF] Heinzelman | Energy-efficient communication protocols for wireless microsensor networks (leach)[END_REF]. Basically, LEACH is aiming to reduce the energy consumption. Each sensor in the cluster may elect itself as a cluster-head CH in its time interval based on two criteria: a) the percentage of the needed number of CHs and b) the number of rounds in which this sensor takes the role of CH. Indeed, the location of each sensor must be known. Although this clustering algorithm has achieved a considerable success, it needs, frequently, new cluster construction process. For this reason, LEACH is not scalable, i.e. for passing to a large scale, its application needs additional costs. In order to overcome this drawback, MESH (Maximum Energy Cluster Head ) has been developed [START_REF] Chang | An energy efficient routing mechanism for wireless sensor networks[END_REF]. Nevertheless,the MESH protocol functioning requires a lot of the control messages broadcasted on the network. This way, the network lifetime can be strongly reduced.

Mobility can also be considered as a new challenge to the energy-efficient solutions. Recently, a lot of research works focused on the mobility management within sensor networks. These works can be categorized into two main methods: a) Mobile-Base Station (MBS) and b) Mobile-Data Collector (MBC). The idea behind MBS is to move the base station in the network with the objective of reducing the energy consumption. Indeed, the data collected by the sensor is related to the base station quickly, i.e., without a long time of buffering. In MBC category, the base station plays a leading role in the collect of data. In other words, the mobile base station go toward the sensors to collect the data. This latest is buffered at the sensor until the arrival of the base station [START_REF] Ekici | Mobilitybased communication in wireless sensor networks[END_REF].

Problem description and assumptions

The deterministic deployment of sensors constitutes a major challenge for many WSN applications. This is due to the large number of sensors and to the type of environment where they are deployed. For this, we consider that the sensors are deployed randomly in the target field for a given application.

We study, in this paper, the following energy problem: Problem: Given N mobile sensors deployed with their limited battery charge; how these sensors could remain operational, and so that the residual energy will be maintained as long as possible with the constraint of the network connectivity?

To resolve this problem, it is necessary to introduce some definitions: Definition 1: Two sensors are considered neighbors if the Euclidean distance between them is less than or equal to the communication range Rc. So the communication range is defined as the area in which another node can be located in order to receive data [START_REF] Ammari | Coverage in wireless sensor networks: A survey[END_REF]. Definition 2: The network lifetime represents the time during which the network is operational, whereas the network is considered not operational if the number of dead sensors is greater than 80% [START_REF] Chamam | On the planning of wireless sensor networks: Energy-efficient clustering under the joint routing and coverage constraint[END_REF].

The network can be modeled by undirected graph G(S, L), where S is a finite set of sensors (nodes), and L is a finite set of wireless links (edges) between the pairs of sensors. The set of possible communications is defined as:

L = {(s i , s j ) ∈ S 2 | s j receives the message of s i } (1)
The neighborhood of sensor s i ∈ S is defined as:

N (s i ) = {s j ∈ S | (s i , s j ) ∈ L} (2)
The proposed algorithms need, for each sensor, three We consider that the sensors move according to random waypoint model [START_REF] Navidi | Stationary Distributions for the Random Waypoint Mobility Model[END_REF]. In this model, the mobile sensor movement is described in two dimensions system. Thereby, the Mobile Sensor (MS) moves from its current location to a next randomly selected one in the area. MS travels to the next point (destination) with random speed selected between two limit values (minimum and maximum speed) after waiting some pause time [START_REF] Madsen | Impact of different mobility models on connectivity probability of a wireless ad hoc network[END_REF].

The energy of each sensor is consumed for three raisons: the data acquisition, the communication and the data processing. Hence, The used energy model is given by the following formulas Djemili et al. ( 2007):

E T x = p × (E amp + f s × d n ) (3) E Rx = p × E amp (4) E M x = E d × dm t-1,t (5)
where E T x and E Rx stand for the energy consumed at transmission and at reception respectively. p is the packet size. E amp and f s are coefficients that depend on the used transmitter amplifier model. d is the distance between the sender and the receiver, and n the exponent of path loss. E M x is the energy required to move and E d is the energy consumption per distance unit for movement where dm t-1,t is the traveled distance between times t -1 and t. The proposed model is presented in Fig. 1. We also assume the following points:

1. All the sensors in the network are homogenous in terms of physical characteristics.

2. The base station is stationary.

3. All the sensors in the network are timesynchronized.

4. Each sensor has a unique identifier id.

5. Initially, each sensor has the same energy charge, but the energy consumption of each sensor is different over time.

6. The batteries can not be replaced after the beginning of deployment.

7. We assume ideal MAC layer conditions, i.e., a perfect transmission data.

4 The proposed algorithms

Basic concepts

The proposed algorithms are completely distributed and designed for mobile wireless sensor networks. The main objectives are summarized as follow:

1. Improving the network lifetime by saving the energy consumed by each sensor.

2. Achieving suitable and continuous connectivity.

3. Ensuring good portability by providing a power allocation algorithm that can be easily implemented on many existing routing protocols.

In the following, we present two power allocation algorithms. The first one is based on the distance between the sensors and its two-hop neighbors. The second algorithm considers additionally the distance between the sensor and the base station. Discussions will be given in order to evaluate the two algorithms.

As described above, all the sensors in the network are mobiles. In such network, the sensors move with different speeds. Accordingly, the network topology may be changed due to: a) sensor failure (battery exhaustion), b) wireless link failure, or both cases. In order to allocate dynamically the power level, determining the distance between two wireless sensors is required for the proposed algorithms. Generally, to calculate the distance between sensors, some methods are considered among them: 1) Euclidean distance between wireless sensors, 2) Received Signal Strength Indication (RSSI) of data packets transmitted and 3)Global Positioning System (GPS)or propagation time of radio signals [START_REF] Hoene | Measuring round trip times to determine the distance between wlan nodes[END_REF]. Noting that these methods consume an additional energy for obtaining the location. In order to overcome this limitation, we may call other methods like prediction methods: Kalman prediction or Grey prediction method, etc. The Kalman prediction filtering method often assumes that the target does uniform motion and uniformly accelerated motion, but in practice the sensors can take an arbitrary motion. Although, Grey prediction method is a simple and practical prediction method which focuses on the future behavior of the system. It can dig out the inherent movement law of target through processing historical position information of the moving target that has no limit to target motion, so it can objectively predict the trajectory.

Power Allocatation based on Two-hop neighbors (PA2)

Similar to the work proposed by [START_REF] Sukhatme | Constrained coverage for mobile sensor networks[END_REF], we propose that each sensor communicates with its twohop neighbors. Obviously, the proposed algorithm seeks to reduce the energy consumed by each sensor, but it takes also into account the control of topology by ignoring the neighbors beyond two hops. Therefore, we take the number of hops to join the neighbors (denoted by k ) k = 2 in order to preserve the connectivity. On the one hand, if we take k less than 2 (i.e., k = 1), isolated sensors could be produced with high probability.

On the other hand, if the value of k is greater than 2, the overhead communication exchange can be increased. After having formed the set of the two-hop neighbors, the transmission power will be set according to the distance of nearest two-hop neighbor. This allows the maximization of the coverage while maintaining the sensor connectivity. To answer the question "why the nearest neighbor?" We could say that because a farther two-hop neighbor leads to a higher distance which may produce some decreased performances: lower reception packet rates, poor link quality and more interference. Despite the fact that a lot of routing protocols are based on one-hop neighborhood information, the multi-hop information gives better performance in many aspects including routing, message broadcasting and the channel access scheduling [START_REF] Wen | Performance evaluation of efficient and reliable routing protocols for fixed power sensor networks[END_REF], [START_REF] Songz | An exploration of geographic routing with khop based searching in wireless sensor networks[END_REF]. So, the PA2 algorithm consists of the following two phases:

Phase 1: Discovery of two-hop neighbors Initially, all the sensors have the same transmission range R and the same transmission power Djemili et al. (2007). The sensor broadcasts, periodically, a HELLO message containing the sender identifier (id ) and its location. Each sensor receives such message can deduce that the sender is in its one-hop neighbors as shown in Algorithm 1. By including the one-hop information in these messages, the two-hop knowledge can be acquired after the second round exchange. After this, the sensor calculates the distance between sender s 1 and receiver s 2 using Euclidean formula:

d(s 1 , s 2 ) = (x 1 -x 2 ) 2 + (y 1 -y 2 ) 2 (6)
Algorithm 1: Require: s i , x i , y i 1: if s i receive the hello message of s j then 2:

if s i ∈ N 1 G (s i ) then 3:
ignore the message 4:

end if 5: else 6: calculate d(s i , s j )

7:

Add s j to N 1 G (s i ) 8: end if 9: return 0 where: (x 1 , y 1 ) and (x 2 , y 2 ) are respectively the coordinates of the sender and the receiver. Then, if d(s 1 , s 2 ) < R, so s 2 is a neighbor of s 1 . After having formed the set of two-hop neighbors and having saved the distances for each neighbor, the transmission power allocation will be established in the second phase.

So, it is necessary to discuss the HELLO message frequency f HELLO . Indeed, in mobile environment, defining an adequate value of f HELLO is highly important. A high value of f HELLO updates more often the routing tables. Consequently, AP2 helps to make a good decision. Whereas, a low value of f HELLO allows to save energy by reducing the number of messages. Nevertheless, the data of neighbors table might be expired. Accordingly, finding a good value for HELLO leads to find the lowest frequency which guarantees sufficient frequent update of the neighbors tables. For adapting f HELLO to the mobility constraint, we take into account the relative sensor mobility. In other words, when sensor moves slowly (at low mobility) it uses a low frequency. This means that the sensor s 1 which travels a distance aR in communication area of sensor s 2 must be detected by this latter [START_REF] Fleury | Rseaux de capteurs : théorie et modélisation[END_REF]. Otherwise, if the sensor moves quickly it must take into consideration the speed of its neighbor sensors. So, we define the optimal frequency as follow:

f HELLO = max(v r ) aR (7)
where v r depicts the relative speed of the neighbor sensors. The chosen value of the constant a in the interval ]0,1] depends on the following constraint: d(s 1 , s 2 ) ≤ aR Phase 2: Transmission Power Allocation During this phase each sensor allocates its transmission power according to the distance calculated previously. Thus, each sensor sets its transmission power using Algorithm 2. the used formula is [START_REF] Jiuqiang | Distance Measurement Model Based on RSSI in WSN[END_REF]: set the P ti to the maximum 5: end if 6: return 0 where: P t and P r stand for the transmission and reception power of the wireless signal, d is the distance between the sender and the receiver, n a transmission factor that depends on the propagation environment.

P r = P t * ( 1 d ) n (

Power Allocation based on the distance from the BS (PA2-BS)

The algorithm denoted PA2-BS is a modified version of PA2 in which we introduce the distance from the base station considered as a new parameter in the power allocation. The sensors located close to the base station consume more energy because the traffic may increase within the area close to the base station. This results in a faster exhaustion of their batteries relative to other sensors in the network. Hence, it is clear that the energy consumption is not equally distributed over the sensors in the network. This leads to an early failure of these sensors, which may result in a disconnected network.

For balancing the energy consumption over the network, the idea is that each sensor located close to the base station decreases its transmission power. In other words, it is not necessary for those sensors to increase the transmission power to reach the two-hop neighbors and so consume more energy. This can be achieved when it is possible by forwarding the collected data using one-hop communication.

Algorithm 3:

Require: s i , N 2 G (s i ) 1: calculate d(s i , BS) 2: if (d(s i , BS)) < d(s i , s j ) then 3:
set P ti according to the distance f rom BS 4: else 5:

set P ti according to the nearest neighbors 6: end if 7: return 0 Indeed, each sensor allocates its transmission power such as detailed in Algorithm 3. Every sensor calculates distance between its neighbors on two-hop and its distance from the BS. If the sensor is close to the BS, its transmission power can be reduced. Otherwise, the transmission power will be set according to the distance of the nearest two-hop neighbor. Consequently, the sensors that are located close to the BS consume less energy, particularly, for exchanging of messages.

Communication plan

The communication with the base station can be performed either using one-hop or multi-hop communication. In one-hop communication, the sensor can reach directly the base station (direct transmission mode). This is the case for the sensors located close to the base station. In multi-hop communication, the sensor routes the data using a specific routing protocols such as Minimum Transmission Energy (MTE) [START_REF] Weng | A minimum transmission energy consumption routing protocol for user-centric wireless networks[END_REF]. This protocol provides multi-hop transmission yielding to an energy-efficient use when the sensors are far away from the base station.

Network topology

The network topology changes over time due to the mobility between the initial and final states by the algorithms PA2 and PA2-BS as shown in figures 2 and 3. The sensor transmission ranges are presented by dashed circles. For the seek of clarity, we present only 50 sensors in the network and some transmission ranges. Initially, all the sensors have the same transmission range. Fig. 2 presents PA2 algorithm after the first stage run. In order to analyze the sensor behavior, the sensing field is divided into three regions: high, medium and low population which are colored respectively in the Fig. 2 using gray, white and orange colors. We can see that all the sensors in high population region decrease their transmission range (ex. sensors: 33, 37, 10 and 49). This can be explained by the fact that these sensors have enough neighbors to improve the area coverage. When the transmission range is reduced, the interference between close sensors is significantly decreased. The sensors in medium and low population region increase (in most cases) their transmission range. Some sensors decrease their transmission range in order to satisfy the two-hop neighbors constraint (ex. sensors: 31 and 29). In some situations, the sensor keeps its transmission range at maximum to reach the other sensor neighbors (ex., sensor 13).

At time t k (as shown in Fig. 3), the topology of the network changes whereas the sensors behavior remains the same. We note that, if two sensors are very close, one of them reduces its transmission range whereas the second sensor increases its transmission range to reach the others in order to improve the own coverage region (ex., the sensors: 19 and 40). Note that the coverage of the mobile sensor network does not lie only on the initial configuration, but also on the mobility behavior of sensors. For these reasons, the PA2 algorithm takes into account, for each sensor, the number of its neighbors that meet the need of its own coverage area. The application of PA2-BS algorithm gives the network topologies presented in figures 4 and 5. The sensing field is divided into three regions: close, medium and far from the base station which are colored respectively using grey, white and orange colors. We see that in the two configurations, the sensors that are close to the BS set their transmission ranges to the distance from the BS (ex. sensors: 12 and 41 in Fig. 4 and sensors: 19, 15 and 36 in Fig. 5). When the sensors are marginally close to or far from the base station, they reduce their transmission range to reach the needed neighbors (ex., sensor: 17 and 5 in Fig. 4 and sensors: 6, 14 and 36 in Fig. 5).

Simulations

In order to evaluate the performances of the proposed algorithms, we use the WSnet simulator that is dedicated, especially, to sensor networks . We compare the obtained results of the proposed In our simulations, we intend to focus on four performance metrics:

• energy consumption;

• network connectivity;

• network lifetime; and

• delivery rate success.

A. Energy consumption

It is the energy consumed during the transmission, the reception and the idle time. Hence, we use the general formula given in ( 9).

E used = E T x + E Rx + E idle + E M x (

C. Network lifetime

The definition of network lifetime is the time span from the deployment to the instant when the network is considered non-operational. A network is considered non-operational according to the chosen application.

It may be, for example, the instant when the first sensor dies, a percentage of dead sensors, the network connectivity is lost, or the loss of coverage occurs. In our study, we consider the case of the percentage of dead sensors [START_REF] Chen | On the Lifetime of Wireless Sensor Networks[END_REF]. Thus, if the number of dead sensors is greater than 80%, we assume that the network is nonoperational.

D. Packet delivery success rate

In all WSN applications, the Packet Delivery success Rate (PDR) is very important in order to accomplish the network task. Since, in the simulations we evaluate the packet delivery success rate defined as: P DR = N umber of received packets N umber of sent packets (12)

Parameters and environment

In our simulations, different network sizes are considered: 200, 400, 600 and 800 nodes in order to assess its impact on the network performances. The sensors are distributed randomly in a square area of 300m × 300m.

A single and stationary base station is used. It is located in the center of the area. The sensors move randomly with speed varying between 1m/s and 30m/s. The complete configuration is summarized in Table 1.

Results

Energy consumption

Fig. 6 shows the ratio of the consumed energy over the simulation time. We can see that PA2-BS outperforms the PA2 and the basic solution by almost 15% for 90 minutes and more than 30% for 120 minutes. This can be explained, on one hand by the decrease of transmission power according to the nearest two-hop neighbors which consume less energy and on the other hand by the decrease of the transmission power of the sensors that are close to the BS. As expected, the improvement of performance due to the use of PA2-BS solution compared to the PA2 and the basic solution is more emphasized for a long-run simulation. The reason is that all the sensors use, initially, the same transmission power. Consequently, the difference of consumed energy is not important in the beginning of the experimentation. To evaluate the quality of the proposed algorithms in a mobile environment, we compare the consumed energy to the solutions in Fig. 7. For 400 sensors, we can observe that the consumed energy increases according to the sensors speed. However, with the PA2-BS, sensors consume considerable less energy compared with the two solutions. This is due to the reduction of transmission power.

Fig. 8 presents the consumed energy for different network densities. We can see that the difference of the consumed energy for small network (200 sensors) is not significant. This can be explained by the dispersion of sensors in the area which increases the distances between neighbors and the distance between the sensors and the BS. Thus, the sensors cannot decrease their transmission power. Nevertheless, for large-scale networks (more than 200 sensors), it is clear that PA2-BS outperforms the two solutions by 17% for 600 sensors and by almost 40% for 800 sensors. This means that PA2-BS is able to save more energy for large-scale WSN.

Network connectivity

In order to evaluate the performance of the proposed algorithms in terms of connectivity, we calculate the number of connected components with different densities. Fig. 9 shows that PA2-BS can manage, in a better way, the consumed energy without adversely affecting the connectivity of the network. However, PA2 has almost the same connectivity than the basic solution. This can be explained by the variations of transmission power which respect the number of neighbors and the We assume that the network lifetime is defined as the moment in time when the network is not connected anymore because the failure of one or more sensors. We observe in Fig. 10 the impact of the variation of transmission power on the performance of PA2-BS, according to the distance between its neighbors on twohop. and the distance from BS. For all configurations, the network lifetime using PA2-BS is better than the two other solutions. This is justified by the results depicted on Fig. 8 in which we can note that PA2-BS saves more energy and allows the network to operate longer. Hence, PA2-BS improves network lifetime.

Network lifetime

Packet delivery success rate

We can note in Fig. 11 that, for all configurations, the PA2-BS ensures a good delivery ratio compared to the two other solutions. We conclude that MP2-BS is able to save energy without adversely affecting the quality of communications. It exists a proportional relationship between the transmission power and the interferences. So, when the transmission power decreases, the interferences decrease. Consequently, the number of packets properly delivered increases.

Conclusions

We have presented two power allocation algorithms for mobile sensor networks. These algorithms are designed to develop an effective mechanism to improve the energy conservation, while simultaneously constraining the connectivity. The first proposed algorithm PA2 is based on the self-regulation of transmission power, for each sensor, according to the distance with its two-hop neighbors. The enhanced proposed PA2-BS algorithm is based on the same principal of PA2 and in addition it considers the distance between the sensors and the BS. Using this combination, the energy consumption is decreased for every sensor and the connectivity is maintained with the required number of neighbors.

We have evaluated these algorithms using a set of extensive simulations. Starting by a configuration in which all the sensors has the same transmission range, the PA2 and PA2-BS algorithms provide promising results both in terms of: increasing the packet delivery rate and extending the network lifetime without adversely affecting the network connectivity.

In the future, we plan to implement the proposed algorithms in a test-bed environment in order to perform a more accurate evaluation.

Figure 1

 1 Figure 1 Network model

Figure 2

 2 Figure 2 MP2-Statique

Figure 4

 4 Figure 4 MP2-BS-etatInitial

  i indicate the sensor i and n the number of neighbor sensors. B. Network connectivity The wireless sensor network connectivity is defined as the connectivity of the largest connected component. Hence, it can reflect the network connectivity status and throughput. It can provide reliable evidence for the timely adjustment of the network topology Gu et al. (2010). Consequently, the Network Connectivity (NC) is calculated as follow: N C = Biggest connected component size N etwork size (11)

Figure 6

 6 Figure 6 Consumed energy vs. Simulation time (600 nodes)

Figure 7 Figure 8

 78 Figure 7 Consumed energy vs. Speed (400 nodes)

Figure 9

 9 Figure 9 Connectivity factor vs. Number of sensors

Figure 10

 10 Figure 10 Network lifetime vs. Number of sensors

Figure 11

 11 Figure 11 Delivery ratio vs. Number of sensors

Table 1

 1 Simulation parameters

	Parameters	Values
	Area size	300 m × 300 m
	Simulation duration	7200 s
	Number of sensors	200, 400, 600 and 800
	Max transmission power 0 dBm
	Min transmission power -25 dBm
	Max transmission range 200 m
	Max speed of sensors	30 m/s

Biographical notes

Fatiha Djemili Tolba is an Assistant Professor in the Department of Computer Science at the Badji Mokhtar University, Annaba, Algeria. She received the PhD degree in computer science from the Franche Comte University, Besancon, France (2007), and the MS degree in Computer Science and Automation from Franche Comte University, Besancon, France (2003). She serves as reviewer for numerous conferences and journals. Her research interests focus on mobile wireless networks, QoS support and energy control in ad hoc and sensor networks.

Damien


Pascal Koiran
email: pascal.koiran@ens-lyon.fr

Sylvain

LIP ⋆ Sylvain Perifel
email: sylvain.perifel]@ens-lyon.fr

VPSPACE and a Transfer Theorem over the Reals

Keywords: computational complexity, algebraic complexity, Blum-Shub-Smale model, Valiant's model

come

VPSPACE and a Transfer Theorem over the Reals

Introduction

Two main categories of problems are studied in algebraic complexity theory: evaluation problems and decision problems. A typical example of an evaluation problem is the evaluation of the permanent of a matrix, and it is well known that the permanent family is complete for the class VNP of "easily definable" polynomial families [START_REF] Valiant | Completeness classes in algebra[END_REF]. Deciding whether a multivariate polynomial has a real root is a typical example of a decision problem. This problem is NP-complete in the Blum-Shub-Smale model of computation over the real numbers [START_REF] Blum | Complexity and Real Computation[END_REF][START_REF] Blum | On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines[END_REF].

The main purpose of this paper is to provide a transfer theorem connecting the complexity of evaluation and decision problems. This paper is therefore in the same spirit as [START_REF] Koiran | Valiant's model: from exponential sums to exponential products[END_REF]. In that paper, we showed that if certain polynomials can be evaluated efficiently then certain decision problems become easy. The polynomials considered in [START_REF] Koiran | Valiant's model: from exponential sums to exponential products[END_REF] are those that can be written as exponentialsize products of polynomials that are easy to compute (see [START_REF] Koiran | Valiant's model: from exponential sums to exponential products[END_REF] for a precise definition) over some field K. The decision problems under consideration are those that are in NP in the structure (K, +, -, =), in which multiplication is not allowed.

In the present paper we work with a larger class of polynomial families, which we call VPSPACE. Roughly speaking, a family of polynomials (of possibly exponential degree) is in VPSPACE if its coefficients can be evaluated in polynomial space. For instance, we show that resultants of systems of multivariate polynomial equations form a VPSPACE family. Our main result is that if (uniform, constant-free) VPSPACE families can be evaluated efficiently then the class PAR R of decision problems that can be solved in parallel polynomial time over the real numbers collapses to P R . This result relies crucially on a combinatorial lemma due to Grigoriev [START_REF] Grigoriev | Topological complexity of the range searching[END_REF] and especially on its effective version, recently established in [START_REF] Charbit | Finding a vector orthogonal to roughly half a collection of vectors[END_REF]. The class PAR R plays roughly the same role in the theory of computation over the reals as PSPACE in discrete complexity theory. In particular, it contains NP R [START_REF] Blum | Complexity and Real Computation[END_REF] (but the proof of this inclusion is much more involved than in the discrete case). It follows from our main result that in order to separate P R from NP R , or even from PAR R , one must first be able to show that there are VPSPACE families which are hard to evaluate. This seems to be a very challenging lower bound problem, but it is still presumably easier than showing that the permanent is hard to evaluate. Organization of the paper. Section 2 recalls some notions and notations from algebraic complexity (Valiant's model, the Blum-Shub-Smale model). The class VPSPACE is defined in Section 3 (both in a uniform and a nonuniform setting) and as an example we show in Section 3.3 that resultants of multivariate polynomial systems form a (uniform) VPSPACE family. It is not necessary to read Section 3.3 in order to understand the remainder of the paper. Some closure properties of VPSPACE are given in Section 3.4.

In Section 4, the hypothesis that VPSPACE families are easy to evaluate is discussed. It is shown that (assuming the generalized Riemann hypothesis) this hypothesis is equivalent to: VP = VNP and P/poly = PSPACE/poly. The conjunction of these two equalities is an extremely strong assumption: by results from [START_REF] Bürgisser | Completeness and Reduction in Algebraic Complexity Theory[END_REF] (see [START_REF] Koiran | Valiant's model and the cost of computing integers[END_REF]), it implies, assuming again GRH, that NC/poly = PSPACE/poly. This conjunction of equalities is still apparently consistent with our current understanding of complexity theory. We also discuss the uniform, constant-free version of the hypothesis that VPSPACE families are easy to evaluate. It turns out that this stronger hypothesis implies that PSPACE collapses to the polynomial-time uniform version of NC. Such a dramatic collapse of complexity classes looks extremely unlikely, but as far as we know it cannot be refuted with the current methods of complexity theory.

Finally, the last two sections of the paper are devoted to the transfer theorem. Section 5 deals with sign conditions, an important tool from computational real algebraic geometry. The transfer theorem is stated at the beginning of Section 6, and proved thereafter.

Preliminaries

The notions of boolean complexity theory that we use are quite standard. In the present section, we focus on algebraic complexity.

The Blum-Shub-Smale Model

In contrast with boolean complexity, algebraic complexity deals with other structures than {0, 1}. In this paper we will focus on the ordered field (R, +, -, ×, ≤) of the real numbers. Although the original definitions of Blum, Shub and Smale [START_REF] Blum | On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines[END_REF][START_REF] Blum | Complexity and Real Computation[END_REF] are in terms of uniform machines, we will follow [START_REF] Poizat | Les petits cailloux[END_REF] by using families of algebraic circuits to recognize languages over R, that is, subsets of

R ∞ = n≥0 R n .
An algebraic circuit is a directed acyclic graph whose vertices, called gates, have indegree 0, 1 or 2. An input gate is a vertex of indegree 0. An output gate is a gate of outdegree 0. We assume that there is only one such gate in the circuit. Gates of indegree 2 are labelled by a symbol from the set {+, -, ×}. Gates of indegree 1, called test gates, are labelled "≤ 0?". The size of a circuit C, in symbols |C|, is the number of vertices of the graph.

A circuit with n input gates computes a function from R n to R. On input ū ∈ R n the value returned by the circuit is by definition equal to the value of its output gate. The value of a gate is defined in the usual way. Namely, the value of input gate number i is equal to the i-th input u i . The value of other gates is then defined recursively: it is the sum of the values of its entries for a +-gate, their difference for a --gate, their product for a ×-gate. The value taken by a test gate is 0 if the value of its entry is > 0 and 1 otherwise. We assume without loss of generality that the output is a test gate. The value returned by the circuit is therefore 0 or 1.

The class P R is the set of languages L ⊆ R ∞ such that there exists a tuple ā ∈ R p (independent of n) and a P-uniform family of polynomial-size circuits (C n ) satisfying the following condition: C n has exactly n + p inputs, and for any x ∈ R n , x ∈ L ⇔ C n (x, ā) = 1. The P-uniformity condition means that C n can be built in time polynomial in n by an ordinary (discrete) Turing machine. Note that ā plays the role of the machine constants of [START_REF] Blum | Complexity and Real Computation[END_REF][START_REF] Blum | On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines[END_REF].

As in [START_REF] Chapuis | Saturation and stability in the theory of computation over the reals[END_REF], we define the class PAR R as the set of languages over R recognized by a PSPACE-uniform family of algebraic circuits of polynomial depth (and possibly exponential size), with constants ā as for P R . Note at last that we could also define similar classes without constants ā. We will use the superscript 0 to denote these constant-free classes, for instance P 0 R and PAR 0 R .

Valiant's Model

In Valiant's model, one computes polynomials instead of recognizing languages. We thus use arithmetic circuits instead of algebraic circuits. A book-length treatment of this topic can be found in [START_REF] Bürgisser | Completeness and Reduction in Algebraic Complexity Theory[END_REF]. An arithmetic circuit is the same as an algebraic circuit but test gates are not allowed. That is to say we have indeterminates x 1 , . . . , x u(n) as input together with arbitrary constants of R; there are +, -and ×-gates, and we therefore compute multivariate polynomials.

The polynomial computed by an arithmetic circuit is defined in the usual way by the polynomial computed by its output gate. Thus a family (C n ) of arithmetic circuits computes a family (f n ) of polynomials,

f n ∈ R[x 1 , . . . , x u(n) ].
The class VP nb defined in [START_REF] Malod | Polynômes et coefficients[END_REF] is the set of families (f n ) of polynomials computed by a family (C n ) of polynomial-size arithmetic circuits, i.e., C n computes f n and there exists a polynomial p(n) such that |C n | ≤ p(n) for all n. We will assume without loss of generality that the number u(n) of variables is bounded by a polynomial function of n. The subscript "nb" indicates that there is no bound on the degree of the polynomial, in contrast with the original class VP of Valiant where a polynomial bound on the degree of the polynomial computed by the circuit is required. Note that these definitions are nonuniform. The class Uniform VP nb is obtained by adding a condition of polynomial-time uniformity on the circuit family, as in Section 2.1.

The class VNP is the set of families of polynomials defined by an exponential sum of VP families. More precisely, (f n (x)) ∈ VNP if there exists (g n (x, ȳ)) ∈ VP and a polynomial p such that |ȳ| = p(n) and f n (x) = ǭ∈{0,1} p(n) g n (x, ǭ).

We can also forbid constants from our arithmetic circuits in unboundeddegree classes, and define constant-free classes. The only constant allowed is 1 (in order to allow the computation of constant polynomials). As for classes of decision problems, we will use the superscript 0 to indicate the absence of constant: for instance, we will write VP 0 nb (for bounded-degree classes, we are to be more careful; see [START_REF] Malod | Polynômes et coefficients[END_REF]).

Note at last that arithmetic circuits are at least as powerful as boolean circuits in the sense that one can simulate the latter by the former. Indeed, we can for instance replace ¬u by 1 -u, u ∧ v by uv, and u ∨ v by u + v -uv. This proves the following classical lemma. Lemma 1. Any boolean circuit C can be simulated by an arithmetic one of size at most 3|C|, in the sense that on boolean inputs, both circuits output the same value.

3 The Class VPSPACE

Definition

We fix an arbitrary field K. The definition of VPSPACE will be stated in terms of coefficient function.

A monomial x α1 1 • • • x α u(n)
u(n) is encoded in binary by α = (α 1 , . . . , α u(n) ) and will be written xα . Definition 1. Let (f n ) be a family of multivariate polynomials with integer coefficients. The coefficient function of (f n ) is the function a whose value on input (n, α, i) is the i-th bit a(n, α, i) of the coefficient of the monomial xα in f n . Furthermore, a(n, α, 0) is the sign of the coefficient of the monomial xα . Thus f n can be written as

f n (x) = α (-1) a(n,α,0) i≥1 a(n, α, i)2 i-1 xα .
The coefficient function is a function a : {0, 1} * → {0, 1} and can therefore be viewed as a language. This allows us to speak of the complexity of the coefficient function.

Definition 2. The class Uniform VPSPACE 0 is the set of all families (f n ) of multivariate polynomials f n ∈ K[x 1 , . . . , x u(n) ] satisfying the following requirements:

1. the number u(n) of variables is polynomially bounded; 2. the polynomials f n have integer coefficients; 3. the size of the coefficients of f n is bounded by 2 p(n) for some polynomial p; 4. the degree of f n is bounded by 2 p(n) for some polynomial p; 5. the coefficient function of (f n ) is in PSPACE.

We have chosen to define first Uniform VPSPACE 0 , a uniform class without constants, because this is the main object of study in this paper. In keeping with the tradition set by Valiant, however, the class VPSPACE, defined in Section 3.5, is nonuniform and allows for arbitrary constants.

An Alternative Characterization

Let Uniform VPAR 0 be the class of families of polynomials computed by a PSPACE-uniform family of constant-free arithmetic circuits of polynomial depth (and possibly exponential size). This in fact characterizes Uniform VPSPACE 0 . Proposition 1. The two classes Uniform VPSPACE 0 and Uniform VPAR 0 are equal.

Proof. Let (f n ) be a Uniform VPSPACE 0 family. In order to compute f n by an arithmetic circuit of polynomial depth, we compute all its monomials in parallel and sum them in a divide-and-conquer-fashion. The resulting family of arithmetic circuits is uniform due to the uniformity condition on (f n ).

For the converse, take an arithmetic circuit of polynomial depth. We show that we can build a boolean circuit of polynomial depth which takes as input the encoding α of a monomial and computes the coefficient of xα . We proceed by induction, computing the coefficient of xα for each gate of the original arithmetic circuit. For the input gates, this is easy. For a +-gate, it is enough to add both coefficients. For a gate a × b, we compute in parallel the sum of the cd over all the monomials xβ and xγ such that β + γ = α, where c is the coefficient of xγ in the gate a, and d the coefficient of xβ in the gate b. The whole boolean circuit remains uniform and of polynomial depth. Therefore, the coefficient function is in PSPACE by the "parallel computation thesis".

⊓ ⊔

We see here the similarity with PAR R , which by definition are those languages recognized by uniform algebraic circuits of polynomial depth. But of course there is no test gate in the arithmetic circuits of Uniform VPSPACE 0 .

An Example

Algebraic geometry is a natural source of examples for the study of polynomials from a computational point of view. For instance, the Hilbert polynomial is studied in [START_REF] Bürgisser | The complexity of computing the Hilbert polynomial of smooth equidimensional complex projective varieties[END_REF] from the point of view of discrete complexity theory. Here we study a different example: the computation of the resultant of a system of multivariate polynomials. A system of n + 1 homogenous equations in n + 1 complex variables has a nontrivial solution if and only if its resultant is zero. We sketch the construction of the resultant below. More details can be found for instance in [START_REF] Macaulay | Algebraic theory of modular systems[END_REF] or [START_REF] Canny | Generalized characteristic polynomials[END_REF].

Let f 1 , . . . , f n+1 ∈ C[X 0 , . . . , X n ] be a system of n + 1 homogeneous polynomials. The resultant consists in the quotient of the determinants of two matrices M and M ′ :

R = det M det M ′ (1)
where the coefficients of M are among those of the f i 's, and M ′ is a submatrix of M . The matrix M is called Macaulay's matrix (a generalization of Sylvester's for two univariate polynomials) and is described as follows. Let d i be the degree of Finally, the submatrix M ′ consists in the rows and columns of M that are "not reduced", see [START_REF] Canny | Generalized characteristic polynomials[END_REF]. What we will compute is not the resultant R itself but rather a multiple of it, namely det M . Whenever det M ′ = 0, this does not change anything if we are only concerned by the vanishing of R.

f i and d = 1 + n+1 i=1 (d i - 1
From now on, we will assume for simplicity that all the d i are equal. We will let n go to infinity, but the common value δ of the d i will remain constant. A system (f 1 , . . . , f n+1 ) of n + 1 homogeneous polynomials of degree δ in n + 1 variables is encoded by the list of the coefficients of the polynomials, i.e., by k(n + 1) variables (a 1,1 , . . . , a 1,k , a 2,1 , . . . , a n+1,k ) where k = n+δ δ is the number of monomials of degree δ in n + 1 variables. Note that k is polynomial in n for any fixed δ.

The matrix Mac δ n (f 1 , . . . , f n+1 ) is then defined as the Macaulay matrix M of (f 1 , . . . , f n+1 ). This matrix is of size n+d d , where d = 1 + (n + 1)(δ -1). This is exponential in n as soon as δ ≥ 2. Computing the determinant of M can be done by a circuit of depth polylogarithmic in the size of M , thus polynomial in n. The above considerations then prove the following proposition.

Proposition 2. For any fixed δ, the family (det(Mac δ n )) (the determinant of the Macaulay matrix of a system of n + 1 homogeneous polynomials of degree δ

in n + 1 variables) is in Uniform VPSPACE 0 .
Likewise, the determinants of the matrices M ′ in (1) form a Uniform VPSPACE 0 family.

Closure Properties

The following lemma is clear from Proposition 1.

Lemma 2. Uniform VPSPACE 0 is closed under big sums and big products.

We can even make sums and products over a set more complicated than {0, 1}, as proven in the following lemma. Lemma 3. Let A be a language in PSPACE, (f n (x, ȳ)) a family in Uniform VPSPACE 0 and p(n) a polynomial, where |ȳ| = p(n). Then the families (g n (x)) and (h n (x)) defined as follows are in Uniform VPSPACE 0 .

g n (x) = ǭ∈A =p(n) f n (x, ǭ) and h n (x) = ǭ∈A =p(n) f n (x, ǭ).
Proof. It is enough to use Lemma 2 since we have

ǭ∈A =p(n) f n (x, ǭ) = ǭ∈{0,1} p(n) χ A (ǭ)f n (x, ǭ), and ǭ∈A =p(n) f n (x, ǭ) = ǭ∈{0,1} p(n) [χ A (ǭ)f n (x, ǭ) + (1 -χ A (ǭ))],
where χ A , the characteristic function of A, is in Uniform VPSPACE 0 by Lemma 1 and Proposition 1 since A is decided by a Uniform family of boolean circuits of polynomial depth.

⊓ ⊔

The Nonuniform Class VPSPACE

Let us now define the nonuniform classes VPSPACE 0 and VPSPACE. Note that the only difference between VPSPACE 0 and Uniform VPSPACE 0 is the nonuniformity of the coefficient function.

Definition 3. The class VPSPACE 0 is the set of all families (f n ) of multivariate polynomials f n ∈ K[x 1 , . . . , x u(n)
] satisfying the following requirements:

1. the number u(n) of variables is polynomially bounded; 2. the polynomials f n have integer coefficients; 3. the size of the coefficients of f n is bounded by 2 p(n) for some polynomial p; 4. the degree of f n is bounded by 2 p(n) for some polynomial p; 5. the coefficient function of

(f n ) is in PSPACE/poly. Now, the class VPSPACE is the set of all families (f n (x)) of multivariate polyno- mials f n ∈ K[x 1 , . . . , x u(n) ]
such that there exist a family (g n (x, ȳ)) ∈ VPSPACE 0 together with a family of tuples of constants (ā (n) ) satisfying for all n:

f n (x) = g n (x, ā(n) ).
We introduce temporarily a degree-bounded version of VPSPACE: this will prove useful for comparing VPSPACE to VP and VNP since the degree of the polynomials in these last two classes are polynomially bounded. A family (f n ) of polynomials is in VPSPACE 0 b if (f n ) ∈ VPSPACE 0 and the size of the coefficients as well as the degree of f n are polynomially bounded. The class VPSPACE b is then defined from VPSPACE 0 b in the same way as VPSPACE is defined from VPSPACE 0 in Definition 3. This new class is interesting for our purpose due to the following two lemmas. Proof. Assume first that VPSPACE = VP nb , and take a family

(f n ) ∈ VPSPACE b . Since VPSPACE b ⊂ VPSPACE, (f n ) is in fact in VP nb by hypothesis. Now, since the degree of (f n ) is polynomially bounded, (f n ) ∈ VP.
For the converse, take a family (f n ) ∈ VPSPACE: remember that it can be written as f n (x) = g n (x, ā(n) ) for some constants ā(n) and (g n (x, ȳ)) ∈ VPSPACE 0 . For convenience, let us rename the u(n) variables of g n by v 1 , . . . , v u(n) , thus we have:

g n (v) = α (-1) a(n,α,0) 2 p(n) i=1 a(n, α, i)2 i-1 vα ,
where a is in PSPACE/poly. In this expression, p(n) is a polynomial and 2 p(n) bounds the size of the coefficients as well as the degree of g n . In order to use the hypothesis, we have to somehow define a family (h n ) ∈ VPSPACE 0 b that will "simulate" (g n ). Let us define

h n (z 1,1 , . . . , z 1,p(n) , z 2,1 , . . . , z u(n),p(n) , w 1 , . . . , w p(n) ) ,
where intuitively the variable z i,j is to replace v 2 j i in g n , and w i will take the value 2 2 i . More formally, h n is defined as follows:

replace v k i in g n by j∈J k z i,j , where the set J k consists of the bits set to 1 in the binary representation of k; -replace the coefficient 2 i-1 in the term

2 p(n)
i=1 a(n, α, i)2 i-1 of g n by j∈Ji-1 w j , where the set J i-1 consists of the bits set to 1 in the binary representation of i -1.

The degree of h n is then polynomially bounded and all the coefficients are among -1, 0 and 1. Note furthermore that the coefficient function is still in PSPACE.

Therefore (h n ) ∈ VPSPACE 0 b , thus (h n ) ∈ VP by hypothesis. It remains to replace z i,j by v 2 j
i and w i by 2 2 i to show that (g n (v) = g n (x, ȳ)) ∈ VP nb , and then to replace ȳ by the original constants in order to show that (f n ) ∈ VP nb .

⊓ ⊔ Lemma 5. VPSPACE b contains VNP.

Proof. Let (HC n ) be the family defined by

HC n (x 1,1 , . . . , x 1,n , x 2,1 , . . . , x n,n ) = σ n i=1 x i,σ(i)
where the sum is taken over all n-cycles σ over {1, . . . , n}. This polynomial counts the number of Hamilton cycles in a graph given by its adjacency matrix. (HC n ) is VNP-complete, see [START_REF] Valiant | Completeness classes in algebra[END_REF] or [START_REF] Malod | Polynômes et coefficients[END_REF]. Since VPSPACE b is closed under p-projections and contains HC n , the lemma follows. Moreover, the implication from right to left holds even without GRH.

Proof. Assume first that P/poly = PSPACE/poly and VP = VNP. By Lemma 4, the equality VPSPACE = VP nb is equivalent to the degree-bounded analogue VPSPACE b = VP. Let (f n ) ∈ VPSPACE b : its coefficient function is in PSPACE/poly, thus in P/poly by our assumption. Since the set of coefficient functions of VNP families contains ⊕P/poly (see [START_REF] Bürgisser | Completeness and Reduction in Algebraic Complexity Theory[END_REF]), hence P/poly, (f n ) is in fact in VNP. By our assumption again, it is in VP.

For the converse, assume now that VPSPACE = VP nb . Again, this is equivalent to VPSPACE b = VP. Hence VNP = VP since VP ⊆ VNP ⊆ VPSPACE b by Lemma 5. It remains to show that a language A in PSPACE/poly belongs in fact to P/poly. A is recognized by a P/poly-uniform family of polynomialdepth boolean circuits, and by Lemma 1 and Proposition 1 there exists a family (f n ) ∈ VPSPACE such that on any boolean input x ∈ {0, 1} n , f n (x) ∈ {0, 1} and f n (x) = 1 if and only if x ∈ A.

By our assumption, (f n ) ∈ VP nb , thus there exists a family of polynomial-size arithmetic circuits (C n ), with arbitrary constants, that computes (f n ). In order to evaluate these circuits on boolean inputs with boolean circuits, the problem now is to eliminate the constants. We proceed as in [START_REF] Bürgisser | Completeness and Reduction in Algebraic Complexity Theory[END_REF]. Let ȳ be the constants for the circuit C n , and call g n ( X, Ȳ ) the polynomial computed by C n where the constants are replaced by the new variables Ȳ . Thus g n ( X, ȳ) = f n ( X), therefore the system S of equations in Ȳ defined by

S = g n (x, Ȳ ) = f n (x) x∈{0,1} n
has a solution ȳ over C. All the equations in this system have integer coefficients, degree bounded by 2 q(n) and weight by 2 2 q(n) for some polynomial q, where the weight of a polynomial is the sum of the absolute value of its coefficients. By Theorem 4.4 of [3, p. 64], assuming GRH there exists a prime number p ≤ 2 n 2 q(n) such that S has a solution over F p . There indeed exists such a p ≤ a as soon as

π(a) d O(n) > √ a log(wa),
where d and w are bounds on the degree and weight of the equations respectively, and π(a) is the number of primes ≤ a. Thus there exists a polynomial-size arithmetic circuit over F p computing the polynomial g n ( X, ȳ′ ) and this polynomial takes the same values as f n ( X) on boolean inputs. Note that the size of p is polynomial, and a solution ȳ′ of this system S over F p also has polynomial size. Therefore a polynomial-size boolean circuit working modulo p can now easily compute the value of g n ( X, ȳ′ ) over F p . This boolean circuit has the same value on boolean inputs as f n . Hence A ∈ P/poly, and the announced result is proved.

⊓ ⊔

We now turn in the next proposition to the most uniform version of the hypothesis, which is stronger than that of Proposition 3. For the proof, we need two definitions from [START_REF] Miller | Efficient parallel evaluation of straight-line code and arithmetic circuits[END_REF] and [START_REF] Malod | Polynômes et coefficients[END_REF]. Definition 4. The formal degree of an arithmetic circuit C is the formal degree of its output gate, where the formal degree of a gate is defined recursively:

the formal degree of an input gate is 1; -the formal degree of a +-gate or a --gate is the maximum of the formal degrees of its inputs; -the formal degree of a ×-gate is the sum of the formal degrees of its inputs. Definition 5. The class VP 0 is the set of families of polynomials computed by a family of constant-free (i.e. using only 1 as a constant) polynomial-size arithmetic circuits of polynomial formal degree.

The following proposition is similar to Proposition 3, but in a uniform setting and without assuming the generalized Riemann hypothesis. It is not clear whether the assumption Uniform VP 0 nb = Uniform VNP 0 nb in this proposition can be replaced by the assumption Uniform VP 0 = Uniform VNP 0 . Proposition 4. Uniform VP 0 nb = Uniform VPSPACE 0 if and only if

P = PSPACE and Uniform VP 0 nb = Uniform VNP 0 nb .
Proof. Assume first that P = PSPACE and Uniform VP 0 nb = Uniform VNP 0 nb . Take a family (f n ) ∈ Uniform VPSPACE 0 . Its coefficient function is in PSPACE, hence in P by assumption. The sum of the monomials with their coefficients is therefore in Uniform VNP 0 nb . Thus (f n ) ∈ Uniform VP 0 nb by assumption. For the converse, let us first show that P = PSPACE. Let A be a PSPACE language: it is decided by a uniform family of polynomial-depth boolean circuits. By Lemma 1 and Proposition 1, we obtain a family of polynomials (f n ) ∈ Uniform VPSPACE 0 that agrees with the boolean circuits on boolean inputs, i.e.,

∀x ∈ {0, 1} n , f n (x) ∈ {0, 1} and [f n (x) = 1 ⇐⇒ x ∈ A].
By our assumption, (f n ) ∈ Uniform VP 0 nb so that there exists a uniform family of polynomial-size arithmetic circuits that computes (f n ). Of course, on boolean inputs such circuits can be evaluated in polynomial time (working modulo 2 to avoid overflows). This implies that PSPACE = P. Now, the proof of Uniform VNP

0 nb = Uniform VP 0 nb is clear since Uniform VP 0 nb ⊆ Uniform VNP 0 nb ⊆ Uniform VPSPACE 0 . ⊓ ⊔
We can now prove a consequence of the hypothesis Uniform VPSPACE 0 = Uniform VP 0 nb . Proposition 5.

Uniform VPSPACE 0 = Uniform VP 0 nb =⇒ PSPACE = P-uniform NC.

Proof. By Proposition 4, the hypothesis already implies P = PSPACE.

Let us now prove that ⊕P ⊆ P-uniform NC under the hypothesis that Uniform VPSPACE 0 = Uniform VP 0 nb . It is enough to show that the ⊕P-complete language ⊕HamiltonPath (the problem of deciding whether there is an odd number of Hamilton paths in a graph, see [18, p. 448]) is in P-uniform NC. For a graph given by its boolean adjacency matrix (a i,j ) (where a i,j = 1 iff there is an edge between i and j), the number of Hamilton paths is

1≤j<k≤n σ∈S j,k n-1 i=1 a i,σ(i) ,
where S j,k is the set of all the n-cycles σ ∈ S n beginning in j and ending in k (j is different from k in order to count paths in the graph and not cycles, and j is smaller than k in order not to count twice each path, which would trivialize the problem ⊕HamiltonPath). The polynomial

p n (x 1,1 , . . . , x 1,n , x 2,1 , . . . , x n,n ) = j<k σ∈S j,k n-1 i=1 x i,σ(i)
therefore outputs the number of Hamilton paths on the boolean encoding x 1,1 . . . x 1,n x 2,1 . . . x n,n of a graph G. This family of polynomials (p n ) is easily seen to be in Uniform VPSPACE 0 , has polynomially bounded degree, and its evaluation modulo 2 provides the answer to the question "G ∈ ⊕HamiltonPath?".

By our assumption, (p n ) ∈ Uniform VP 0 nb so that there exists a P-uniform family of polynomial-size arithmetic circuits (C n ) that computes (p n ). We are going to build a family of circuits (D n ) that computes a family of polynomials (q n ) ∈ VP 0 such that on boolean inputs, p n and q n have the same parity. Note that despite the polynomial bound on its degree, (p n ) needs not be already in VP 0 because the formal degree of C n needs not be polynomial (indeed, constants of exponential size might be computed by C n ). This is why we cannot directly evaluate C n in parallel with the algorithm of [START_REF] Miller | Efficient parallel evaluation of straight-line code and arithmetic circuits[END_REF].

The idea here is that we can compute only the remainder modulo 2 of the constants because we are only interested in the result modulo 2. D n is then built from C n as follows. First, note that p n has degree n -1. We compute each homogeneous component separately: each gate α of C n is split into n -1 gates α 1 , . . . , α n-1 , the gate α i computing the homogeneous component of degree i of α. The homogeneous components of degree 0 (i.e. the constants) are not computed, only their remainder modulo 2 is taken into account. In other words, we replace an even constant by the constant 0, and an odd one by 1. The Puniformity remains because we can compute in polynomial time the the constants modulo 2. The last step of D n is to compute the sum of the homogeneous components of the output gate.

It is easy and well known how to compute these homogeneous components at each step, while keeping a polynomial circuit size: we merely discard the homogeneous components of degree > n -1. With this construction, it is clear that p n and q n coincide modulo 2, that the construction is P-uniform, and that the formal degree of D n is at most n -1 because there is no constant in the circuit any more. Hence (q n ) ∈ VP 0 .

In order to decide ⊕HamiltonPath, we therefore only have to compute the value of q n modulo 2 on the given input, that is, to evaluate a P-uniform circuit of polynomial size s(n) and polynomially bounded formal degree n -1. Theorem 5.3 of [START_REF] Miller | Efficient parallel evaluation of straight-line code and arithmetic circuits[END_REF] tells us that such a circuit can be evaluated modulo 2 by a logspaceuniform algorithm in parallel time O(log(s(n)) log(ns(n))), i.e. O(log(n) 2 ), and with O(n 2 ) processors, thus placing ⊕P in P-uniform NC 2 .

Hence, assuming that Uniform VPSPACE 0 = Uniform VP 0 nb we have proved that PSPACE = P ⊆ ⊕P ⊆ P-uniform NC 2 .

Note that this construction does not seem to be logspace uniform because evaluating the constants modulo 2 is a P-complete problem.

Since we construct a circuit family which is only polynomial-time uniform, one could also use the construction of [START_REF] Valiant | Fast parallel computation of polynomials using few processors[END_REF] instead of the parallel algorithm of [START_REF] Miller | Efficient parallel evaluation of straight-line code and arithmetic circuits[END_REF]. Indeed, as pointed out in [START_REF] Miller | Efficient parallel evaluation of straight-line code and arithmetic circuits[END_REF], the construction of [START_REF] Valiant | Fast parallel computation of polynomials using few processors[END_REF] can be performed in polynomial time.

⊓ ⊔ Remark 1. Despite its unlikeliness, the separation "PSPACE = P-uniform NC" is not known to hold to the authors' knowledge (by contrast, PSPACE can be separated from logspace-uniform NC thanks to the space hierarchy theorem).

Sign Conditions

Definition

Given are s polynomials f 1 , . . . , f s ∈ Z[x 1 , . . . , x n ]. A sign condition is merely an s-tuple S ∈ {-1, 0, 1} s . Intuitively, the i-th coordinate of S represents the sign of f i : -1 for < 0, 0 for 0, and 1 for > 0. Accordingly, the sign condition of a point x ∈ R n is the tuple S ∈ {-1, 0, 1} s such that

S i = -1 if f i (x) < 0, S i = 0 if f i (x) = 0 and S i = 1 if f i (x) > 0.
Of course some sign conditions are not realizable, in the sense that the polynomials can nowhere take the corresponding signs (think for instance of x 2 + 1 which can only take positive values over R). We say that a sign condition is satisfiable if it is the sign condition of some x ∈ R n and we call N the number of satisfiable sign conditions. The key result detailed in the next section is that among all possible sign conditions, there are few satisfiable ones (i.e. N is small), and there exists a polynomial space algorithm to enumerate them all.

A PSPACE Algorithm for Sign Conditions

The following theorem will prove to be a central tool in our proofs. The bound on the number of satisfiable sign conditions follows from the Thom-Milnor bounds [START_REF] Milnor | On Betti numbers of real varieties[END_REF] (see Grigoriev [START_REF] Grigoriev | Complexity of deciding Tarski algebra[END_REF]Lemma 1]); the enumeration algorithm is from Renegar [START_REF] Renegar | On the computational complexity and geometry of the first-order theory of the reals, part 1[END_REF]Prop. 4.1].

Theorem 1. Let f 1 , . . . , f s ∈ Z[x 1 , . . . ,
x n ] be s polynomials of maximal degree d, and whose coefficients have bit size ≤ L. Then:

1. there are N = (sd) O(n) satisfiable sign conditions; 2. there is an algorithm using work space (log L)[n log(sd)] O (1) which, on input (f 1 , . . . , f s ) in dense representation, and (i, j) in binary, outputs the j-th component of the i-th satisfiable sign condition.

If S is the i-th satisfiable sign condition produced by this enumeration algorithm, we say that the rank of S is i (the rank is therefore merely the index of the sign condition in the enumeration). Note that if d = 2 n O(1) , s = 2 n O(1) and L = 2 n O(1) as will be the case, then the work space of the algorithm is polynomial in n.

Enumerating all Possibly Tested Polynomials

In the execution of an algebraic circuit, the values of some polynomials at the input x are tested to zero. If two points x and ȳ have the same sign condition with respect to all polynomials possibly tested to zero, then they will either both belong to the language, or both be outside of it: indeed the results of all the tests will be the same during the execution of the circuit. Therefore we can handle sign conditions (i.e. boolean words) instead of algebraic inputs. Note that in order to find the sign condition of the input x, we have to be able to enumerate in polynomial space all the polynomials that can ever be tested to zero in some computation of an algebraic circuit. This is done as in [START_REF] Cucker | On the power of real Turing machines over binary inputs[END_REF]Th. 3]. Proposition 6. Let C be a constant-free algebraic circuit with n variables and of depth d.

1. The number of different polynomials possibly tested to zero in some compu-

tation of C is 2 d 2 O(n) .
2. There exists an algorithm using work space (nd) O(1) which, on input C and integers (i, j) in binary, outputs the j-th bit of the i-th of these polynomials.

Proof. C is sliced in levels corresponding to the depth of the gates: input gates are on the level 0 and the output gate is the only one on level d. Suppose that the results of the tests of the levels 0 to i -1 are fixed: we can then compute all the polynomials tested at level i. Since our agebraic circuits have fan-in at most 2, there are at most 2 d-i gates on level i of C: in particular, at most 2 d-i polynomials can be tested on level i. But the degree of a polynomial computed at level i is at most 2 i and the size of its coefficients is (nd) O(1) 2 i . Therefore, by Theorem 1 there are at most (2 d ) O(n) possible outcomes for the tests of level i, and they are moreover enumerable in space (nd) O (1) . Therefore we can compute all the (2 d ) O(n) possible outcomes of all the tests of level i and proceed inductively. This gives an algorithm using work space (nd) O (1) for enumerating all the polynomials that can possibly be tested in an execution of the circuit. Since there are 2 dO(n) possible outcomes at each level, the total number of polynomials for the whole circuit (that is, for

d levels) is (2 dO(n) ) d = 2 d 2 O(n) ,
as claimed in the statement of the proposition.

⊓ ⊔

Note that this proposition can also be useful when our algebraic circuit is not constant-free: it is enough to replace the constants by fresh variables. The only risk is indeed to take more polynomials into account since we have replaced specific constants by generic variables.

A Transfer Theorem

In this section we prove our main result. Theorem 2. Uniform VPSPACE 0 = Uniform VP 0 nb =⇒ PAR 0 R = P 0 R . Note that the collapse of the constant-free class PAR 0 R to P 0 R implies the collapse of PAR R to P R : just replace constants by new variables in order to transform a PAR R problem into a PAR 0 R problem, and then replace these variables by their orignal values in order to transform a P 0 R problem into a P R problem. Let A ∈ PAR 0 R : it is decided by a uniform family (C n ) of constant-free algebraic circuits of polynomial depth. For convenience, we fix n and work with C n . For the proof of Theorem 2 we will need to find the sign condition of the input x with respect to the polynomials f 1 , . . . , f s of Proposition 6, that is to say, with respect to all the polynomials that can be tested to zero in an execution of C n . We denote by N the number of satisfiable sign conditions with respect to f 1 , . . . , f s .

Note that most of the forthcoming results depend on the polynomials f 1 , . . . , f s , therefore on the choice of C n . For instance, once C n and f 1 , . . . , f s are chosen, the satisfiable sign conditions are fixed and we will speak of the i-th satisfiable sign condition without referring explicitly to the polynomials f 1 , . . . , f s .

In order to find the sign condition of the input, we will give a polynomialtime algorithm which tests some VPSPACE family for zero. Here is the formalized notion of a polynomial-time algorithm with VPSPACE tests. Definition 6. A polynomial-time algorithm with Uniform VPSPACE 0 tests is a Uniform VPSPACE 0 family (f n (x 1 , . . . , x u(n) )) together with a uniform constantfree family (C n ) of polynomial-size algebraic circuits endowed with special test gates of indegree u(n), whose value is 1 on input (a 1 , . . . , a u(n) ) if f n (a 1 , . . . , a u(n) ) ≤ 0 and 0 otherwise.

Observe that a constant number of Uniform VPSPACE 0 families can be used in the preceding definition instead of only one: it is enough to combine them all in one by using "selection variables". The following Theorem 3 is the main result en route to showing the transfer theorem. It is proved via successive lemmas in Sections 6.1 to 6.3: we proceed as in [START_REF] Grigoriev | Topological complexity of the range searching[END_REF] but constructively.

Theorem 3. There is a polynomial-time algorithm with Uniform VPSPACE 0 tests that, on input x, computes the rank of the sign condition of x with respect to f 1 , . . . , f s .

Truncated Sign Conditions

A truncated sign condition is merely an element T of {0, 1} s . Contrary to full sign conditions, only the two cases = 0 and = 0 are distinguished. We define in a natural way the truncated sign condition T of a point x:

T i = 0 if and only if f i (x) = 0.
Of course, there are fewer satisfiable truncated sign conditions than full ones, and of course there exists a polynomial space algorithm to enumerate them. Furthermore, truncated sign conditions can be viewed as subsets of {1, . . . , s} (via the convention k ∈ T ⇐⇒ T k = 1), therefore enabling us to speak of inclusion of truncated sign conditions.

We fix an order ≤ T compatible with inclusion and easily computable in parallel, e.g. the lexicographic order. Let us call T (i) the i-th satisfiable truncated sign condition with respect to this order. Lemma 6. There is an algorithm using work space polynomial in n which, on input (f 1 , . . . , f s ) in dense representation, and (i, j) in binary, outputs the j-th component of T (i) (the i-th satisfiable truncated sign condition with respect to ≤ T ).

Proof. It is enough to use the algorithm of Theorem 1, followed by a fast parallelsorting procedure, for instance Cole's parallel merge-sort algorithm [START_REF] Cole | Parallel merge sort[END_REF].

⊓ ⊔

Note that the truncated sign condition of the input x is the maximal truncated satisfiable sign condition T satisfying ∀i, T i = 1 ⇒ f i (x) = 0. Hence we have to find a maximum. This will be done by binary search. Lemma 7. There is a Uniform VPSPACE 0 family (g n ) of polynomials satisfying, for real x and boolean i,

g n (x, i) = j≤i k ∈T (j) f k (x) 2 .
Proof. Lemma 6 asserts that deciding whether k ∈ T (j) is in PSPACE. Then we use twice Lemma 3 (once for the sum and once for the product).

⊓ ⊔ Proposition 7. There is a polynomial-time algorithm with Uniform VPSPACE 0 tests which on input x outputs the rank m of its truncated sign condition T (m) .

Proof. The algorithm merely consists in performing a binary search thanks to the polynomials of Lemma 7: if the truncated sign condition of the input x is T (m) , then j≤i k ∈T (j) f k (x) 2 = 0 if and only if m ≤ i. By making i vary, we find m in a number of steps logarithmic in the number of satisfiable truncated sign conditions, i.e. in polynomial time.

⊓ ⊔

Binary Search for the Full Sign Condition

We say that a (full) sign condition S is compatible with the truncated sign condition T if ∀i, T i = 0 ⇔ S i = 0 (i.e. they agree for "= 0" and for " = 0").

Let N ′ denote the number of (full) satisfiable sign conditions compatible with the truncated sign condition of the input x. Obviously, N ′ ≤ N . The following lemma is straightforward after Lemma 6 and Theorem 1.

Lemma 8. There is an algorithm using work space polynomial in n which, on input (i, j, k), ouputs the j-th bit of the i-th satisfiable sign condition compatible with T (k) .

Since we know the truncated sign condition of x after running the algorithm of Proposition 7, we know which polynomials vanish at x. We can therefore discard the zeros in the (full) compatible satisfiable sign conditions. Hence we are now concerned with two-valued sign conditions, that is, elements of {-1, 1} s ′ with s ′ ≤ s. In what follows arithmetic over the field of two elements will be used, hence it will be simpler to consider that our sign conditions have values among {0, 1} instead of {-1, 1}: 0 for > 0 and 1 for < 0. Thus sign conditions are viewed as vectors over {0, 1}, or alternately as subsets of {1, . . . , s ′ }. The set {0, 1} s ′ is endowed with the inner product u.v = i u i v i (mod 2), and we say that u and v are orthogonal whenever u.v = 0 (see [START_REF] Charbit | Finding a vector orthogonal to roughly half a collection of vectors[END_REF]).

The following proposition from [START_REF] Charbit | Finding a vector orthogonal to roughly half a collection of vectors[END_REF] will be useful. It consists in an improvement of the result of [START_REF] Grigoriev | Topological complexity of the range searching[END_REF]: first (and most importantly), it is constructive, and second, the range

[N ′ /2 - √ N ′ /2, N ′ /2 + √ N ′ /2] here is much better than the original one [N ′ /3, 2N ′ /3]. Proposition 8. Let V be a set of N ′ vectors of {0, 1} s ′ .
1. There exists a vector u orthogonal to at least N ′ /2 -√ N ′ /2 and at most N ′ /2 + √ N ′ /2 vectors of V . 2. Such a vector u can be found on input V by a logarithmic space algorithm.

Our aim is to find the sign condition of x. We will use Proposition 8 in order to divide the cardinality of the search space by two at each step. This is based on the following observation: if u ∈ {0, 1} s ′ , the value of the product j∈u f j (x) is negative if the inner product of u and the sign condition of x is 1, and is positive otherwise. The idea is then to choose u judiciously so that the number of satisfiable sign conditions having the same inner product with u as the sign condition of x is halved at each step. Therefore, in a logarithmic number of steps, the sign condition of x will be uniquely determined. This gives the following algorithm for finding the sign condition of x.

-Let E be the set of all the satisfiable sign conditions.

-While E contains more than one element, do

• Find by Proposition 8 a vector u orthogonal to at least |E|/2 -|E|/2 and at most |E|/2 + |E|/2 vectors of E. • Let b be the result of the test " j∈u f j (x) < 0?".

• Let the new E be the set of all sign conditions in E which have inner product b with u. -Enumerate all the satisfiable sign conditions and find the one that produces exactly the same results as in the loop: this is the sign condition of x.

Note that the number of steps is O(log N ′ ), which is polynomial in n. The last step of this algorithm (namely, recovering the rank of the sign condition of x from the list of results of the loop) is detailed in Section 6.3.

We now show how to perform this algorithm in polynomial time with Uniform VPSPACE 0 tests. The main technical difficulty is that according to Definition 6 we can use only one VPSPACE family, whereas we want to make adaptive tests. We therefore have to store the intermediate results of the preceding tests in some variables c (a "list of choices") of the VPSPACE polynomial. Proposition 8 shows that, by reusing space, there exists a logspace algorithm that, given any set V of N ′ vectors together with a "list of choices" c ∈ {0, 1} l (with l = O(log N ′ )), enumerates l + 1 vectors u (1) , . . . , u (l+1) satisfying the following condition (⋆):

u (1) is orthogonal to at least N ′ /2 -√ N ′ /2 and at most

N ′ /2 + √ N ′ /2 vectors of V . -Let V i ⊆ V be the subset of all the vectors v ∈ V satisfying ∀j ≤ i, v.u (j) = c j . Then the vector u (i+1) is orthogonal to at least |V i |/2 -|V i |/2 and at most |V i |/2 + |V i |/2 vectors of V i .
Note that |V i | is roughly divided by 2 at each step, so the number of steps is O(log N ′ ). In particular, since s ′ and N ′ are simply exponential, the following lemma is easily derived by combining what precedes with Lemma 8.

Lemma 9. There is an algorithm using work space polynomial in n which, on input (i, j, k, c) in binary, outputs the j-th bit of u (i) ∈ {0, 1} N ′ , where the vectors u (1) , . . . , u (l+1) satisfy condition (⋆) for the input consisting of:

the set V of the N ′ (full) satisfiable sign conditions compatible with T (k) , -together with the list of choices c ∈ {0, 1} l .

Lemma 10. There exists a Uniform VPSPACE 0 family (h n ) satifsying, for real x and boolean (i, k, c):

h n (x, i, k, c) = j∈u (i) f j (x),
where u (1) , . . . , u (l+1) are defined as in Lemma 9 (in particular they depend on T (k) ).

Proof. Lemma 9 asserts that deciding whether j ∈ u (i) is done in polynomial space. The use of Lemma 3 then concludes the proof. ⊓ ⊔ Therefore, by a Uniform VPSPACE 0 test, one is able to know the sign of the polynomial h n (x, i, k, c) = j∈u (i) f j (x). As mentioned before, this gives us the inner product of u (i) and the (full) sign condition of x: this sign is < 0 if and only if the inner product is 1. By beginning with c = 0 • • • 0 (step 1), and at step i ≥ 2 letting c i-1 = 1 if and only if the preceding test was < 0, the number of sign conditions that have the same inner products as that of x is divided by (roughly) two at each step. At the end, we therefore have a list of choices c that only the sign condition of x fulfills. This proves the following lemma.

Lemma 11. There is a polynomial-time algorithm with Uniform VPSPACE 0 tests which on input x outputs the list of choices c (defined as above) which uniquely characterizes the sign condition of x, provided we know the rank k of the truncated sign condition T (k) of x.

We are now able to recover the rank of the sign condition of x from this information, as explained in the next section.

Recovering the Rank of the Sign Condition

Lemma 12. There is an algorithm using work space polynomial in n which, on input c ∈ {0, 1} l (a list of choices) and k, outputs the rank of a satisfiable sign condition compatible with T (k) that fulfills the list of choices c.

Proof. In polynomial space we recompute all the vectors u (i) as in Lemma 9, then we enumerate all the sign conditions thanks to Theorem 1 until we find one that fulfills the list of choices c.

⊓ ⊔

The proof of Theorem 3 follows easily from Proposition 7 and Lemmas 11-12.

A Polynomial-time Algorithm for PAR R Problems

Remember that A ∈ PAR 0 R and (C n ) is a uniform family of polynomial-depth algebraic circuits deciding A.

Lemma 13. There is a (boolean) algorithm using work space polynomial in n which, on input i (the rank of a satisfiable sign condition), decides whether the elements of the i-th satisfiable sign condition S are accepted by the circuit C n .

Proof. We follow the circuit C n level by level. For test gates, we compute the polynomial f to be tested. Then we enumerate the polynomials f 1 , . . . , f s as in Proposition 6 for the circuit C n and we find the index j of f in this list. By consulting the j-th bit of the i-th satisfiable sign condition with respect to f 1 , . . . , f s (which is done by the polynomial-space algorithm of Theorem 1), we therefore know the result of the test and can go on like this until the output gate.

⊓ ⊔ Theorem 4. Let A ∈ PAR 0 R . There exists a polynomial-time algorithm with Uniform VPSPACE 0 tests that decides A.

Proof. A is decided by a uniform family (C n ) of polynomial depth algebraic circuits. On input x, thanks to Theorem 3 we first find the rank of the sign condition of x with respect to the polynomials f 1 , . . . , f s of Proposition 6. Then we conclude by Lemma 13.

⊓ ⊔ Theorem 2 follows immediately from this result. One could obtain other versions of these two results by changing the uniformity conditions or the role of constants.

  ). Denote by Mon d the set of all monomials in X 0 , . . . , X n of degree d: the cardinal of Mon d is N = d+n d . The matrix M has N rows and N columns, both indexed by the elements of Mon d . The row corresponding to the monomial xα represents the polynomial xα x di i f i , where i = min{j; x dj j divides xα }.

Lemma 4 .

 4 VPSPACE b = VP ⇐⇒ VPSPACE = VP nb .

⊓ ⊔ 4

 4 On the Hypothesis that VPSPACE has Small Circuits In this section, we investigate some consequences of the hypotheses VPSPACE = VP nb and Uniform VPSPACE 0 = Uniform VP 0 nb . Proposition 3. Under the generalized Riemann hypothesis (GRH), VP nb = VPSPACE ⇐⇒ [P/poly = PSPACE/poly and VP = VNP].