Although recent provable methods have been developed to compute preimage bounds for neural networks, their scalability is fundamentally limited by the #P-hardness of the problem. In this work, we adopt a novel probabilistic perspective, aiming to deliver solutions with high-confidence guarantees and bounded error. To this end, we investigate the potential of bootstrap-based and randomized approaches that are capable of capturing complex patterns in high-dimensional spaces, including input regions where a given output property holds. In detail, we introduce Random Forest Property Verifier (RF-ProVe), a method that exploits an ensemble of randomized decision trees to generate candidate input regions satisfying a desired output property and refines them through active resampling. Our theoretical derivations offer formal statistical guarantees on region purity and global coverage, providing a practical, scalable solution for computing compact preimage approximations in cases where exact solvers fail to scale.

Random access to highly compressed strings - represented by straight-line programs or Lempel-Ziv parses, for example - is a well-studied topic. Random access to such strings in strongly sublogarithmic time is impossible in the worst case, but previous authors have shown how to support faster access to specific characters and their neighbourhoods. In this paper we explore whether, since better compression can impede access, we can support faster access to less compressible substrings of highly compressed strings. We first show how, given a run-length compressed straight-line program (RLSLP) of size g_{rl} or a block tree of size L, we can build an O (g_{rl})-space or an O (L)-space data structure, respectively, that supports access to any character in time logarithmic in the length of the longest repeated substring containing that character. That is, the more "incongruous" a character is with respect to the characters around, the faster we can support access to it. We then prove a similar but more powerful and sophisticated result for parsings in which phrases' sources do not overlap much larger phrases, with the query time depending also on the number of phrases we must copy from their sources to obtain the queried character.

We study the problem of generating robust counterfactual explanations for deep learning models subject to model changes. We focus on plausible model changes altering model parameters and propose a novel framework to reason about the robustness property in this setting. To motivate our solution, we begin by showing for the first time that computing the robustness of counterfactuals with respect to model changes is NP-hard. As this (practically) rules out the existence of scalable algorithms for exactly computing robustness, we propose a novel probabilistic approach which is able to provide tight estimates of robustness with strong guarantees while preserving scalability. Remarkably, and differently from existing solutions targeting plausible model changes, our approach does not impose requirements on the network to be analysed, thus enabling robustness analysis on a wider range of architectures, including state-of-the-art tabular transformers. A thorough experimental analysis on four binary classification datasets reveals that our method improves the state of the art in generating robust explanations, outperforming existing methods.

Ensuring safety in reinforcement learning (RL) is critical for deploying agents in real-world applications. During training, current safe RL approaches often rely on indicator cost functions that provide sparse feedback, resulting in two key limitations: (i) poor sample efficiency due to the lack of safety information in neighboring states, and (ii) dependence on cost-value functions, leading to brittle convergence and suboptimal performance. After training, safety is guaranteed via formal verification (FV) methods for deep neural networks, whose computational complexity hinders their application during training. We address the limitations of using cost functions via verification by proposing a safe RL method based on a violation value—the risk associated with policy decisions in a portion of the state space. Our approach verifies safety properties (i.e., state-action pairs) that may lead to unsafe behavior, and quantifies the size of the state space where properties are violated. This violation value is then used to penalize the agent during training to encourage safer policy behavior. Given the NP-hard nature of FV, we propose an efficient, sample-based approximation with probabilistic guarantees to compute the violation value. Extensive experiments on standard benchmarks and real-world robotic navigation tasks show that violation-augmented approaches significantly improve safety by reducing the number of unsafe states encountered while achieving superior performance compared to existing methods.

We study the complexity of constructing an optimal parsing φ of a string s = s 1 … s n under the constraint that given a position p in the original text, and the LZ76-like (Lempel Ziv 76) encoding of T based on φ , it is possible to identify/decompress the character s p by performing at most c accesses to the LZ encoding, for a given integer c . We refer to such a parsing φ as a c -bounded access LZ parsing or c -BLZ parsing of s . We show that for any constant c the problem of computing the optimal c -BLZ parsing of a string, i.e., the one with the minimum number of phrases, is NP -hard and also APX -hard, i.e., no P T A S can exist under the standard complexity assumption P ≠ N P . We also study the ratio between the sizes of an optimal c -BLZ parsing of a string s and an optimal LZ76 parsing of s (which can be greedily computed in polynomial time). For this we establish a non-trivial lower bound Ω ( | s | c + 1 ) on the size of an optimal parsing for a square free string s , and also show that such a lower bound is tight for a large class of (square free) morphic words. Finally, after showing that under ETH, every algorithm for c -BLZ requires time 2 Ω ( | s | 1 c ) , hence strongly exponential in the special case c = 1 , we show an algorithm matching this bound that can compute an optimal 1-BLZ parsing of a string s in time ⁎ O ⁎ ( 1.755 | s | ) .

