Frédéric Alexandre
email: frederic.alexandre@inria.fr

Beyond Machine Learning : Autonomous Learning

Keywords: Machine Learning, Computational Neuroscience, Autonomous Learning

Recently, Machine Learning has achieved impressive results, surpassing human performances, but these powerful algorithms are still unable to define their goals by themselves or to adapt when the task changes. In short, they are not autonomous. In this paper, we explain why autonomy is an important criterion for really powerful learning algorithms. We propose a number of characteristics that make humans more autonomous than machines when they learn. Humans have a system of memories where one memory can compensate or train another memory if needed. They are able to detect uncertainties and adapt accordingly. They are able to define their goals by themselves, from internal and external cues and are capable of self-evaluation to adapt their learning behavior. We also suggest that introducing these characteristics in the domain of Machine Learning is a critical challenge for future intelligent systems.

INTRODUCTION

Machine Learning has achieved impressive results recently, for a variety of applications ranging from text and natural scene labeling [START_REF] Farabet | Learning hierarchical features for scene labeling[END_REF] to games as difficult as the Go [START_REF] Clark | Training Deep Convolutional Neural Networks to Play Go[END_REF]. Notably, these results have been mentioned as surpassing human performances but this kind of statements deserves some comments. It is true that the AlphaGo computer program by Google DeepMind was the first to beat a professional player and that some software tools developed by Facebook are able to analyze a thousand of posts per second, clearly beyond human performances. These undoubtly impressive results mainly rely on one major characteristic of their underlying algorithms like Deep Learning (LeCun et al., 2015): their learning is based on a combinatorial analysis of cases extracted from huge databases, specifically dedicated to their narrow domain of expertise. AlphaGo can only play Go. A deep learning system trained to extract faces from pictures can only identify faces.

In contrast, one remarkable characteristic of human learning is that, whereas we are in general not excellent in one specific domain, we are quite good in most of them. In addition, we are able to adapt when a new problem appears. This high level of adaptability can be seen by other signs. With neither explicit la-bels, nor data preprocessing or segmentation, we are able to pay attention to important information and neglect noise. We define by ourselves our goals and the means to reach them, we self-evaluate our performances and re-exploit previously learned knowledge and strategies in some different context. All these characteristics are notably absent from classical Machine Learning approaches.

In summary, whereas Machine Learning demonstrates an impressive brute force of learning in specific domains, humans are versatile and adaptable and can learn in a changing and uncertain world: We are good at autonomous learning. Comparing both kinds of learning is difficult because they address different characteristics; nevertheless, it can be said that autonomous learning is probably an important characteristic, as one want to embed intelligent modules in robots or in interfaces dedicated to act in the real world. It is consequently important to wonder how Machine Learning could integrate more autonomy, instead of just developing more power as it is mainly proposed in most research programs.

The goal of this position paper is not to compare the performances of two approaches, bio-inspired and purely based on mathematics. Neither is it to give precise recipes to improve existing techniques. Instead, we would like to convince the reader that autonomy is a primary property for learning and to in-troduce two kinds of information that might be useful to develop more autonomous machine learning. One the one hand, we would like to define more precisely what being autonomous means: even if this property may seem obvious, it is sometimes difficult to concretely explain which characteristics are the bases of an autonomous analysis of our situation and of the best decision to make. One the other hand, we propose to mention the main cerebral structures and circuits involved in these facets of autonomous behavior. This might be useful to decide for future research topics. To do so, we propose to describe here a series of characteristics of the human brain that participates in our capability to learn autonomously, with the idea that introducing these characteristics in artificial neural systems could orient Machine Learning toward Autonomous Machine Learning.

AN INTERACTING SYSTEM OF MEMORIES

It is known for a long time [START_REF] Squire | Declarative and nondeclarative memory: multiple brain systems supporting learning and memory[END_REF] that specific circuits in the brain are mobilized to learn explicit knowledge and others to learn procedures. These functions have been respectively addressed by recurrent [START_REF] Hopfield | Neural networks and physical systems with emergent collective computational abilities[END_REF] and layered [START_REF] Rosenblatt | The perceptron: a probabilistic model for information storage and organization in the brain[END_REF] neural networks, the latter being the ancestor of the deep learning networks. It has also been advocated [START_REF] Alexandre | Biological Inspiration for Multiple Memories Implementation and Cooperation[END_REF] that realistic models of memory should include both kinds of networks to be able to learn by heart specific events as well as generalize some skills from a set of experiences.

Besides modeling these circuits, studying their interactions is also crucial to understand how one system can compensate for or supervise another system, resulting in a more autonomous learning. In particular, interaction between systems can lead to situations where one system can propose an answer (possibly of lower quality) if the other one is too specific or is not trained enough or even if it has been damaged. It can consequently give more time to the other one to become more general or more mature, or to recover. As we will exemplify below, interaction between systems can also more directly give the opportunity to one system to send well selected cases to train the other system. In both cases, the mechanisms are internal and do not require help from the external world, hence an increased autonomy.

For example, in the domain of perceptual learning in the medial temporal lobe, models of the hippocampus can store in episodic memories important events in one trial [START_REF] Kassab | Integration of exteroceptive and interoceptive information within the hippocampus: a computational study[END_REF][START_REF] O'reilly | Conjunctive Representations in Learning and Memory: Principles of Cortical and Hippocampal Function[END_REF]. This neural structure is also known [START_REF] Mcclelland | Why there are complementary learning systems in the hippocampus and neocortex: insights from the successes and failures of connectionist models of learning and memory[END_REF] to form later, by consolidation in other circuits, new semantic categories. In the domain of decision-making in the loops between the prefrontal cortex and the basal ganglia, models of cerebral mechanisms are currently developed [START_REF] Piron | The globus pallidus pars interna in goal-oriented and routine behaviors: Resolving a long-standing paradox[END_REF], by which goal-directed behavior relying on explicit evaluation of expected rewards can later become habits, automatically triggered with less flexibility but increased effectiveness.

In both cases (either perceptual or motor), the strategy of learning is first to store some specific cases of interest and to recall them if necessary. Then if it appears that similar cases frequently occur, the strategy will be to find some generality and build a generic rule or procedure to deal with such cases. Building such rules from the initially stored cases has several advantages, among which autonomy is not the least. Understanding how both kinds of memory cooperate can lead to an autonomous learning system, able to cope with facts and rules, to elaborate rules from selected facts and to decide which kind of memory is the most adapted to the current situation.

COPING WITH UNCERTAINTY

We learn the rules that govern the world and consider it uncertain for two main reasons: it can be predictable up to a certain level (stochastic rules) or non-stationary (changing rules). Whereas standard probabilistic models are rather good at tackling the first kind of uncertainty, non-stationarity in a dynamic world raises more difficult problems [START_REF] Cohen | Should I stay or should I go? How the human brain manages the trade-off between exploitation and exploration[END_REF]. Learning in autonomy in the real (and hence uncertain) world consequently implies to be able to autonomously give the best explanation to the fact that a previously valid rule has given an unsatisfactory result: Is it just noise or has the rule changed ? It also implies of course to trigger the corresponding best answer (respectively modifying the level of stochasticity associated to the rule or, more critically, selecting another rule in the set of previously designed rules or elaborating a new rule).

Concerning the first point, we are studying how regions of the medial prefrontal cortex are detecting and evaluating the kind and the level of uncertainty by monitoring recent history of performance at managing correctly incoming events (Carrere and Alexandre, 2016a). Concerning the second point, these prefrontal regions and other cerebral regions sensitive to reward prediction errors are also reported to activate the release of neuromodulators like monoamines, known to play a central role in adaptation to uncertainties [START_REF] Doya | Metalearning and neuromodulation[END_REF][START_REF] Alexandre | Modeling neuromodulation as a framework to integrate uncertainty in general cognitive architectures[END_REF].

Acetylcholine has been reported to be an important factor in case of stochasticity [START_REF] Yu | Uncertainty, Neuromodulation, and Attention[END_REF] and has been modeled as increasing the signal-to-noise ratio in the sensory cortex [START_REF] Pauli | Attentional control of associative learning-a possible role of the central cholinergic system[END_REF] and promoting learning about the context [START_REF] Carrere | A pavlovian model of the amygdala and its influence within the medial temporal lobe[END_REF]. We have also recently studied the role of noradrenaline in unstationary environments (Carrere and Alexandre, 2016b) and have proposed a biologically-inspired model, proposing that the balance between exploration and exploitation of sensory cues associated to a rule can be modified by the action of noradrenaline on critical cerebral regions. Similarly, the tonic level of dopamine has been reported as increasing when an unstationary environment is detected and as modifying the balance between exploration and exploitation of motor aspects of the rule [START_REF] Humphries | Dopaminergic control of the exploration-exploitation trade-off via the basal ganglia[END_REF]. Altogether, the brain can be presented as a system able to autonomously detect the level of uncertainty and to autonomously modify the way to exploit and update previously acquired rules or to design new rules, with the help of neuromodulators, seen as a meta-learning system modifying hyperparameters of learning algorithms [START_REF] Doya | Metalearning and neuromodulation[END_REF].

DEFINING GOALS BY EMBODIMENT AND EMOTIONAL LEARNING

One major difference between artificial and natural learning systems is that the latter ones can autonomously detect and define their goals in the surrounding environment. This is important to choose what to learn and to orient attentional systems accordingly. Instead of learning from a corpus prepared offline, learning is made online and adapted to what has happened during the behavior. In addition, if learning is centred on cues that are important for the agent, like mates, preys or predators, the agent will be probably more efficient than if learning is made from a randomly sampled corpus. The ability to detect ones goals is due to several ingredients. First our body itself tells us by interoception [START_REF] Craig | Interoception: the sense of the physiological condition of the body[END_REF] what is good or bad for us; what must be searched or avoided. It is consequently important for a really autonomous learning agent not only to have a model of the brain with classical cognitive functions related to perception, learning, attention or deliberation but also to feed that model with information coming from a substrate corresponding to the body, including sensors for pain and pleasure.

In the cerebral system, the perceptive system is pre-wired to automatically detect biologicallysignificant aversive and appetitive (emotional) stimuli and to trigger pavlovian reflexes [START_REF] Kim | Mechanisms contributing to the induction and storage of Pavlovian fear memories in the lateral amygdala[END_REF]. Subsequently, pavlovian learning will allow to anticipate these stimuli by the detection of predictive stimuli that will in turn trigger preparatory behavior [START_REF] Cardinal | Emotion and motivation: the role of the amygdala, ventral striatum, and prefrontal cortex[END_REF]. All these stimuli are key targets for attentional processing and correspond to the main goals organizing the behavior. Learning to detect them automatically is consequently important for autonomy, since attentional and learning systems will be fed by an over-representation of these meaningful examples, in contrast to artificial systems that only learn from a stereotyped and artificially prepared corpus. It is consequently important to propose models implementing these pavlovian mechanisms [START_REF] Krasne | Design of a Neurally Plausible Model of Fear Learning[END_REF][START_REF] Carrere | A pavlovian model of the amygdala and its influence within the medial temporal lobe[END_REF] and also the effects of Pavlovian responses onto the body and the neuromodulatory system (Carrere and Alexandre, 2016b).

MOTIVATION AND SELF-EVALUATION

Specifying relations between the brain and the body is also an opportunity to introduce physiological needs, fundamental to consider internal goals in addition to external goals evoked above. Indeed, it is important for an agent to learn autonomously, as one of its major constraints is to survive by monitoring some internal variables within vital bounds. One of its primary goals will be to elaborate and select behaviors that help controlling these variables, which can be done in autonomy and not by obeying a supervising system. It is consequently required that the critical internal variables be perceived, carefully processed and participate to decision making: They are undoubtly key cues for an organization of behavior decided in full autonomy. Such a consideration is also the basis for renewed approaches regarding reinforcement learning. Indeed an important aspect of autonomous decision making is to be able to adapt the behavior as a compromise between external goals (what should be searched and avoided) and internal goals (what are the current needs), whereas classical reinforcement learning generally relies on optimizing a simple scalar representing an abstract reward, artificially given in some situations. To progress in that aim, it is fundamental to better understand how internal and external goals (motivational and emotional cues) are combined in decision making [START_REF] Zahm | Functional-anatomical implications of the nucleus accumbens core and shell subterritories[END_REF][START_REF] Mannella | The nucleus accumbens as a nexus between values and goals in goal-directed behavior: a review and a new hypothesis[END_REF][START_REF] Kolling | Multiple signals in anterior cingulate cortex[END_REF].