We present Probabilistically Tightened Linear Relaxation-based Perturbation Analysis (PT-LiRPA), a novel framework that combines over-approximation techniques from LiRPA-based approaches with a sampling-based method to compute tight intermediate reachable sets. In detail, we show that with negligible computational overhead, PT-LiRPA exploiting the estimated reachable sets, significantly tightens the lower and upper linear bounds of a neural network's output, reducing the computational cost of formal verification tools while providing probabilistic guarantees on verification soundness. Extensive experiments on standard formal verification benchmarks, including the International Verification of Neural Networks Competition, show that our PT-LiRPA-based verifier improves robustness certificates, i.e., the certified lower bound of ε perturbation tolerated by the models, by up to 3.31X and 2.26X compared to related work. Importantly, our probabilistic approach results in a valuable solution for challenging competition entries where state-of-the-art formal verification methods fail, allowing us to provide answers with high confidence (i.e., at least 99%).

Identifying safe areas is a key point to guarantee trust for systems that are based on Deep Neural Networks (DNNs). To this end, we introduce the AllDNN-Verification problem: given a safety property and a DNN, enumerate the set of all the regions of the property input domain which are safe, i.e., where the property does hold. Due to the #P-hardness of the problem, we propose an efficient approximation method called ε-ProVe. Our approach exploits a controllable underestimation of the output reachable sets obtained via statistical prediction of tolerance limits, and can provide a tight —with provable probabilistic guarantees— lower estimate of the safe areas. Our empirical evaluation on different standard benchmarks shows the scalability and effectiveness of our method, offering valuable insights for this new type of verification of DNNs.

We study the problem of assessing the robustness of counterfactual explanations for deep learning models. We focus on plausible model shifts altering model parameters and propose a novel framework to reason about the robustness property in this setting. To motivate our solution, we begin by showing for the first time that computing the robustness of counterfactuals with respect to plausible model shifts is NP-complete. As this (practically) rules out the existence of scalable algorithms for exactly computing robustness, we propose a novel probabilistic approach which is able to provide tight estimates of robustness with strong guarantees while preserving scalability. Remarkably, and differently from existing solutions targeting plausible model shifts, our approach does not impose requirements on the network to be analyzed, thus enabling robustness analysis on a wider range of architectures. Experiments on four binary classification datasets indicate that our method improves the state of the art in generating robust explanations, outperforming existing methods on a range of metrics.

In this article, we study the problem of computing Random Forest-distances in the presence of missing data. We present a general framework which avoids pre-imputation and uses in an agnostic way the information contained in the input points. We centre our investigation on RatioRF, an RF-based distance recently introduced in the context of clustering and shown to outperform most known RF-based distance measures. We also show that the same framework can be applied to several other state-of-the-art RF-based measures and provide their extensions to the missing data case. We provide significant empirical evidence of the effectiveness of the proposed framework, showing extensive experiments with RatioRF on 15 datasets. Finally, we also positively compare our method with many alternative literature distances, which can be computed with missing values.

Deep Neural Networks are increasingly adopted in critical tasks that require a high level of safety, e.g., autonomous driving. While state-of-the-art verifiers can be employed to check whether a DNN is unsafe w.r.t. some given property (i.e., whether there is at least one unsafe input configuration), their yes/no output is not informative enough for other purposes, such as shielding, model selection, or training improvements. In this paper, we introduce the #DNN-Verification problem, which involves counting the number of input configurations of a DNN that result in a violation of a particular safety property. We analyze the complexity of this problem and propose a novel approach that returns the exact count of violations. Due to the #P-completeness of the problem, we also propose a randomized, approximate method that provides a provable probabilistic bound of the correct count while significantly reducing computational requirements. We present experimental results on a set of safety-critical benchmarks that demonstrate the effectiveness of our approximate method and evaluate the tightness of the bound.

In this paper we propose RatioRF, a novel Random Forest-based similarity measure for clustering. We build upon Tversky's ratio model definition of similarity and specialize it to the Random Forest case. We study some properties of the proposed axiomatic similarity measure and present an extensive experimental clustering analysis involving different datasets and configurations. Results confirm that RatioRF represents a good alternative to other similar measures for clustering recently studied in the literature.

Decision trees are widely used in many settings where interpretable models are preferred or required. As confirmed by recent empirical studies, the interpretability/explanability of a decision tree critically depends on some of its structural parameters, like size and the average/maximum depth of its leaves. There is indeed a vast literature on the design and analysis of decision tree algorithms that aim at optimizing these parameters.This paper contributes to this important line of research: we propose as a novel criterion of measuring the interpretability of a decision tree, the sparsity of the set of attributes that are (on average) required to explain the classification of the examples. We give a tight characterization of the best possible guarantees achievable by a decision tree built to optimize both our newmeasure (which we call the {\em explanation size}) and the more classical measures of worst-case and average depth. In particular, we give an algorithm that guarantees $O(\ln n )$-approximation (hence optimal if $P \neq NP$) for the minimization of both the average/worst-case explanation size and the average/worst-case depth. In addition to our theoretical contributions, experiments with 20 real datasets show that our algorithm has accuracy competitive with CART while producing trees that allow for much simpler explanations.

An impurity measures I : Rd→ R+is a function that assigns a d-dimensional vector v to a non-negative value I(v) so that the more homogeneous v, with respect to the values of its coordinates, the larger its impurity. A well known example of impurity measures is the entropy impurity. We study the problem of clustering based on the entropy impurity measures. Let V be a collection of n many d-dimensional vectors with non-negative components. Given V and an impurity measure I, the goal is to find a partition n of V into k groups V1, . . . , Vkso as to minimize the sum of the impurities of the groups in P, i.e., I(P) = Σi=1kI (Σv∈Viv). Impurity minimization has been widely used as quality assessment measure in probability distribution clustering (KL-divergence) as well as in categorical clustering. However, in contrast to the case of metric based clustering, the current knowledge of impurity measure based clustering in terms of approximation and in approximability results is very limited. Here, we contribute to change this scenario by proving that the problem of finding a clustering that minimizes the Entropy impurity measure is APX-hard, i.e., there exists a constant ε > 0 such that no polynomial time algorithm can guarantee (1 + ε)-approximation under the standard complexity hypothesis P ≠ N P . The in approximability holds even when all vectors have the same 11 norm. This result provides theoretical limitations on the computational efficiency that can be achievable in the quantization of discrete memoryless channels, a problem that has recently attracted significant attention in the signal processing community. In addition, it also solve a question that remained open in previous work on this topic [Chaudhuri and McGregor COLT 08; Ackermann et. al. ECCC 11].

Machine Teaching studies how efficiently a Teacher can guide a Learner to a target hypothesis. We focus on the model of Machine Teaching with a black box learner introduced in [Dasgupta et al., ICML 2019], where the teaching is done interactively without having any knowledge of the Learner’s algorithm and class of hypotheses, apart from the fact that it contains the target hypothesis $h^*$. We first refine some existing results for this model and, then, we study new variants of it. Motivated by the realistic possibility that $h^*$ is not available to the learner, we consider the case where the teacher can only aim at having the learner converge to a best available approximation of $h^*$. We also consider weaker black box learners, where, in each round, the choice of the consistent hypothesis returned to the Teacher is not adversarial, and in particular, we show that better provable bounds can be obtained for a type of Learner that moves to the next hypothesis smoothly, preferring hypotheses that are close to the current one; and for another type of Learner that can provide to the Teacher hypotheses chosen at random among those consistent with the examples received so far. Finally, we present an empirical evaluation of our basic interactive teacher on real datasets.