In humans, another important source of information for learning autonomously is based on selfevaluation of the performances. Not only this information can recommand what to learn but, more importantly, it can orient the behavior to explore situations that are best adapted to current expertise and give what is called intrinsic motivations [START_REF] Oudeyer | Intrinsic motivation systems for autonomous mental development[END_REF]. It is noticeable that both motivation and self-evaluation processing are central in cognitive control [START_REF] Koechlin | The Architecture of Cognitive Control in the Human Prefrontal Cortex[END_REF] and reported to be located in the anterior part of the prefrontal cortex, that should be consequently critical targets for future researches, particularly to understand how behavioral rules are elaborated and selected from self-evaluation in the prefrontal cortex [START_REF] Badre | Cognitive control, hierarchy, and the rostrocaudal organization of the frontal lobes[END_REF][START_REF] Donoso | Foundations of human reasoning in the prefrontal cortex[END_REF].

DISCUSSION

In this position paper, we have first noticed that natural and artificial learning systems differ because, whereas the latter ones are high level specialists in a restricted and artificially sampled domain, the former ones are rather characterized by their intrinsic adaptability to any situation and their capacity to update their knowledge and skills accordingly. Basically, this refers to the function of learning in living systems. Their primary goal is to survive and breed in an unknown environment. As their environment is generally too complex and changing to only consider pre-wired behavioral rules, their knowledge and skills must evolve and adapt to what is perceived internally and externally.

Of course, even in living agents, a part of the adaptation can be dictated during epigenesis by external resources, like genes or social and educational environments, but, most of the time, this adaptation must be done in autonomy and is the main goal of learning processes. In this paper, we have consequently set the focus on autonomy, seen as a primary ingredient of learning and we have explored more precisely several characteristics that, we believe, are the way autonomy can be expressed during learning. In short, we propose that autonomous learning is made easier because our different systems of memory can interact and exchange information, because we are able to estimate the kind of uncertainty we are facing and to propose the suitable adaptation, because we can perceive important noxious and positive events in the environment and inside our body, learn to predict them and build the underlying behavioral rules to optimize in some way their occurrence or avoidance.

We have also mentioned the hypothetized under-lying cerebral circuitry for each of these mechanisms and have reported modeling efforts to better understand them. Importantly, we think that these models are important not only for computational neuroscience but also for Machine Learning. Transfering these principles to classical learning algorithms would endow them with more autonomy, which is critical in a context where it is more and more aimed at integrating an Artificial Intelligence in autonomous agents and interfaces.

Up to now, we have only enumerated a list of characteristics, whereas an essential goal for a real autonomy would be to integrate all of them in an agent, corresponding to a physically identified and separated entity, thrown in an unknown environment with the recommendation to survive and no subsequent help.

In this perspective, we have recently designed a software platform [START_REF] Denoyelle | VirtualEnaction: A Platform for Systemic Neuroscience Simulation[END_REF] where an autonomous agent with an artificial body can explore an unknown virtual world. The platform is designed in such a way that the characteristics of the agent's body and of the environment can be easily specified and long lasting experiments can be run to evaluate its survival performances. The main challenge is now to integrate more and more sophisticated versions of the mechanisms evoked above to better understand how they interact and how a viable Autonomous Machine Learning framework can be defined. We are also presently experimenting that, beyond Machine Learning, this numerical testbed is also a precious simulation tool for our medical and neuroscientist colleagues.


Ioannis Z Emiris

Anna Karasoulou

Charilaos Tzovas

Approximating Multidimensional Subset Sum and the Minkowski Decomposition of Polygons $

We consider the approximation of two NP-hard problems: Minkowski Decomposition (MinkDecomp) of lattice polygons in the plane and the closely related problem of Multidimensional Subset Sum (kD-SS) in arbitrary dimension. In kD-SS we are given an input set S of k-dimensional vectors, a target vector t and we ask, if there exists a subset of S that sums to t. We prove, through a gap-preserving reduction, that, for general dimension k, kD-SS is not in APX although the classic 1D-SS is in PTAS. On the positive side, we present an O(n 3 / 2 ) approximation grid based algorithm for 2D-SS, where n is the cardinality of the set and bounds the difference of some measure of the input polygon and the sum of the output polygons. We also describe two more approximation algorithms with a better experimental ratio. Applying one of these algorithms, and a transformation from MinkDecomp to 2D-SS, we can approximate Mink-Decomp. For an input polygon Q and parameter , we return two summands A and B such that A + B = Q with Q being bounded in relation to Q in terms of volume, perimeter, or number of internal lattice points, an additive error linear in and up to quadratic in the diameter of Q. A similar function bounds the Hausdorff distance between Q and Q . We offer experimental results based on our implementation.

$ The authors were

Introduction

Every polynomial is related with its Newton polytope and, using a theorem of Ostrowski, Gao devised an irreducibility test for a polynomial. Here, we consider the problem of decomposition of integral polygons. A polygon Q is called an (integral) lattice polygon, when all its vertices are points with integer coordinates.

A polygon Q is called an (integral) lattice polygon, when all its vertices are points with integer coordinates.

Definition 1. The Minkowski sum of two sets of vectors A and B in Euclidean space is defined by adding each vector in A to each vector in B, namely:

A+B = {a + b | a ∈ A, b ∈ B}.
Problem 2. Minkowski Decomposition (MinkDecomp). Given a lattice convex polygon Q, decide if it is decomposable, that is, if there are nontrivial lattice polygons A and B such that A + B = Q, where + denotes the Minkowski sum. The polygons A and B are called summands.

?? is proven NP-complete in [? ] and can be reduced to 2D-SS. For the reduction see ??. The approximation version can be defined as follows.

Problem 3. MinkDecomp-µ-approx

Input: A lattice polygon Q, a parameter 0 < < 1 and a function µ.

Output: Lattice polygons A, B such that 0 ≤ µ(A + B)µ(Q) < • φ(D), where D is the diameter of Q and φ a polynomial. We call such an output an

• φ(D)-solution.

For µ we may consider the functions vol(Q): the volume, per(Q): the perimeter, i(Q): the internal lattice points of Q or d H (Q, A + B): the Hausdorff distance between Q and A + B. An interesting question is what other functions we can use to measure the similarity of two polygons.

Problem 4. kD-Subset Sum (kD-SS)

Input: A vector set S = {v i | v i ∈ Z k , 1 ≤ i ≤ n, k ≥ 1} and a target vector t ∈ Z k .
Output: Decide, whether there exists a vector subset S ⊆ S such that

v i = t, v i ∈ S .
This is a generalization of the classic 1D-SS problem, and as such, is also NP-complete.

Let P i be the set of all possible vector sums that can be produced by adding at most i vectors among the first vectors in S. Then, P n ⊆ Z k is the set of all possible vector sums. Here is the approximation version:

Problem 5. kD-SS-opt

Input: A set S = {v i | v i ∈ Z k , 1 ≤ i ≤ n, k ≥ 1}, a nonzero target t ∈ P n and 0 < < 1.

Output: Find a subset S ⊆ S whose vector sum t = v i , v i ∈ S that minimize dist(t, t ).

We consider the Euclidean distance l 2 here, but our method is easily generalized to any l p , 1 ≤ p < ∞. For more details see Theorem 8.22 in [? ]. Definition 6. A PTAS (Polynomial Time Approximation Scheme) is an algorithm, which takes an instance of an optimization problem, a parameter > 0 and in polynomial time produces a solution, that is within a factor 1 + of being optimal for minimization problems or 1for maximization problems.

We further recall the classes EPTAS (Efficient PTAS), where time complexity is polynomial in the input size (but can have any dependence on ) and FPTAS (Fully PTAS), where the time complexity is polynomial in both input size and the parameter . The class APX contains every problem that can be approximated within a constant factor c.

Previous work 1D-SS and kD-SS are not strongly NP-complete and can be solved exactly in pseudo-polynomial time: 1D-SS is solved in O(n|t|), see [? ]. Generalizing this idea kD-SS is solved in O(n|M | k ), where M = max P n is the farthest reachable point. Moreover, 1D-SS is in FPTAS, see [? ]. A related problem is the Multidimensional Knapsack. Firstly, it was proved in [? ], that this problem does not have an FPTAS. Later in [? ], does not have an EPTAS, while Knapsack is in FPTAS. 1D-SS is a special case of Knapsack as both are defined as maximization problems. In two or higher dimension, it makes more sense to define kD-SS as a minimization problem, since a vector sum with maximum length may be far from the target vector. So, in dimension two or higher, the problem is not related to Multidimensional Kanspack but rather to CVP.

A closely connected problem to kD-SS is the Closest Vector Problem (CVP): we are given a set of basis vectors B = {b 1 , . . . , b n }, where b i ∈ Z k , and a target vector t ∈ Z k , and we ask what is the closest vector to t in the lattice L(B) generated by B. This is

L(B) = { m i=1 a i b i | a i ∈ Z} and
thus kD-SS is a special case of CVP, where a i ∈ {0, 1}. CVP is not in APX and cannot even be approximated within a factor of

2 log 1-n with = (log(log n)) c for c < 1/2 [? ? ].
MinkDecomp has its fair share of attention. One application is in the factorization of bivariate polynomials through their Newton polygons. As noticed by Ostrowski in 1921, if a polynomial factors, then its Newton polygon has a Minkowski decomposition. An algorithm for polynomial irreducibility testing using MinkDecomp is presented in [? ] motivated by previous similar work in [? ]. They present a criterion for MinkDecomp that reduces the decision problem into a linear programming question. Continuing the work of [? , sections 4,5] we propose a polynomial time algorithm, that solves MinkDecomp approximately using a solver for 2D-SS. Here, we are interested in finding approximate solutions. We will discuss these problems in ??. MinkDecomp is NP-complete for lattice polygons, and a pseudopolynomial algorithm exists [? ].

Our contribution We introduce the kD-SS problem. It is clearly NPcomplete; we prove that it cannot be approximated efficiently. For k ≥ 2 it cannot be approximated within a constant factor (although the classic 1D-SS has a FPTAS). We design an algorithm for 2D-SS-approx: given a set S, |S| = n, target t and 0 < < 1, the algorithm returns, in O(n 3 -2 ) time, a subset of S whose vectors sum to t such that dist(t, t ) ≤ M , where M = max P n . We also describe two more approximation algorithms with a better experimental ratio.

Applying one of these algorithms yields an approximation algorithm for MinkDecomp (??): If Q is the input polygon the algorithm returns polygons A and B whose Minkowski sum defines polygon

Q such that vol(Q) ≤ vol(Q ) ≤ vol(Q) + D 2 , per(Q) ≤ per(Q ) ≤ per(Q) + 2 D, i(Q) ≤ i(Q ) ≤ i(Q) + D 2 , where D is the diameter of Q. The Hausdorff distance of Q and Q is bounded by d H (Q, Q ) ≤ /2D.

kD-SS is not in APX

To prove that kD-SS-opt is not in APX we will apply the idea used to prove that CVP is not in APX, see [? ] for more details. We apply their proof to our problem, in order to prove something similar for the kD-SS-opt.

Proposition 7.

[? ] For every c > 1 there is a polynomial time reduction that, given an instance φ of SAT, produces an instance of Set Cover {U, (S 1 , . . . , S m )} where U is the input set of integers and S 1 , . . . , S m are subsets of U, and integer K with the following property: If φ is satisfiable, there is an exact cover of size K, otherwise all set covers have size more than cK.

Given a CNF formula φ we invoke ?? and get an instance of the Set Cover problem. This is a gap introducing reduction, because if φ is statisfiable then the instance of Set Cover has a solution of size exactly K and if φ is not statisfiable every solution has size at least cK for a constant c. From this instance of Set Cover we create an instance for kD-SS that preserves the gap. Now, if φ is satisfiable, the closest vector to a given target t has distance exactly K. If φ is not statisfiable, the closest vector in target t has distance at least cK.