We define a D-ary Fano code based on a natural generalization of the splitting criterion of the binary Fano code to the case of D-ary code. We show that this choice allows for an efficient computation of the code tree and also leads to a strong guarantee with respect to the redundancy of the resulting code: for any source distribution p = p1,... pn1) for D = 2, 3,4 the resulting code satisfies L̅ - HD(p) ≤ 1 - pmin, where L̅ is the average codeword length, pmin= minipi, and HD(p) = Σi=1npilogD1/pi(the D-ary entropy);2) inequality (1) holds for every D ≥ 2 whenever every internal node has exactly D children in the code tree produced by our construction.We also formulate a conjecture on the basic step applied by our algorithm in each internal node of the code tree, that, if true, would imply that the bound in (1) is actually achieved for all D ≥ 2 without the restriction of item 2.

We study the problem of optimizing the clustering of a set of vectors when the quality of the clustering is measured by the Entropy or the Gini impurity measure. Our results contribute to the state of the art both in terms of best known approximation guarantees and inapproximability bounds: (i) we give the first polynomial time algorithm for Entropy impurity based clustering with approximation guarantee independent of the number of vectors and (ii) we show that the problem of clustering based on entropy impurity does not admit a PTAS. This also implies an inapproximability result in information theoretic clustering for probability distributions closing a problem left open in [Chaudhury and McGregor, COLT08] and [Ackermann et al., ECCC11]. We also report experiments with a new clustering method that was designed on top of the theoretical tools leading to the above results. These experiments suggest a practical applicability for our method, in particular, when the number of clusters is large.

Given a discrete random variable X that takes values in a finite set χ according to a probability mass function (pmf) P, a truncated pmf Q of P is a conditional pmf that results from restricting the domain of X to some subset of χ. Truncated pmf arise in several problems of statistics and probability. In this paper, we propose and analyze a few criteria to truncate pmf's so that the truncated one is as much close as possible to the original pmf, under different information theoretic measures of distance.

Given two discrete random variables X and Y, with probability distributions p = (p1, ..., pn) and q = (q1, ..., qm), respectively, let us denote by C(p, q) the set of all couplings of p and q, that is, the set of all bivariate probability distributions that have p and q as marginals. In this paper, we study the problem of finding a joint probability distribution in C(p, q) of minimum entropy (equivalently, a coupling that maximizes the mutual information between X and Y), and we discuss several situations where the need for this kind of optimization naturally arises. Since the optimization problem is known to be NP-hard, we give an efficient algorithm to find a joint probability distribution in C(p, q) with entropy exceeding the minimum possible at most by 1 bit, thus providing an approximation algorithm with an additive gap of at most 1 bit. Leveraging on this algorithm, we extend our result to the problem of finding a minimum-entropy joint distribution of arbitrary k ≥ 2 discrete random variables X1, ..., Xk, consistent with the known k marginal distributions of the individual random variables X1, ..., Xk. In this case, our algorithm has an additive gap of at most log k from optimum. We also discuss several related applications of our findings and extensions of our results to entropies different from the Shannon entropy.

Given a probability distribution p=(p1, ⋯, pn) and an integer 1 ≤ m1, ⋯, qm) is a contiguous m-aggregation of p if there exist indices such that for each j=1, ⋯, m it holds that qj= Σk=i(j-1)+1ijpk. In this paper, we consider the problem of efficiently finding the contiguous m-aggregation of maximum entropy. We design a dynamic programming algorithm that solves the problem exactly, and two more time-efficient greedy algorithms that provide slightly sub-optimal solutions. We also discuss a few scenarios where our problem matters.

It is well known that the entropy $H(X)$ of a discrete random variable $X$ is always greater than or equal to the entropy $H(f(X))$ of a function $f$ of $X$, with equality if and only if $f$ is one-to-one. In this paper, we give tight bounds on $H(f(X))$ when the function $f$ is not one-to-one, and we illustrate a few scenarios where this matters. As an intermediate step towards our main result, we derive a lower bound on the entropy of a probability distribution, when only a bound on the ratio between the maximal and minimal probabilities is known. The lower bound improves on previous results in the literature, and it could find applications outside the present scenario.

It is well known that the entropy H (X) of a finite random variable is always greater or equal to the entropy H (f (X)) of a function f of X, with equality if and only if f is one-to-one. In this paper, we give tights bounds on H(f (X) when the function f is not one-to-one, and we illustrate a few scenarios where this matters. As an intermediate step towards our main result, we prove a lower bound on the entropy of a probability distribution, when only a bound on the ratio between the maximum and the minimum probability is known. Our lower bound improves previous results in the literature, and it could find applications outside the present scenario.

Given two discrete random variables X and Y, with probability distributions p = (p1, ..., pn) and q = (q1, ..., qm), respectively, denote by C(p, q) the set of all joint distributions of X and Y that have p and q as marginals. In this paper, we study the problem of finding the joint probability distribution in C (p, q) of minimum entropy (equivalently, the joint probability distribution that maximizes the mutual information between X and Y), and we discuss several situations where the need for this kind of optimization naturally arises. Since the optimization problem is known to be NP-hard, we give an efficient algorithm to find a joint probability distribution in C(p, q) with entropy exceeding the minimum possible by at most 1, thus providing an approximation algorithm with additive approximation factor of 1. We also discuss some related consequences of our findings.

Given a probability distribution p = (p1, ..., pn) and an integer m1, ..., qm) that is “the closest” to p, that is, that best approximates p? It is clear that the answer depends on the function one chooses to evaluate the goodness of the approximation. In this paper we provide a general criterion to approximate p with a shorter vector q by using ideas from majorization theory. We evaluate the goodness of our approximation by means of a variety of information theoretic distance measures.

In several applications of automatic diagnosis and active learning a central problem is the evaluation of a discrete function by adaptively querying the values of its variables until the values read uniquely determine the value of the function. In general reading the value of a variable is done at the expense of some cost (computational or possibly a fee to pay the corresponding experiment). The goal is to design a strategy for evaluating the function incurring little cost (in the worst case or in expectation according to a prior distribution on the possible variables’ assignments). We provide an algorithm that builds a strategy (decision tree) with both expected cost and worst cost which are at most an O(\log n) factor away from, respectively, the minimum possible expected cost and the minimum possible worst cost. Our algorithm provides the best possible approximation simultaneously with respect to both criteria. In fact, there is no algorithm that can guarantee o(\log n) approximation, under the assumption that \cal P ≠\cal NP.

Given a sequence of n numbers, the MAXIMUM CONSECUTIVE SUBSUMS PROBLEM (MCSP) asks for the maximum consecutive sum of lengths ℓ for each ℓ = 1, …, n. No algorithm is known for this problem which is significantly better than the naive quadratic solution. Nor a super linear lower bound is known. The best known bound for the MCSP is based on the the computation of the (min; +)-convolution, another problem for which neither an O(n2−ε) upper bound is known nor a super linear lower bound. We show that the two problems are in fact computationally equivalent by providing linear reductions between them. Then, we concentrate on the problem of finding super linear lower bounds and provide empirical evidence for our conjecture that the solution of both problems requires Ω(n log n) time in the decision tree model.

We introduce two new information theoretic measures of distances among probability distributions and we discuss their possible applications to Econometrics.

Let f be a function on a set of variables V . For each x ∈ V , let c(x) be the cost of reading the value of x . An algorithm for evaluating f is a strategy for adaptively identifying and reading a set of variables U ⊆ V whose values uniquely determine the value of f . We are interested in finding algorithms which minimize the cost incurred to evaluate f in the above sense. Competitive analysis is employed to measure the performance of the algorithms. We address two variants of the above problem. We consider the basic model in which the evaluation algorithm knows the cost c(x) , for each x ∈ V . We also study a novel model where the costs of the variables are not known in advance and some preemption is allowed in the reading operations. This model has applications, for example, when reading a variable coincides with obtaining the output of a job on a CPU and the cost is the CPU time. For the model where the costs of the variables are known, we present a polynomial time algorithm with the best possible competitive ratio γ c f for each function f that is representable by a threshold tree and for each fixed cost function c (⋅). Remarkably, the best-known result for the same class of functions is a pseudo-polynomial algorithm with competitiveness 2 γ c f . Still in the same model, we introduce the Linear Programming Approach ( LPA ), a framework that allows the design of efficient algorithms for evaluating functions. We show that different implementations of this approach lead in general to the best algorithms known so far—and in many cases to optimal algorithms—for different classes of functions considered before in the literature. Via the LPA , we are able to determine exactly the optimal extremal competitiveness of monotone Boolean functions. Remarkably, the upper bound which leads to this result, holds for a much broader class of functions, which also includes the whole set of Boolean functions. We also show how to extend the LPA (together with these results) to the model where the costs of the variables are not known beforehand. In particular, we show how to employ the extended LPA to design a polynomial-time optimal (with respect to competitiveness) algorithm for the class of monotone Boolean functions representable by threshold trees.