We reduce kD-SS to Set Cover for norm l 1 , but this can easily be generalized to any l p , where p is a positive integer. We say that a cover is exact if the sets in the cover are pairwise disjoint.

Theorem 8. Given a CNF formula φ and c > 1 we create an instance {v 1 , . . . , v m ; t} of kD-SS. If φ is satisfiable, then the minimum distance of a possible vector sum from t is smaller than K otherwise, it is larger than cK.

Proof. Let {U, (S 1 , . . . , S m ), K} be the instance of Set-Cover obtained in Proposition ?? for the formula φ. We transform it to an instance of kD-SS with input set {v 1 , . . . , v m } and target t, such that the distance of t from the nearest point in the set of all possible points P n is either K or ≥ cK.

Let v i ∈ Z n+m , where |U| = n. We will create such a vector v i for every set S i ; 1 ≤ i ≤ m. Let L = cK. Then the first n coordinates of each vector v i have their j'th-coordinate (j ≤ n) equal to L if the corresponding j'th-element belongs to set S i , or 0 otherwise. The remaining m coordinates have 1 in the (n + i)'th-coordinate and zeros everywhere else:

v i = (L • χ Si , 0, . . . , 1, . . . 0) = (L • χ Si , e i ),
where χ Si is the characteristic function of the set S i . The target vector t has in the first n coordinates L and the last m coordinates are zeros, t = (L, . . . , L, 0, . . . , 0). Now, let the instance of Set-Cover have an exact cover of size K. We will prove that the minimum distance of every v ∈ P n from target t is less than K. Without loss of generality, let the solution be {S 1 , . . . , S K }. For each S i , 1 ≤ i ≤ K, sum the corresponding vectors v i and let this sum be ζ ∈ Z n+m :

ζ = K i=1 v i = (L, . . . , L, n 1, . . . , 1 K 0, . . . , 0 m-K ).
The first n coordinates must sum up to (L, L . . . , L), because if one of the coordinates was 0, the solution would not be a cover and if one of them was greater than L, then some element is covered more than once and the solution would not be exact. Note that each of the first n coordinates is either 0 or greater than L. The key point is that in the last m coordinates we will have exactly K units and everything else 0. The distance of this vector ζ from t is

-t + ζ 1 = (0, . . . , 0, n 1, . . . , 1 K 0, . . . , 0 m-K ) 1 = K
Thus, there is a point in P n that its distance from t is at most K.

Let us consider the other direction, where the Set Cover instance has a solution set greater than cK = L. We will show that the closest vector to t has distance at least L from t. This solution must have at least cK = L sets. As before,t + ζ 1 ≥ L (this time the cover need not be exact).

Towards a contradiction, suppose there exists a vector ξ such thatt + ξ 1 < L. If the corresponding sets do not form a cover of S then one of the first n coordinates of ξ is 0 and this alone is enough fort + ξ 1 > L. If the sets form a cover that is not exact, then in at least one of the first n coordinates of ξ will be greater than L (for the element that is covered more than once) and will forcet + ξ 1 to be greater than L. Finally, if the sets form an exact cover, the first n coordinates oft + ξ 1 will be 0. For the distance to be less than L, in the last m coordinates there must be less than L units implying that the sets in the cover are less than L contradicting our hypothesis.

In all cases, there cannot exist a vector whose distance from t is < cK.

Theorem 9. There is no APX for kD-SS-approx unless P=NP.

Proof. Let φ be a given formula as an instance of SAT. Use ?? to get an instance of Set Cover and then the reduction from ?? to get an instance of kD-SS. Suppose there exists an algorithm A for kD-SS-opt that is in APX. A returns a vector t such that tt 1 ≤ (1 + )OP T , where OP T = tt * 1 and t * is the closest vector in P n . From ??, if φ is satisfiable then OP T ≤ K and if φ is not satisfiable OP T > cK.

We must run algorithm A with a suitable parameter so we can distinguish if the optimum solution t * is within distance K or not. When φ is satisfiable we would want (1 + )K < cK =⇒ < c -1. Set c < c -1, call A with parameter = c and let t be the returned vector. In the case where φ is satisfiable and

OP T ≤ K we have t -t 1 ≤ (1 + )OP T < cK
Of course if φ is not satisfiable for any t we have that tt 1 > cK. Thus, tt 1 < cK if and only if φ is satisfiable. Since is a constant and A is in APX we can decide SAT in polynomial time.

Although there can be no algorithm that returns a constant factor approximation solution for general dimension k, we will present algorithms that provide different kind of approximation. Specifically, the returned vector t of our algorithm is an (OP T + M ) solution, where M = max P n is the longest possible vector sum.

Three approximation algorithms for 2D-SS

annulus-slice algorithm

The idea here is to create all possible vectors step by step. At each step, if two vectors are close to each other, one is deleted. Whenever we refer to distance it is the Euclidean distance. We begin with some notation.

• Input: the set S = {v 1 , v 2 , . . . , v n } with v i = (x i , y i ) ∈ Z 2 and |S| = n, parameter 0 < < 1. a) δ|v| δ|v| δ|v| αδ|v| v b) c)
Figure 1: a) A single cell for the dashed vector v. All vectors in the cell will be deleted. The distances are shown and the furthest point is in distance αδ|v|. b) How space is divided. c) A few cells. The shorter the vector the smaller the cell.

• P i is the set of all possible vectors that can be produced by adding at most i elements from the first i vectors in S. P n is the set of all possible vector sums.

• E i = L i-1 ∪ {w + v i | w ∈ L i-1
} is the list created at the beginning of every step and that is about to get trimmed.

• L i = trim(E i , δ) is the trimmed list and 0 ≤ δ ≤ 1.

At the beginning of the i-th step we create the list

E i = L i-1 ∪ {w + v i | w ∈ L i-1 }.
Notice that addition is over Z 2 . After a point is found we calculate its length, sort E i based on the lengths and call trim(E i , /2n). For each vector u ∈ E i with length |u| and angle θ(u) from the x-axis, check all the vectors

u ∈ E i that have length |u| ≤ |u | ≤ (1+δ)|u|. If also θ(u)-δ ≤ θ(u ) ≤ θ(u)+δ, remove u from E i .
The remaining trimmed list is the list L i . The two conditions ensure that dist(u , u) ≤ αδ|u|, where 1 ≤ α ≤ 2 is a constant. Every vector that is deleted from E i is not very far away from a vector in L i :

∀u ∈ E i , ∃w ∈ L i : u = w + r w , |r w | ≤ αδ|w| (1) hence, |w| ≤ |u| ≤ (1 + δ)|w|. See ??.
Since all vectors have integer coordinates, any vector u ∈ E i such that |u| < 1/αδ < √ 2n/ implies that αδ|u| < 1. Thus, the area around u does not contain any other other lattice points except u.

Lemma 10. Using the above notation, call function L i =trim(E i , δ), with parameter δ = /2n and let M i = max{|u| : u ∈ E i }, the vector in E i with the largest length. It holds that

|L i | = O(n 2 -2 log M n ) for 1 ≤ i ≤ n.
Proof. Every vector in E i has length between (1 + δ) k and (1 + δ) k+1 . These are circles with center (0, 0) and radius (1 + δ), (1 + δ) 2 , . . . , (1 + δ) k for some k. Every two successive circles form an annulus that we call it a zone. We must cover all u ∈ P n and k is the minimum such that

(1 + δ) k > M n . Solving (1 + δ) k ≥ M n for k, there are O(n log M n / ) = O(n 2 / ) many zones that can be created.
Every zone is divided into cells. Each cell is taken in such a way that it will cover 2δR of the inner circle of the zone, where R is the radius of this circle (??a). Thus, every zone between the circles with radious R and (1 + δ)R has at most 2πR/δR = 4πn/ cells.

Since a list L i has at most an entry for every cell created in every zone, its size can be at most

(n 2 / ) • (4πn/ ) = O(n 3 -2 ).
For function trim, the time required is |E i | to consider all vectors and, in the worst case, we have to check each vector in E i with all the others leading to a running time of

O(|E i | 2 ) = O(|L i | 2 ). The running time for ?? is n • T (trim) = O(n|L n | 2
) and overall, from ??, it requires time O(n 5 -4 log 2 M n ). The algorithm only stores at each step the list L i so the space consumption is O(n 2 -2 log M n ).

Corollary 11. For δ = /2n the running time of

?? is O(n 5 -4 log 2 M n ) and space required is O(n 2 -2 log M n ). Algorithm 1: trim input : E ⊂ Z 2 , 0 ≤ δ ≤ 1 output: a trimmed list L sort(E) for v k ∈ E do i = 1 while |v k+i | ≤ (1 + δ)|v k | do if θ(v k+i ) -δ ≤ θ(v k ) ≤ θ(v k+i ) + δ then remove v k+i from E i = i + 1 return E Theorem 12. For a set of vectors S = {v i | v i ∈ Z 2 , 0 ≤ i ≤ n},
every possible vector sum v ∈ P n can be approximated by a vector w such that

∀v ∈ P n , ∃w ∈ L n , ∃r w ∈ Z 2 : v = w + r w , |r w | ≤ nδM n ,
Proof. The proof is by induction. The base step, it is easy to see that if we only have one element the theorem holds. The induction hypothesis

∀v ∈ P n-1 , ∃w ∈ L n-1 , ∃r w : v = w + r w , |r w | ≤ (n -1)δM n-1 . Algorithm 2: approx-2D-SS input : S ⊂ Z 2 , 0 ≤ ≤ 1 output: all approximation points L n L 0 =∅ for v i ∈ S do E i = L i-1 ∪ {L i-1 + v i } L i = trim(E i , /2n) return L n
Now suppose v ∈ P n \ P n-1 , because if v ∈ P n-1 the theorem holds straight from the induction hypothesis. We write v as v = z + v n , z ∈ P n-1 and the induction hypothesis holds for z, thus

∃p ∈ L n-1 , ∃r p : z = p + r p , |r p | ≤ (n -1)δM n-1 .
(2)

Since p ∈ L n-1 this means that p + v n ∈ E n and L n = trim(E n ). From the guarantee of function trim we know that ∃q ∈ L n : p + v n = q + r q , |r q | ≤ δ|q|.

(3)

From ???? we get v = z + v n = p + v n + r p = q + r q + r p . This proves that for v ∈ P n there exists a vector q ∈ L n that approximates it; but how close are they? We will bound the length |r q + r p |. From ????,

|r p | ≤ (n -1)δ max{L n-1 } ≤ (n -1)δM n |r q | ≤ δ|q|, q ∈ L n =⇒ |r q | ≤ δM n Thus |r q + r p | ≤ |r q | + |r p | ≤ (n -1)δM n + δM n ≤ nδM n .
Setting δ = /2n we can ensure that every possible vector sum will be approximated by a vector in L n at most M n far. Implementing and testing the algorithm, much better bounds are obtained, see ??.

A grid based algorithm

Our input is a list of vector S = {v i | v i ∈ Z 2 , i ≤ n}. We define the list

E i = L i-1 ∪ {w + v i | w ∈ L i-1 }
and at each step i we trim it by a parameter δ to get the trimmed list L i = trim(E i , δ). Also, P i is the set of all possible vector sums using a subset of the first i vectors of S,

P i = { i j a j v j | a j ∈ {0, 1}, v j ∈ S}.
It turns out that the same approximation ratio M n can be achieved by a faster algorithm that separates the plane into a grid, where M n is the length of the largest vector in E i . Instead of creating this different annulus-slice cells we have a regular orthogonal grid where each square cell has side d = M n /2n. Many thanks to Günter Rote for the fruitful conversation.

Let the cell side length be d = M n /2n, and for each v(x, y) ∈ E i store in the trimmed list L i the vector with its coordinates rounded in the integer multiple of d: The whole grid has size 2M n and since d = M n /2n the grid has O((M n /d) 2 ) = O((n/ ) 2 ) cells. In the worst case we will have a vector in every cell and this means that the time to traverse the lists E i at each step is O(n 2 -2 ). Since we have n lists the total running time of the new algorithm is O(n 3 -2 ) and the space requirements are O(n 2 -2 ).

∀v(x, y) ∈ E i ∃w(x , y ) ∈ L i : x = x d , y = y d w M t OP T ∈ P n w ∈ L n
Also, every u ∈ P n is the sum of at most n vectors from S. In the worst case, every time we call trim, we represent a vector u ∈ E i by another one that has distance form u at most d. In that case we lost at most nd = M n :

∀v ∈ P n ∃w ∈ L n : dist(v, w) ≤ M n .
Thus, for every given target vector t the algorithm will return an approximation solution that is nd = M n far from being optimum ??.

Corollary 13. The grid-based algorithm runs in time O(n 3 -2 ), requires space O(n 2 -2 ) and returns a solution t such that dist(t, t ) ≤ OP T + M n In 2D case there is a factor √ 2 that we also omit it from our approximation. This happens because the maximum distance inside a cell is not d but √ 2d. For dimension k the minimum distance is √ kd and this affects the algorithm in higher dimension.

A heuristic method

The grid-based algorithm "cuts" a constant d from every factor regardless of its length. If a vector has length 10,10 3 or 10 5 , the algorithm will behave the same. On the other hand, it is fast, because it does not have to check any other vector; for every vector it sees it rounds it on the spot, thus having linear time in the size of the lists. We can make a version of a circular grid, where each cell does not have a constant side length. For small vectors we create smaller cells and as the length increases so does the cell side. This way we can provide a better experimental approximation ratio. At step i we have the list E i and we will trim it with a factor δ. We will consider the polar coordinates of the vectors. For a vector v(φ, r) let φ = θ(v) be the angle with the x axis and r = |v| its euclidean length. Let v be a vector in E i and, to get the list L i , we will replace v by v = (φ , r ). First round its angle in multiple of δ : φ = φ/δ . Next, we round its length. The idea is to round in such a way that shorter vectors are approximated better than the longer ones. Rounding to a multiple of some d does not provide that. For rounding the lengths we will construct an array A with all the acceptable rounded lengths. The entries of A are the lengths [1, (1 + δ), . . . , (1 + δ) i ] for the minimum i such that (1 + δ) i > M n . Solving this inequality we get that i = O(n log M n / ) and this is the size of A. Now, for a vector v we just make a binary search in A for |v| that returns the zone such that

(1 + δ) k ≤ |v| ≤ (1 + δ) k+1 and r = bin_search(A, |v|) = (1 + δ) k . The space is divided in O(δ) = O(n/ ) angles and O(n log M n / ) different lengths. Each E i has size O(n 2 -2 log M n );
we save the quadratic factor, but add a log |E i | for the binary search. The whole algorithm runs in time

O(n|E i | log |E i |) = O(n 3 -2 log M n log n 2 log M n 2 )
and provides the same approximation, since ∀v ∈ E i , ∃w ∈ Li : dist(v, w) ≤ |w| as before. We believe that the better behaviour of this algorithm can be suited for an average case analysis, that will prove that the algorithm provides a better approximation ratio for the majority of v ∈ P n . Also, the binary search may be dropped by using a method to round the lengths in O(1) time, dropping this way the log |E i | factor.

Minkowski Decomposition using 2D-SS

In this section, we will describe an algorithm for approximating MinkDecomp. The algorithm takes an input polygon Q, transforms it to an instance {S, t} of 2D-SS-approx and calls the algorithm for 2D-SS-approx. Then it takes the output and converts it to an approximate solution to MinkDecomp.

Let Q be the input to MinkDecomp:

Q = {v i | v i ∈ Z 2 , 0 ≤ i ≤ n}, such that n 1 v i = (0, 0)
. First, we create the vector set s(Q) by subtracting successive vertices of Q (in clockwise order):

s(Q) = {v 0 -v 1 , v 1 -v 2 , . . . , v n -v 0 }. Each vector in s(Q)
is called an edge vector and s(Q) is called the edge sequence of Q. For each edge vector in s(Q) we calculate its primitive vector. We get an edge vector (x, y) ∈ s(Q) and calculate its primitive vector e = (x/d, y/d), where d = gcd(x, y). We could create the set S by adding in it d times the vector e for every v ∈ s(Q) but this may create a set S that has exponential size to the edges of the polygon. Instead, we computer the scalars d 1 , . . . , d k by the following formulas

(Q) s(Q) s(A) s(A) s(B) s(B) Q Q v v Q = Q + v Q = Q + v v v v v
d i = 2 i , i = 0, . . . , log 2 d/2 and d k = d - log 2 d/2 i=1 d i
We create the set S from the vectors d i e and repeat the procedure for all vectors v ∈ s(Q). Notice that k 1 d i = d, so the primitive edge sequence also sums to (0, 0). Using this construction, the primitive vectors added are at most log d for every v ∈ s(Q) keeping the size of S polynomial with respect to the edges of Q. The primitive edge sequence uniquely identifies the polygon up to translation determined by v 0 . This is a standard procedure as in [? ? ].

The main defect in this approach is that the algorithm returns a sequence of vectors S ⊂ S that sum close to (0, 0) but possibly not (0, 0). This means the corresponding edge sequence does not form a closed polygon. To overcome this, we just add to s(A) the vector v, from the last point to the first, to close the gap. If s(A) sums to a point (a, b), by adding vector v = (-a, -b) to s(A) the edge sequence s(A)∪{v} now sums to (0, 0). If we rearrange the vectors by their angles, they form a closed, convex polygon that is summand A. We do the same for the sequence s(B). The vector added in s(B) is -v = (a, b) and this sequence (rearranged) also forms a closed, convex polygon. We name s(A ) = s(A) ∪ {v}, s(B ) = s(B) ∪ {v} and take their Minkowski Sum Q = A + B , where A and B are the convex polygons formed by s(A ) and s(B ). We measure how close Q is to the input Q. Let D be the diameter of Q, the maximum distance between two vertices of Q.

Lemma 15. Let Q be the input polygon and Q be the polygon as discussed above. vol stands for volume. per for perimeter, i are the interior lattice points of a polygon and d H the Huasdorff distance. We deduce that 3

v s(Q) s(A) s(B) -v D D v Q = Q + v
. i(Q) ≤ i(Q ) ≤ i(Q) + D 2 4. d H (Q, Q ) ≤ /2D
Proof. We observe that

s(Q ) = s(A ) ∪ s(B ) = s(A) ∪ s(B) ∪ {v} ∪ {} ∪ {-v} =⇒ s(Q ) = s(Q) ∪ {v} ∪ {} ∪ {-v}.
This equals adding to Q a single segment s of length |s| = |v| and Q = Q + s.

The length of vector v we add to close the gap, is the key factor to bound polygon Q . From the guarantee of the 2D-SS-approx algorithm we know that s(A) (and respectively s(B)) sum to a vector with length at most max{L n }. This is vector v and thus |v| ≤ max{L n }. Since max{L n } ≤ D, we get |s| = |v| ≤ D.

From above we easily see that:

1. per(Q) = v∈s(Q) |v|, it follows per(Q ) = per(Q) + 2|v| ≤ per(Q) + 2 D. 2. vol(Q ) ≤ vol(Q) + sD ≤ vol(Q) + D 2 3. By Pick's theorem, vol(Q) = i(Q) + b(Q)/2 -1 =⇒ i(Q) = vol(Q) - b(Q)/2 + 1. Note that b(Q) = ∀v∈s(Q) d v where v = (x, y) ∈ s(Q) and d v = gcd(x, y) as is ??. Now, i(Q ) = i(Q) + i(sD) since sD is the maximum volume added and i(sD) ≤ sD -b(sD)/2 + 1 ≤ sD -1 ≤ D 2 . Thus, i(Q ) ≤ i(Q) + D 2 4. If we "slide" Q by s/2 units in the direction of v, d H (Q, Q ) = s/2 =⇒ d H (Q, Q ) ≤ /2D
A bad example can be seen in ??, where the added vector is (almost) perpendicular to D maximizing the extra volume and internal lattice points. ?? leads to following conclusion:

Implementation and experimental results.

We implement both ???? in Python3. The code can be accessed through Github1 and is roughly 750 lines long. We provide methods for either 2D-SSapprox or MinkDecomp-µ-approx. To test ?? we created vectors v i at random with |v i | ≤ 5000. For ?? we create random points and take their convex hull to form input polygon Q. All tests were executed in an Intel Core i5-2320 @ 3.00 GHz with 8Gb RAM, 64-bit Ubuntu GNU/Linux. Results for ?? are shown in ?? and for algorithm ?? in ??. It is clear in ?? that our results stay below the expected time and behave analogously. In ?? the results obtained are much better than the proven bounds and in most cases volume and perimeter are almost the same and the polygons differ slightly.

Further work

In this work we presented some theoretical results concerning the approximation of two NP-hard problems: kD-SS and Minkdecomp. Additionally, we provide polynomial time approximation algorithms to solve these problems. next step is to associate these ideas with certain algebraic problems like approximate polynomial factoring or irreducibility testing. Given a polynomial f Q and its Newton polygon Q, we use the MimkDecomp approximation algorithm to find an approximation decomposition Q = A + B . Using the irreducibility test in [? ], we either find a binary bivariate factorization or that f Q is irreducible. In the second case, we use the approximate polynomial factorization algorithm in [? ]. All monomials of f Q lie in the support of f Q therefore the corresponding coefficients should be same with the coefficients of these monomials in f Q . The new terms in f Q have coefficients, whose value is to be determined In other words, we need to determine, whether there exist valid coefficients for the monomials that correspond to lattice points in Q \ Q.

Figure 2 :

 2 Figure 2: For every t the returned vector is at most M from the optimum

  Definition 14. Let v = (a, b) be a vector and d = gcd(a, b). The primitive vector of v is e = (a/d, b/d).

  s

Figure 3 :

 3 Figure 3: Two examples for two polygons Q. Their summands are shown and the red vector v is the new vector added to fill the gap. At the end, the new polygon Q is Minkowski Sum of the two summands.

Figure 4 :

 4 Figure 4: A worst case example where the vector v is (almost) perpendicular to the diameter D maximizing the extra volume added. More, D and v have no lattice points thus the interior points added are also maximum (D is not vertical).

Corollary 16 .Figure 5 :

 165 Figure 5: Experimental results for 2D-SS-approx: a) = 0.2 and b) =0.30, c)n = 30 and d)n = 40. The blue line is the expected time, the red dots our experiments.

Table 1 :

 1 The #vertices #examples vol(Q)/vol(Q') per(Q)-per(Q') Hausdorff Input polygon Q, output Q (per(Q) > 1000).Gather examples by the number of their vertices. We measure volume, perimeter and Hausdorff distance and present their mean values.

	time(secs)

vol(Q) ≤ vol(Q ) ≤ vol(Q) + D 2

per(Q) ≤ per(Q ) ≤ per(Q) + 2 D

https://github.com/tzovas/Approximation-Subset-Sum-and-Minkowski-Decomposition

partially supported by H2020 M. Sklodowska


Jean-Christophe Mourrat

Felix Otto

ANCHORED NASH INEQUALITIES AND HEAT KERNEL BOUNDS FOR STATIC AND DYNAMIC DEGENERATE ENVIRONMENTS

Keywords: MSC 2010: 26D10, 35K65, 35B65, 60K37 Nash inequality, heat kernel, diffusion in dynamic random medium

We introduce anchored versions of the Nash inequality. They allow to control the L 2 norm of a function by Dirichlet forms that are not uniformly elliptic. We then use them to provide heat kernel upper bounds for diffusions in degenerate static and dynamic random environments. As an example, we apply our results to the case of a random walk with degenerate jump rates that depend on an underlying exclusion process at equilibrium.

Introduction