We consider the problem of searching for an unknown number in the search space U ={0,...,M-1}. q-ary questions can be asked and some of the answers may be wrong. An arbitrary integer weighted bipartite graph Gamma is given, stipulating the cost Gamma(i,j) of each answer jnei when the correct answer is i, i.e., the cost of a wrong answer. Correct answers are supposed to be cost-less. It is assumed that a maximum cost e for the sum of the cost of all wrong answers can be afforded by the responder during the whole search. We provide tight upper and lower bounds for the largest size M = M(q,e,Gamma,n) for which it is possible to find an unknown number x*isinU with n q-ary questions and maximum lie cost e. Our results improve the bounds of Cicalese et al. (2004) and Ahlswede et al. (2008). The questions in our strategies can be asked in two batches of nonadaptive questions. Finally, we remark that our results can be further generalized to a wider class of error models including also unidirectional errors.

The well known Tunstall algorithm for discrete memoryless sources [17] produces optimal variable-to-fixed length source codes that maximize the expected number of source letters per codeword. Tun stall algorithm achieves this result by constructing parse trees with maximum average height for the source output. In the first part of this paper we introduce a simple variant of Tun stall algorithm in order to optimizes additional natural cost functions of interest. For instance we show how to select, among all parse trees with maximum average height, those having minimum height, minimum variance, minimum external length, and more general natural parameters. In the second part of the paper we consider the problem of selecting, among all parse trees of height bounded by some parameter L, those parse trees having maximum average height. We motivate the problem, and we quantify the loss of performance these parse trees suffer with respect to unrestricted Tuns tall parse trees, when they are used as variable-to-fixed length encoding for a discrete memoryless source.

In this correspondence, we prove that the probability distribution induced on the leaves of a Tunstall parse tree for a given source is a (unique) lower bound in the partially ordered set of the probability distributions induced by all possible parse trees with a same number of leaves, and ordered according to the majorization partial order. We apply this result to the problem of optimally approximating a uniform distribution with flips of a biased coin

This paper focuses on competitive function evaluation in the context of computing with priced information. A function f is given together with a cost cx for each variable x of f. The cost cx has to be paid to read the value of x. The problem is to design algorithms that query the values of the variables sequentially in order to compute the function while trying to minimize the total cost incurred. Competitive analysis is employed to evaluate the performance of the algorithms. We describe a novel approach for devising efficient algorithms in this setting. We apply our approach to several classes of functions which have been studied in the literature of computing with priced information. In all cases considered, our approach provides algorithms that achieve better bounds than the best known algorithm for the same class of functions.More precisely, for the class of monotone boolean functions, we give a polynomial time algorithm with extremal competitiveness (k+l - √ min(k,l)) where k (l) denotes the minimum number of variables that one must read, in the worst case, in order to prove that the function under consideration evaluates to 1 (0). This dramatically improves upon the best known result which is an exponential time 2 max(k, l)-competitive algorithm. For the subclass of monotone boolean functions known as Threshold Trees we further improve our bounds and give a polynomial time algorithm with extremal competitive ratio 1.618 max(k, l).We then apply our methodology to classes of non-boolean functions. We consider the case of the so called Game Trees. We improve upon previously published results for this class of functions providing a polynomial time algorithm with extremal competitive ratio 1.5 γ(f), where γ(f) is a lower bound on the extremal competitive ratio of any deterministic algorithm.Finally, we consider the case when f is the function min (minimum). In this case, we are able to determine the optimal competitiveness for the problem. In fact we provide an algorithm with an (n-2)-competitive ratio, which matches the known lower bound.

We consider the problem of bounding the average length of an optimal (Huffman) source code when only limited knowledge of the source symbol probability distribution is available. For instance, we provide tight upper and lower bounds on the average length of optimal source codes when only the largest or the smallest source symbol probability is known. Our results rely on basic results of majorization theory and on the Schur concavity of the minimum average length of variable-length source codes for discrete memoryless sources. In the way to prove our main result we also give closed formula expressions for the average length of Huffman codes for several classes of probability distributions.

We prove that the entropy is a supermodular and subadditive function on the lattice of all n-dimensional probability distributions, ordered according to the partial order relation defined by majorization among vectors.