In the study of reversible random walks in degenerate static random environments, heat kernel estimates have played a key role. Consider a random walk evolving on a super-critical (infinite) percolation cluster. As was pointed out in [START_REF] Sidoravicius | Quenched invariance principles for walks on clusters of percolation or among random conductances[END_REF], the problem of showing that the walk satisfies a central limit theorem for almost every realisation of the environment (i.e. a "quenched" CLT) is reduced to showing a spatially averaged (instead of uniform) sublinear control of the corrector if the heat kernel is known to satisfy a diffusive upper bound. For the case of percolation, such a bound was obtained in [START_REF] Mathieu | Isoperimetry and heat kernel decay on percolation clusters[END_REF][START_REF] Barlow | Random walks on supercritical percolation clusters[END_REF]. This bound indeed became a primary ingredient in the subsequent proofs that the random walk on percolation clusters and other degenerate i.i.d. environments satisfies a quenched central limit theorem [START_REF] Sidoravicius | Quenched invariance principles for walks on clusters of percolation or among random conductances[END_REF][START_REF] Berger | Quenched invariance principle for simple random walk on percolation clusters[END_REF][START_REF] Mathieu | Quenched invariance principles for random walks on percolation clusters[END_REF][START_REF] Biskup | Functional CLT for random walk among bounded random conductances[END_REF][START_REF] Mathieu | Quenched invariance principles for random walks with random conductances[END_REF][START_REF] Andres | Invariance principle for the random conductance model[END_REF]. (A notable exception is a geometric argument introduced in [START_REF] Berger | Quenched invariance principle for simple random walk on percolation clusters[END_REF], which in two dimensions does not use any a priori heat kernel bounds.) We refer to [START_REF] Biskup | Recent progress on the random conductance model[END_REF] (in particular, Section 4.3 therein) and [START_REF] Kumagai | Random walks on disordered media and their scaling limits[END_REF] for reviews. Related ideas of regularity theory lead to a proof of the local central limit theorem in [START_REF] Barlow | Parabolic Harnack inequality and local limit theorem for percolation clusters[END_REF].

The approach to heat kernel bounds in [START_REF] Mathieu | Isoperimetry and heat kernel decay on percolation clusters[END_REF] is based on studying isoperimetric inequalities on boxes, with an effective dimension that is slowly tuned up to d as the size of the box increases. In [START_REF] Barlow | Random walks on supercritical percolation clusters[END_REF], upper and lower bounds are proved (including optimal off-diagonal control) using a fine decomposition of the space into good and bad boxes, where a box is said to be good if the Poincaré inequality (with the standard scaling) holds in that box. The case of i.i.d. conductances with a polynomial tail near zero is investigated in [START_REF] Boukhadra | Harnack inequalities and local central limit theorem for the polynomial lower tail random conductance model[END_REF] using a combination of probabilistic arguments and Harnack inequalities.

One can also consider environments that do not possess strong decorrelation properties at large distances. Assuming a certain moment condition (from above and below) on the conductances, it was shown in [START_REF] Andres | Invariance principle for the random conductance model in a degenerate ergodic environment[END_REF] that the random walk satisfies a quenched central limit theorem. The proof relies on weighted Sobolev inequalities, and on Moser's iteration scheme. Harnack inequalities and a local CLT were then established in [START_REF] Andres | Harnack inequalities on weighted graphs and some applications to the random conductance model[END_REF], and Gaussian heat kernel bounds in [START_REF] Andres | Heat kernel estimates for random walks with degenerate weights[END_REF]. Related ideas were developped in [START_REF] Fannjiang | A martingale approach to homogenization of unbounded random flows[END_REF] to prove a quenched invariance principle for Brownian motion subject to an incompressible drift. In a different direction, diffusions on clusters of correlated percolation models such as random interlacements are studied in [START_REF] Procaccia | Quenched invariance principle for simple random walk on clusters in correlated percolation models[END_REF] via isoperimetric inequalities. Some assumptions on the law of the conductivities are necessary for diffusive heat kernel bounds to hold. Indeed, even in the setting of i.i.d. conductances, where the quenched CLT is known to hold in full generality [START_REF] Biskup | Functional CLT for random walk among bounded random conductances[END_REF][START_REF] Mathieu | Quenched invariance principles for random walks with random conductances[END_REF][START_REF] Andres | Invariance principle for the random conductance model[END_REF], diffusive heat kernel upper bounds will not hold if the conductivities are allowed to take very small values [START_REF] Berger | Anomalous heat-kernel decay for random walk among bounded random conductances[END_REF]. The basic mechanism is that a portion of space surrounded by a region of low conductivity acts as a trap for the random walk. This phenomenon was analysed with precision in [START_REF] Boukhadra | Heat-kernel estimates for random walk among random conductances with heavy tail[END_REF][START_REF] Biskup | Subdiffusive heat-kernel decay in four-dimensional i.i.d. random conductance models[END_REF][START_REF] Biskup | Trapping in the random conductance model[END_REF].

The aim of this work is to introduce a new method to prove diffusive heat kernel bounds for degenerate environments. In a celebrated work [START_REF] Nash | Continuity of solutions of parabolic and elliptic equations[END_REF], Nash introduced the inequality that now bears his name for this purpose, for uniformly elliptic differential operators. This was then extended to the setting of Markov chains in [START_REF] Carlen | Upper bounds for symmetric Markov transition functions[END_REF]. Our first main result, obtained in Section 2, is an anchored version of the Nash inequality. The standard Nash inequality gives a control of the L 2 norm of a function f in terms of ∇f 2 and f 1 . We show that one can control the L 2 norm of f in terms of w∇f 2 , f 1 and |x| p/2 f 2 , where w is a weight function that can for instance be taken to be the square root of the conductance field (in particular, it is not bounded away from 0 in cases of interest). Note that the translation invariance of the standard Nash inequality is broken by the term |x| p/2 f 2 .

We then show in Section 3 that despite this extra term |x| p/2 f 2 , one can obtain diffusive heat kernel upper bounds for static degenerate environments satisfying a certain flexible assumption. In particular, this assumption covers bounded stationary conductances with inverse having a moment of order p > d. When the conductances are independent, a moment of order p > 1/4 suffices. We thus recover certain results of [START_REF] Andres | Harnack inequalities on weighted graphs and some applications to the random conductance model[END_REF][START_REF] Boukhadra | Harnack inequalities and local central limit theorem for the polynomial lower tail random conductance model[END_REF]. We can also cover cases with vanishing conductances, see Remark 3.8. As a by-product of our method, we also obtain an estimate on the behaviour of the heat kernel away from the diagonal. Stronger information can be obtained from the on-diagonal bounds we prove using the result of [START_REF] Folz | Gaussian upper bounds for heat kernels of continuous time simple random walks[END_REF] recalled here in Theorem 3.5, which is itself inspired by [START_REF] Grigor Yan | Gaussian upper bounds for the heat kernel on arbitrary manifolds[END_REF] (see also [START_REF] Coulhon | The discrete integral maximum principle and its applications[END_REF][START_REF] Chen | Pointwise upper estimates for transition probability of continuous time random walks on graphs[END_REF]).

Our main motivation is to derive heat kernel bounds for dynamic degenerate random environments. We are not aware of previous results in this context, although quenched central limit theorems have been proved in some cases (see in particular [START_REF] Fannjiang | An invariance principle for diffusion in turbulence[END_REF]). The dynamics of the environment can facilitate anomalous behaviour of the heat kernel [START_REF] Buckley | Anomalous heat kernel behaviour for the dynamic random conductance model[END_REF]. As a simple example, one can construct a dynamic environment such that the probability of return to the origin decays from 1 to almost zero, and then climb back up to almost 1/4. Indeed, take z a neighbour of the origin, and consider that initially, the edge connecting the origin to z is open, and these two sites are disconnected from the rest of the graph. The probability for the walk to be on z goes to 1/2 as time passes. Then change the environment so that the site z is isolated from the rest, and otherwise every edge is open. The probability for the walk to be at the origin decays to 0. Then move back to the initial situation with the origin and z connected, and disconnected from the rest: the probability for the walk to be at the origin moves back to being almost 1/4.

Let us denote by p s,t (x, y) the probability for the walk started at x at time s to be at y at time t s. It is more convenient to aim first for bounds on

E t := x∈Z d (p 0,t (0, x)) 2 ,
in particular because, as opposed to p 0,t (0, 0), this quantity is monotone in t. In Section 4, we provide a general criterion that allows to prove diffusive bounds of the form 2 , where X is a random variable. In order to illustrate the relevance of our criterion, we study in Section 5 an example of a random walk whose (symmetric) jump rates (a t (e)) are a local function of an underlying simple exclusion process at equilibrium. We show that in this case, (1.1) holds with a random variable X that has finite moments of every order, regardless of the density of particles in the exclusion process, or of the specific definition of the jump rates. (In particular, it may be that at any given time, the set of sites that are reachable by the random walk is finite.) We also show that for every r 1, sup t E[(t d/2 p 0,t (0, 0)) r ] is finite, and that for every ε > 0, E[(sup t t d/2-ε p 0,t (0, 0)) r ] is also finite. In order for these results to hold, we need only little information on the underlying dynamics. Roughly speaking, we only use the fact that the jump rates are very unlikely to vanish over an extended period of time. In particular, we do not use the fact that the simple exclusion process has a polynomial mixing rate of order t -d/2 (as was shown in [START_REF] Bertini | Coercive inequalities for Kawasaki dynamics. The product case. Markov Process[END_REF][START_REF] Janvresse | Relaxation to equilibrium of conservative dynamics. I. Zero-range processes[END_REF]).

(1.1) E t X t d/
An immediate consequence of the diffusive heat kernel bound is the transience of the random walk in dimension d 3. This extends [36, Theorem 1.1 (ii)] to conservative (and therefore much less mixing) environments.

1.1. Notation. Throughout this paper, we focus on the discrete space Z d , d 1. We say that x, y ∈ Z d are neighbours, and write x ∼ y, if |x -y| = 1, where | • | is the Euclidean distance. This turns Z d into a graph, and we denote by B the associated set of (unoriented) edges. For any positive integer r, we denote by B r the box {-r, . . . , r} d , and B r the set of edges with both end-points in B r . For any p ∈ [1, ∞], we denote by • L p r the norm of the space L p (B r ) or L p (B r ) (which of the two will be clear from the context), i.e.

f L p r = x∈Br |f (x)| p 1/p or f L p r = e∈Br |f (e)| p 1/p
, with the usual interpretation as a supremum if p = ∞. We also write

f p =   x∈Z d |f (x)| p   1/p or f p = e∈B |f (

Anchored Nash inequality

The aim of this section is to prove the following theorem.

Theorem 2.1 (Anchored Nash inequality). Let p ∈ (d, +∞), q ∈ (d, +∞], and θ ∈ [θ c , 1], where θ c ∈ [0, 1) is defined by

(2.1) 1 θ c = 1 + dp + 2p dp + 2d q d -1 . Define α, β, γ ∈ [0, 1) by (2.2) α = (1 -θ) d d + 2 + θ p p + 2 , β = (1 -θ) 2 d + 2 , γ = θ 2 p + 2 .
There exists C < ∞ such that for any functions f :

Z d → R and w : B → R + , (2.3) f 2 C (M q w ∇f 2 ) α f β 1 |x| p/2 * f γ 2 ,
where

(2.4) M q q = M q q (w) = sup r∈N 1 |B r | e∈Br w -q (e).
Remark 2.2. By setting q = +∞ and θ = 0, we recover the usual Nash inequality, provided that M ∞ is finite (i.e. that w -1 is bounded). For θ > 0 (and thus γ > 0), the inequality is no longer translation invariant. Indeed, a crucial aspect of the inequality is that in the definition of M q , the supremum is taken only over boxes that are centred around the origin. The price one has to pay for this is the appearance of the extra term |x| p/2 * u γ 2 , which is of course not translation invariant either. Remark 2.3. Clearly, α + β + γ = 1, as must be the case by homogeneity.

Remark 2.4. Our proof applies as well to the setting of continuous space. Considerations of scale invariance then show that the exponents α, β and γ have to be of the form (2.2) for some θ.

Remark 2.5. As far as our applications are concerned, the precise value of θ c is unimportant, the only crucial point being that θ c < 1.

Before we turn to the proof of Theorem 2.1, we recall some classical functional inequalities for the reader's convenience. Theorem 2.6 (Poincaré-Sobolev inequalities). Let 1 < p < d and let p be such that d/p = d/p -1. There exists a constant C < ∞ such that for every r and f : B r → R,

(2.5) f -f r L p r C ∇f L p r
, where we write

f r = 1 |B r | x∈Br f (x).
Proof. For every x, y ∈ B r , we give ourselves a path γ x,y of nearest-neighbour points of Z d from x to y that stays as close as possible to the segment joining x and y. To be precise, by symmetry we may assume that y x (i.e. each coordinate of y is larger than the corresponding coordinate of x). In this case, we construct a path x 0 = x, x 1 , . . . , x l = y as follows. We write I x,y for the line segment joining x and y in R d . Assuming that x 0 , . . . , x j are already built, we define i = arg min{dist(x j + e i , I x,y ), 1 i d},

(take the smallest one in case of ties), and put x j+1 = x j + e i . Such a path stays at distance at most √ d from I x,y , and has no self-intersections. We have

|f (y) -f (x)| e∈γx,y |∇f |(e),
with obvious notation. Since

(2.6) f (x) -f r = 1 |B r | y∈Br (f (x) -f (y)), the triangle inequality yields f (x) -f r 1 |B r | y∈Br e∈γx,y |∇f |(e).
One can check that there exists a constant C (independent of r) such that for every x ∈ B r and e ∈ B,

|{y ∈ B r : e ∈ γ x,y }| Cr r 1 + |x -e| d-1 . As a consequence, (2.7) f (x) -f r e∈Br (1 + |x -e|) -(d-1) |∇f |(e).
The desired result now follows from the Hardy-Littlewood-Sobolev inequality, see e.g. [6, Theorems 1.5 and 1.7].

Remark 2.7. Theorem 2.6 can be generalised in the following way. Under the same conditions, if g :

B r → R is such that g r = 1, then f -(f g) r L p r C g L ∞ r ∇f L p r . Indeed, it suffices to observe that (f g) r -f r = 1 |B r | x∈Br g(x) f (x) -f r g L ∞ r 1 |B r | 1/p f -f r L p r ,
and to use the triangle inequality and Theorem 2.6 (with g L ∞ r 1).

In dimension 2, we will also need to use inequality (2.5) in the critical case p = 2, p = 1. The following theorem gives the result in any dimension.

Theorem 2.8 (Isoperimetric inequality). Let p = d/(d -1). There exists C < ∞ such that for every r and f

: B r → R, f -f r L p r C ∇f L 1 r . Proof. Let m be a median of f . It suffices to show that (2.8) f -m L p r C ∇f L 1 r . Indeed, if m > f r , then by the defining property of the median, |B r | 2 |{x ∈ B r : f (x) m}| 1 (m -f r ) p f -f r p L p r .
If m < f r , the symmetric argument shows that in every case,

|m -f r | 2 |B r | 1/p f -f r L p r .
By the triangle inequality, it thus suffices to show (2.8). Without loss of generality, we may assume that m = 0. Let g = f ∨ 0. Since |∇g| |∇f |, it suffices to show that (2.9)

g L p r C ∇g L 1 r (g s.t. |{x ∈ B r : g(x) = 0}| |B r |/2). For t 0, let L t = {x ∈ B r : g(x) > t}. Since g = ∞ 0 1 Lt dt, we have by Minkowski's inequality g L p r ∞ 0 |L t | 1/p dt.
The isoperimetric inequality [START_REF] Saloff-Coste | Lectures on finite Markov chains[END_REF]Theorem 3.3.15] ensures that there exists C < ∞ such that for every A ⊆ B r with |A| |B r |/2, we have |A| (d-1)/d C|∂A|, where

∂A = {e = {x, y} ∈ B r : x ∈ A and y / ∈ A}.
Hence,

g L p r C ∞ 0 |∂L t | dt = C ∞ 0 x∼y:g(x)<t g(y) 1 dt = C x∼y:g(x)<g(y) (g(y) -g(x)) = C ∇g L 1 r ,
which concludes the proof.

Remark 2.9. Under the conditions of Theorem 2.8, if g :

B r → R is such that g r = 1, then f -(f g) r L p r C g L ∞ r ∇f L 1 r . Indeed, the proof is identical to that of Remark 2.7.
Proof of Theorem 2.1. The proof will be divided into two steps. We show the result for θ = 1 in the first step, and for θ = θ c in the second step. The full result then follows by interpolation: it suffices to take ν ∈ [0, 1], write

f 2 = f ν 2 f 1-ν 2
and apply the result with θ = 1 and θ = θ c on each of the two terms.

Step 1. We show that the theorem holds for θ = 1. Let p be such that (2.10)

1 p = 1 d + 1 2 .
Let R be an even positive integer. We define a function g :

B R → R + that is 0 in B R/2
, and is constant on the complementary "annulus"

A R := B R \ B R/2 .
The constant is specified by imposing g R = 1. We use the Poincaré-Sobolev inequality in the form given by Remark 2.7 in dimension d 3, and the isoperimetric inequality in the form given by Remark 2.9 when d = 2, to derive

f -(f g) R L 2 R ∇f L p R .
In view of the definition of g, we have

(f g) R L 2 R |B R | -1/2 f L 1 (A R ) f L 2 (A R ) R -p/2 |x| p/2 * f L 2
R , where we used Jensen's inequality for the second inequality. By Hölder's inequality (and recalling (2.10)), we also have

∇f L p R w -1 L d R w∇f L 2
R . By Jensen's inequality (and since q d),

w -1 L d R |B R | 1/d-1/q w -1 L q R |B R | 1/d M q ,
with M q as in (2.4). We thus get

f L 2 R |B R | 1/d M q w∇f L 2 R + R -p/2 |x| p/2 * f L 2 R . Clearly, (2.11) f L 2 (Z d \B R ) R -p/2 |x| p/2 * f L 2 , so we established (2.12) f L 2 |B R | 1/d M q w∇f L 2 + R -p/2 |x| p/2 * f L 2
, uniformly over R even positive integer. It suffices to change the implicit multiplicative constant in (2.12) to ensure that the inequality

(2.13) f L 2 R M q w∇f L 2 + R -p/2 |x| p/2 * f L 2 remains valid for every real R 1. Since f L 2 |x| p/2 * f L 2
, the inequality extends to all R > 0. Optimizing over R, we obtain

f L 2 (M q w∇f L 2 ) p/(p+2) |x| p/2 * f 2/(p+2) L 2
, as desired.

Step 2. We now show that Theorem 2.1 holds for θ = θ c .

Let Q be a box of size r ∈ N, We use again p as in (2.10). By the Poincaré-Sobolev (or isoperimetric) inequality,

f -f Q L 2 (Q) ∇f L p (Q) ,
where we denote by f Q the average of f over the box Q. By (2.10) and Hölder's inequality, we have

∇f L p (Q) w -1 L d (Q) w∇f L 2 (Q) , while f Q L 2 (Q) |Q| -1/2 f L 1 (Q) , so that f L 2 (Q) w -1 L d (Q) w∇f L 2 (Q) + |Q| -1/2 f L 1 (Q) , and thus (2.14) f 2 L 2 (Q) w -1 2 L d (Q) w∇f 2 L 2 (Q) + |Q| -1 f 2 L 1 (Q) . Let R ∈ N, R r. By Jensen's inequality, |Q| -1/d w -1 L d (Q) |Q| -1/q w -1 L q (Q) . For Q ⊆ B R , w -1 L q (Q) w -1 L q R |B R | 1/q M q
, and we have (2.15) w -1

L d (Q) |Q| 1/d-1/q |B R | 1/q M q . If (Q i ) is a finite collection of pairwise disjoint boxes, then i f 2 L 1 (Q i ) f L 1 (∪Q i ) i f L 1 (Q i ) = f 2 L 1 (∪Q i ) .
We cover the box B R by sub-boxes (Q i ) of size r. We can do so in such a way that no point of B R is covered by more than 2 d sub-boxes, so that

i f 2 L 1 (Qi) f 2 L 1 R .
Combining this and (2.15) into (2.14) thus yields

f 2 L 2 R i f 2 L 2 (Qi) |Q| 2/d-2/q |B R | 2/q M 2 q w∇f 2 L 2 R + |Q| -1 f 2 L 1 R ,
where we now simply use |Q| to denote the cardinality of a box of size r, without reference to a specific box. Using (2.11) (and |Q| r), we obtain

f 2 L 2 |Q| 2/d-2/q |B R | 2/q M 2 q w∇f 2 L 2 + r -d f 2 L 1 + R -p |x| p/2 * f 2 L 2 .
By changing the implicit multiplicative constant in this inequality, we can ensure that (2.16)

f L 2 r 1-d q R d q M q w∇f L 2 + r -d/2 f L 1 + R -p/2 |x| p/2 * f L 2 holds uniformly over R r 1.
In view of (2.13), we can extend this to all R 1, r 1. Since we clearly have f L 2 f L 1 and f L 2 |x| p/2 * f L 2 , the inequality in fact holds for every R > 0 and r > 0. The conclusion will now follow by optimizing over R and r. We summarize this optimization into the following lemma, whose proof is postponed to the end of this section.

R a r a A + r -b B + R -c D 3A bc/σ B a c/σ D ab/σ .
In our context, we let

a = d q , a = 1 - d q , b = d 2 , c = p 2 ,
then σ = ab + a c + bc, and finally

α = bc σ , β = a c σ , γ = ab σ .
Applying Lemma 2.10 to (2.16) leads to (2.3). In order to check that α, β and γ can be rewritten as in (2.2) for some θ, we observe that

(d + 2)a c + (p + 2)ab = 2a c + 2ab + d 1 - d q p 2 + p d q d 2 = 2σ, so that (2.17) d + 2 2 β + p + 2 2 γ = 1.
This, together with the fact that α + β + γ = 1, ensures a representation of the form (2.2) for some θ. The value of θ can be recovered from

1 θ = 2 p + 2 1 γ = 2 p + 2 σ ab = 2 p + 2 1 + 2q d 2 1 - d q p 2 + dp 4 = 2 p + 2 1 + p 2 + p d + p 2 q d -1 ,
and we recognize that θ = θ c as defined by (2.1).

Proof of Lemma 2.10. It suffices to consider the case when none of A, B and D are zero. We simply choose r and R so that the contributions of the three terms in the sum to be minimized are equal, that is,

(2.18) R a r a A = r -b B = R -c D.
The second equality gives

R = D B 1/c r b/c ,
while by the first equality,

D B a/c r ab/c+a +b = B A .
This leads to

r σ = A -c B c+a D -a ,
and thus

r -b B = A bc/σ B 1-ab+bc σ D ab/σ ,
and the lemma follows by (2.18).

Static environments

We now show how to use the anchored Nash inequality derived in the previous section to deduce heat kernel bounds for static, degenerate environments. We begin by defining the notion of w-moderate static environment. Definition 3.1. Let w : B → R + . For a static environment a : B → [0, 1], we define p t (x, •) to be the unique bounded function such that p 0 (x, y) = 1 x=y and

∂ t p t (x, y) = z∼y a({y, z}) (p t (x, z) -p t (x, y)) .
In probabilistic terms, p t (x, y) is the probability for the random walk in the environment a started at x to be at y at time t. We write u t = p t (0, •) and

D t = √ a ∇u t 2 2
. We say that the static environment a is w-moderate if for every t 0, (3.1)

w ∇u t 2 2 D t .
Theorem 3.2 (Upper bound for static environments). For every q > d and every α, β, γ ∈ (0, 1) as in Theorem 2.1, there exists C < ∞ such that if the static environment a is w-moderate, then for every t 1,

p t (0, 0) C M 2α/β q t d/2
, where we recall that M q = M q (w) was defined in (2.4).

Before proving the theorem, we introduce some notation, and then prove an important preliminary result. For f :

Z d → R and x ∈ Z d , we define ∇ i f (x) = f (x + e i ) -f (x).
We observe that the following discrete Leibniz rule holds, for f, g :

Z d → R: ∇ i (f g) = (∇ i f )g + f (• + e i )∇ i g.
We write a i (x) = a(x, x + e i ).

Proposition 3.3. There exists

C < ∞ such that (3.2) d dt |x| p/2 * u t 2 2 C |x| p/2 * u t 2(p-2)/p 2 u t 4/p 2 .
Proof. The proof is similar to that of [25, (81)], with some extra care required by the fact that we do not assume uniform ellipticity here. We write ρ(x) = |x| * , and observe that 1 2

d dt |x| p/2 * u t 2 2 = 1 2 d dt x∈Z d ρ p u 2 t (x) = - e∈B ∇(ρ p u t )a∇u t (e) = - x∈Z d 1 i d ∇ i (ρ p u t )a i ∇ i u t (x).
By the discrete Leibniz rule, we have

∇ i (ρ p u t ) = ∇ i (ρ p )u t + ρ p (• + e i )∇ i u t ,
and moreover, ∇ i (ρ p )(x) ρ p-1 (x). As a consequence, the left-hand side of (3.2) is bounded by

x∈Z d 1 i d -ρ p (• + e i )a i |∇ i u t | 2 + Cρ p-1 u t a i |∇ i u t | (x)
for some constant C. Since a 1, we have a a 2 , so that by the Cauchy-Schwarz inequality,

x∈Z d 1 i d ρ p-1 u t a i |∇ i u t |(x) x∈Z d 1 i d ρ p a i |∇ i u t | 2 (x) 1/2 x∈Z d 1 i d ρ p-2 |u t | 2 (x) 1/2 .
Up to a multiplicative constant, we may replace ρ p by ρ p (• + e i ) in the middle sum above. By Young's inequality, the resulting expression is bounded by

1 2C x∈Z d 1 i d ρ p (• + e i )a i |∇ i u t | 2 (x) + C 2 x∈Z d 1 i d ρ p-2 |u t | 2 (x) ,
for arbitrary C > 0. By choosing C sufficiently large, we obtain that the left-hand side of (3.2) is bounded by a constant times Integrating (3.4) (and since N 0 = 1), we obtain, for every t 1/2, (3.5)

x∈Z d ρ p-2 |u t | 2 (x) (Hölder)   x∈Z d ρ p |u t | 2 (x)   p-2 p   x∈Z d |u t | 2 (x)   2
N t Λ t t (p-d)/2 .
For α, β, γ ∈ (0, 1) as in Theorem 2.1, we have

E t M 2 q w∇u t 2 2
α N γ t , where we used the fact that u t 1 = 1. In view of (3.1) and (3.3), it follows that E t (-M 2 q E t ) α N γ t , and by (3.5), for every t 1/2,

(-M 2 q E t ) α E t Λ -γ t t -γ(p-d)/2
. Integrating this relation (and recalling that Λ t is increasing), we get

(3.6) E 1-1 α t M -2 q Λ -γ α t t 1-γ(p-d) 2α , provided that 1 -γ(p-d) 2α
> 0. In order to check this and to simplify this expression, we recall from (2.17) that

d 2 β + p 2 γ = 1 -β -γ = α, so that (3.7) α - γ(p -d) 2 = d 2 β + d 2 γ = d 2 (1 -α).
Since α < 1, the inequality (3.6) is justified, and can be rewritten as

E t M 2α 1-α q Λ γ 1-α t t -d 2 .
Since Λ t is increasing, we get that for every s t,

s d/2 E s M 2α 1-α q Λ γ 1-α t , that is, Λ t M 2α 1-α q Λ γ 1-α t . Since γ 1-α = γ β+γ < 1, this shows that Λ t M 2α/β q ,
and in particular,

(3.8) E t M 2α/β q t d/2
. By the semi-group property,

p t (0, 0) = x∈Z d p t/2 (0, x)p t/2 (x, 0).
The symmetry of p t (•, •) thus leads to p t (0, 0) E t/2 , and in view of (3.8), this concludes the proof.

As a by-product of the above proof, we also obtain the following off-diagonal information.

Proposition 3.4 (Off-diagonal decay). For every p > d, q > d and α, β, γ ∈ (0, 1) as in Theorem 2.1, there exists C < ∞ such that if the static environment a is w-moderate, then for every t 1,

|x| p/2 * u t 2 2 C M 2α/β q t (p-d)/2 .
Proof. This follows directly from (3.5) and (3.8).

Much more precise information on the off-diagonal behaviour of the heat kernel can be obtained as an application of [24, Theorem 1.1] (see also [START_REF] Grigor Yan | Gaussian upper bounds for the heat kernel on arbitrary manifolds[END_REF][START_REF] Coulhon | The discrete integral maximum principle and its applications[END_REF][START_REF] Chen | Pointwise upper estimates for transition probability of continuous time random walks on graphs[END_REF]). We state here a particular case of this result which is most relevant to our context. Theorem 3.5 (Improved off-diagonal decay [START_REF] Folz | Gaussian upper bounds for heat kernels of continuous time simple random walks[END_REF]). There exists a constant C < ∞ such that the following holds. Let x, y ∈ Z d and c(x), c(y) < ∞. If

p t (x, x) c(x) t d/2 and p t (y, y) c(y) t d/2 , then for all t 1 ∨ |x -y|, p t (x, y) C c(x)c(y) t d/2 exp - |y -x| 2 Ct .
We conclude this section by giving some examples of applications of Theorem 3.2. To begin with, we show a heat kernel upper bound assuming stationarity and a moment condition. We refer to [START_REF] Andres | Harnack inequalities on weighted graphs and some applications to the random conductance model[END_REF]Theorem 5.4] for an example (due to Noam Berger) showing that the condition is essentially sharp for a local CLT. Proposition 3.6 (Moment condition). Let q > d and α, β, γ be as in Theorem 2.1. Assume that under the probability measure P, the family of random variables a = (a(e)) e∈B is stationary with respect to translations, takes values in (0, 1], and satisfies E a(e) -q/2 < ∞.

There exists a random variable X 0 such that

∀r < qβ 2α , E [X r ] < ∞ and (3.9) p t (0, 0) X t d/2 .
Proof. Clearly, the environment a is √ a-moderate. Hence, it suffices to check that for every r < 1, we have E[M qr q ( √ a)] < ∞. This follows from Proposition A.1.

If we also assume that the conductances are independent, then we can weaken the integrability condition to E[a(e) -γ ] < ∞ for some γ > 1/4, and thus recover some of the results of [4, Theorem 1.13], [START_REF] Boukhadra | Harnack inequalities and local central limit theorem for the polynomial lower tail random conductance model[END_REF]Theorem 1.8]. Proposition 3.7 (Moment condition under independence). Let q > d and α, β, γ be as in Theorem 2.1. Assume that under the probability measure P, the family of random variables a = (a(e)) e∈B is i.i.d., takes values in (0, 1], and satisfies

E a(e) -q 4d < ∞.
There exists a random variable X 0 such that

∀r < qβ 2α , E [X r ] < ∞ and (3.10) p t (0, 0) X t d/2 .
Proof. For an edge e, we denote by e, e the endpoints of e, conventionally chosen so that e -e is a canonical basis vector. One can find 2d paths 1 (e), . . . , 2d (e) linking e to e such that no two paths have an edge in common; moreover, we can make sure that each path contains at most 9 edges (see [START_REF] Mourrat | Lyapunov exponents, shape theorems and large deviations for the random walk in random potential[END_REF]Lemma 2.1]). We define w by

(3.11) 1 w(e) 2 = inf 1 i 2d b∈ i(e)

a(b) .

We denote by (e) a path (among 1 (e), . . . , 2d (e)) that realises the infimum above. By the Cauchy-Schwarz inequality, Clearly, one can find C < ∞ such that for each b, the number of edges e such that b ∈ (e) is bounded by C. Hence, the environment a is w/C-moderate. We now choose q ∈ (d, q) and check that w(e) -1 has finite q -th moment. By independence, for x > 0,

|∇u(e)| b∈ (e) |∇u(b)|   b∈ (e) 1 a(b)   1/2   b∈ (e) a(b)|∇u(b)| 2   1/2 w(e) -1   b∈ (e)
P[w(e) -q x] = 2d i=1 P   b∈ i(e) 1 a(b) x 2/q   .
Since each path has length at most 9, and by stationarity,

P   b∈ i(e) 1 a(b) x 2/q   9 P 1 a(b) x 2/q 9 9 1+ q 4d E[a(b) -q 4d ] x -q 2dq .
We obtain that E[w(e) -q ] < ∞ by combining the previous two displays and the fact that E[w(e) -q ] = ∞ 0 P[w(e) -q x] dx. For every r < 1, we thus have E[M q r q (w)] < ∞ by Proposition A.1, so the result follows by Theorem 3.2.

Remark 3.8. The case of percolation corresponds to assuming that (a(e)) e∈B are i.i.d. Bernoulli random variables. Obtaining heat-kernel upper bounds for super-critical percolation would require more work, which we will not pursue here (see [START_REF] Mathieu | Isoperimetry and heat kernel decay on percolation clusters[END_REF][START_REF] Barlow | Random walks on supercritical percolation clusters[END_REF] for previous work on this). In [START_REF] Lamacz | Moment bounds for the corrector in stochastic homogenization of a percolation model[END_REF], the following simpler situation is considered: all edges e pointing in a given direction satisfy a(e) = 1, while (a(e)) are i.i.d. Bernoulli for the other edges. In this case, one can show that the environment is w-moderate for some w such that all moments of w(e) -1 are finite (see [START_REF] Lamacz | Moment bounds for the corrector in stochastic homogenization of a percolation model[END_REF]Lemma 4]). We thus obtain (3.9) for a random variable X with finite moments of every order.

Dynamic environments

We now turn our attention to dynamic degenerate environments. We first define the notion of (w, K)-moderate dynamic environment. Definition 4.1. For every e ∈ B, we give ourselves a piecewise continuous function

R → [0, 1] t → a t (e),
and we call a = (a t (e)) e∈B,t∈R a dynamic environment. (It is convenient, although inessential, to consider environments defined over the whole time line.) For every x ∈ Z d and s ∈ R, we define (p s,t (x, y)) y∈Z d ,t s as the unique bounded function such that p s,s (x, y) = 1 x=y and, for every t s,

∂ t p s,t (x, y) = z∼y a t ({y, z}) (p s,t (x, z) -p s,t (x, y)) .
In probabilistic terms, p s,t (x, y) is the probability that the random walk evolving in the dynamic environment a and started at time s and position x reaches y at time t. We write u t = p 0,t (0, •) and

E t = u t 2 2 , D t = √ a t ∇u t 2 2 , D t = +∞ t K s-t D s ds.
Let K : R + → R + and, for each e ∈ B, let t ∈ R + → w t (e) ∈ [0, 1] be a measurable function. We say that the dynamic environment a is (w, K)-moderate if for every t 0, (4.1)

w t ∇u t 2 2 D t .
Theorem 4.2 (Energy upper bound for dynamic environments). Let q > d and α, β, γ ∈ (0, 1) be as in Theorem 2.1. There exists C < ∞ such that if the dynamic environment a is (w, K)-moderate, then

(4.2) E t C C(K) M 2α/β q (w) t d/2
, where

(4.3) M -2 q (w) = inf t 1 1 t t 0 M -2 q (w s ) ds and (4.4) C(K) = 1 ∨ K α/β 1 K (1-α)/β L 1 ([0,1])
.

Proof. We define

E t = +∞ t K s-t E s ds, N t = |x| p/2 * u t 2 2 .
Proposition 3.3 remains valid for dynamic random environments, and gives us

(4.5) N t N (p-2)/p t E 2/p t . Defining Λ t = 1 ∨ sup s t s d/2
E s , we obtain as for the static case that for every t

N t Λ t t (p-d)/2 . By Theorem 2.1, E t M 2 q (w t ) w t ∇u t 2 2 1, (4.6)
α N γ t , which by assumption (4.1) and (4.6) leads to

E t M 2 q (w t ) D t α Λ γ t t γ(p-d)/2 .
Since E t is decreasing, we have E t K 1 E t , and moreover, E t = -2D t . As a consequence,

E t K 1 -M 2 q (w t ) E t α Λ γ t t γ(p-d)/2
, which can be rewritten as

(4.7) -E t E -1 α t K -1 α 1 M -2 q (w t ) Λ -γ α t t -γ(p-d) 2α
.

Since Γ t is increasing and p > d, we obtain

E 1-1 α t K -1 α 1 Λ -γ α t t -γ(p-d) 2α t 0 M -2 q (w s ) ds.
Recalling (3.7) and the definition of M q = M q (w) in (4.3), we obtain that for every t 1,

t d/2 E t K α 1-α 1 M 2α 1-α q Λ γ 1-α t .
We now observe that, since E t is decreasing,

E t E 2t t 0 K s ds,
and in particular, for t 1,

E t K L 1 ([0,1]) E 2t . Since moreover, Λ 2 2 d/2 , we get Λ t 1 + K α 1-α 1 K L 1 ([0,1]) M 2α 1-α q Λ γ 1-α t ,
and this proves the theorem since C(K) 1 and M q 1 (recall that w 1).

As before, the proof above reveals more detailed information about off-diagonal decay of the heat kernel. Proposition 4.3 (Off-diagonal decay). Let p > d, q > d and α, β, γ ∈ (0, 1) be as in Theorem 2.1. There exists C < ∞ such that if the dynamic environment a is (w, K)-moderate, then for every t 1,

|x| p/2 * u t 2 2 C C(K) M 2α/β q (w) t (p-d)/2 .
Proof. This follows from (4.6) and (4.2).

For a dynamic environment a, we let a (t) be the dynamic environment defined, for all s ∈ R, by a

(t) s = a t-s .
Corollary 4.4 (Heat kernel upper bound for dynamic environments). In the setting of Theorem 4.2, there exists C < ∞ such that if a is (w, K)-moderate and a (t) is (w (t) , K (t) )-moderate, then

(4.8) p 0,t (0, 0) C C(K)C(K (t) ) M q (w)M q (w (t) )
α/β t d/2 Corollary 4.4 will be obtained from the following lemma.

Lemma 4.5 (Space-time reversal). For every

u v ∈ R, t ∈ R and x, y ∈ Z d , p u,v (x, y) = p (t) t-v,t-u (y, x). Proof. For f : Z d → R of compact support, we write f u,v (x) = y∈Z d p u,v (x, y)f (y), f (t) u,v (x) = y∈Z d p (t) u,v (x, y)f (y).
The lemma is equivalent to the claim that for every f , g of compact support,

(f u,v , g) = (f , g (t)
t-v,t-u ), where (•, •) denotes the scalar product on L 2 (Z d ). That this relation is correct is clear if t → a t is piecewise constant. Otherwise, one can proceed via finite-volume approximations.

Proof of Corollary 4.4. From the lemma,

p t/2,t (x, 0) = p (t) 0,t/2 (0, x).
Hence, a Cauchy-Schwarz inequality gives p 0,t (0, 0) =

x∈Z d p 0,t/2 (0, x) p t/2,t (x, 0) E t/2 E (t) t/2
(with obvious notation), and the result thus follows from Theorem 4.2.

We conclude this section by providing a method to build (w, K) out of a dynamic environment a, so that a is (w, K)-moderate.

Proposition 4.6 (A criterion for moderation).

There exists c < ∞ such that the following holds. Let k : R + → R + be such that (1 + t 2 )k t dt < ∞, let

K t = k t + +∞ t s k s ds,
and for a dynamic environment a, let (4.9)

w 2 t = +∞ t k s-t a s ds.
Then the dynamic environment a is (w, cK)-moderate.

Remark 4.7. Recall that in order to get non-trivial bounds from Theorem 4.2, we still need to make sure that w -q is integrable for some q > d (the fact that K ∈ L 1 is automatic from the assumption on k). This can be obtained if one knows that it is unlikely for a s to remain close to 0 during a long time interval.

Proof. which is the desired result.

The exclusion process as dynamic random environment

As an example of the results of the previous section, we study a random walk evolving in an environment that is a local function of the symmetric simple exclusion process on Z d , d 2. Recall that the infinitesimal generator L of the symmetric simple exclusion process is given by This process is also called the Kawasaki dynamics. (Strictly speaking, the exclusion process is thought of as particles performing independent random walks, but with any jump of one particle onto another being suppressed; since the particles are indistinguishable here, this is equivalent to the process defined by (5.1).) We refer to [START_REF] Liggett | Stochastic interacting systems: contact, voter and exclusion processes[END_REF]Part III] for a thorough study of this process.

For every ρ ∈ [0, 1], let µ ρ = Z d Bernoulli(ρ). The measures µ ρ are the only extremal invariant (and in fact, reversible) measures of the process [START_REF] Liggett | Stochastic interacting systems: contact, voter and exclusion processes[END_REF]Corollary III.1.11]. From now on, we fix ρ ∈ (0, 1). By stationarity, we can build the probability measure P such that under this measure, the process (η t ) t∈R (defined over the whole time line) evolves as an exclusion process, and η t is distributed according to µ ρ for every t ∈ R.

For concreteness, we define our dynamic environment by

a t (e) = 1 if η t (e) = η t (e) = 0, 0 otherwise,
where e and e are the end-points of e. The specific form of a is not important, as long as it is a function of the unoriented edge e, and depends only locally on the configuration η. We let (p s,t (x, y)) s t∈R,x,y∈Z d be as in Definition 4.1.

Theorem 5.1 (Heat kernel estimates).

There exists a random variable X with finite moments of every order and such that (5.2)

x∈Z d (p 0,t (0, x)) 2 X t d/2 .
Moreover, there exists a stationary process (Y t ) t∈R satisfying

(5.3) p 0,t (0, 0) Y t t d/2 ,
and such that for every r > 0 and ε > 0,

(5.4) E [(Y t ) r ] < ∞, (5.5
) E sup t 1 Y t t ε r < ∞.
Remark 5.2. We believe that sup t t d/2 p 0,t (0, 0) should have finite moments of every order, but proving this would require more work, so we do not pursue this question further here.

We begin by showing that a t (e) is unlikely to remain equal to 0 for a long period of time. The first term in the sum above is controlled since δ > 1/d. For the second term, the fact that δ < 1 ensures that the logarithmic term decays to 0 slower than any negative power of t, so the proof is complete.

Proof of Theorem 5.1. We let k t = (1 + t) -4 , and K, w be defined as in Proposition 4.6, so that the dynamic environment a is (w, cK)-moderate. For every u ∈ (0, 1), ).

P
In particular, w t (e) -1 has finite moments of every order. By Corollary A.2, the maximal function M q (w t ) has finite moments of every order. The same property holds for M q (w) itself by Remark A.3. (Strictly speaking, Remark A.3 applies only to processes indexed by a discrete time, but it is not difficult to check that this is sufficient for our purpose.) By Theorem 4.2, we thus obtain (5.2) (the choice of q ∈ (d, ∞) and of α, β, γ as in Theorem 2.1 is arbitrary). Recall that we denote the time reversals around time t of a and w by a (t) and w (t) respectively. Clearly, a (t) is (w (t) , cK)-moderate, so Corollary 4.4 yields that p 0,t (0, 0) Y t t d/2 , with Y t = C M q (w)M q (w (t) )

α/β for some constant C < ∞. Since w (t) and w have the same law, every moment of M q (w (t) ) is finite, and (5.4) is proved. In order to obtain (5.5), it suffices to consider a supremum over integer times, since for any u ∈ [t -1, t], we have M q (w (u) ) 2M q (w (t) ). We then note that for any r > 1/ε and y > 0,

P sup n∈N\{0} n -ε Y n y +∞ n=1 E [(Y n ) r ]
(yn ε ) r C y r , so that (5.5) follows.

Appendix A. Maximal inequalities

In this appendix, we recall classical properties of maximal functions in a multidimensional setting. Let (Ω, F, P) be a probability space, and (θ x ) x∈Z d be a measurepreserving action of Z d on this space. For every measurable function f : Ω → R, we define the maximal function

Mf (ω) = sup r∈N 1 |B r | x∈Br f (θ x ω).
The following result is [1, Theorem 3.2].

Proposition A.1 (Weak type (1,1) estimate). For every f ∈ L 1 (Ω) and λ > 0,

P [Mf λ] 3 d f L 1 (Ω) λ .
Obviously, the maximal function defines a bounded operator from L ∞ to L ∞ . By the Marcinkiewicz interpolation theorem (see e. M(g -1 ).

  e)| p 1/p . Finally, we introduce the shorthand notation | • | * := | • | ∨ 1.

Lemma 2 . 10 .

 210 Let a, a , b, c > 0, and define σ = ab+a c+bc. For every A, B, D 0, inf r,R>0

  ) 2 |∇u(e)| 2 e,b:b∈ (e) a(b)|∇u(b)| 2 .

(5. 1 )

 1 Lf (η) = e∈B (f (η e ) -f (η)), where η = (η(x)) x∈Z d ∈ {0, 1} Z d ,f is a function that depends on a finite number of coordinates of η, and (η e )(x) = η(y) if {x, y} = e, η(x) otherwise.

  g. [40, Appendix D]), we thus have the following. Corollary A.2 (L p estimate). For every p ∈ (1, ∞], there exists C p < ∞ such thatMf L p (Ω) C p f L p (Ω) . Remark A.3. If we let m g(ω) = inf r∈N 1 |B r | x∈Br g(θ x ω),then for every p ∈ (1, ∞] and g > 0, we also have(m g) -1 L p (Ω) C p g -1 L p (Ω), since by Jensen's inequality, (m g) -1

  The condition (1 + t 2 )k t dt < ∞ ensures that K is integrable. We need to estimate (∇u s -∇u t ) 2 (e) ds.Up to a constant (and since a s 1), the second sum above is bounded by

						+∞
		w t ∇u t	2 2 =	w 2 t (∇u t ) 2 (e) =	k s-t a s (∇u t ) 2 (e) ds.
				e∈B		t
	This quantity is bounded by
		+∞				+∞
	t	k s-t (u s -u t ) 2 (x) e∈B a s (∇u s ) 2 (e) =Ds = a s x∈Z d ds + t k s-t e∈B e∈B t ∇ * a s ∇u s (e) ds s	2
					(Jensen)	(s -t)	s	(∇ * a s ∇u s (e))	2 ds ,
						e∈B	t
	which, up to a constant, is bounded by
				s		s
			(s -t)	a s (∇u s (e)) 2 ds = (s -t)	D s ds .
				t e∈B		t
	We have thus shown that
				+∞		+∞	s
	w t ∇u t	2 2		k s-t D s ds +	(s -t)k s-t	D s ds ds
				t		t	t

+∞ t k s-t D s ds + +∞ t ds D s +∞ s (s -t)k s-t ds,

  (x)) x∈Z d are independent Bernoulli random variables of parameter ρ ∈ (0, 1). As a consequence, for every s ∈ R and t 2,1 -P [A s,t ] x∈B log δ t P η s ≡ 1 on B log δ t \ {x} = |B log δ t | exp |B log δ t | -1 log(ρ) C exp -c log δd t . A k log δ t,t holds C exp -c log δd t .Let e be an edge adjacent to the origin. Conditionally on A 0,t , we can estimate the probability that a s (e) becomes 1 by considering a particular choice of moves that bring the two holes in B log δ t onto the two endpoints of e, and then asking that they stay put for one unit of time. More precisely, for every t 2,

	By a union bound (and since δ > 1/d), we obtain
	1 -P ∀k integer, 0 k log δ t -1, P t log δ t a
	0
	Lemma 5.3. For every κ < 1, there exists C < ∞ such that
	t
	P	a s (e) ds 1	C exp (-t κ ) .
	0
	Proof. Throughout the proof, the value of the constants c > 0 and C < ∞ may
	vary in each occurence. Let δ ∈ (1/d, 1), and denote by A s,t the event

there exist x = y ∈ B log δ t s.t. η s (x) = η s (y) = 0.

Recall that under P and for every time s, the configuration η s is distributed accoring to the invariant measure µ ρ . In other words, for any fixed s, the random variables (η s s (e) ds 1 A 0,t exp -C log δ t (the bound being very crude). By the Markov property,

P t 0 a s (e) ds 1 C exp -c log δd t + 1 -exp -C log δ t t log δ t C exp -c log δd t + exp t log δ t log 1 -exp -C log δ t .