Narrow Results

We prove the first unconditional consistency result for superpolynomial circuit lower bounds with a relatively strong theory of bounded arithmetic. Namely, we show that the theory $V_2^0$ is consistent with the conjecture that $NEXP⊈P/poly$, i.e. some problem that is solvable in non-deterministic exponential time does not have polynomial size circuits. We suggest this is the best currently available evidence for the truth of the conjecture. The same techniques establish the same results with $NEXP$ replaced by the class of problems decidable in non-deterministic barely superpolynomial time such as $NTIME(n^{O(logloglogn)})$. Additionally, we establish a magnification result on the hardness of proving circuit lower bounds.

Let $G$ be a graph and $S\subseteq V(G)$. We define by $〈S〉$ the subgraph of $G$ induced by $S$. For each vertex $u\in S$ and for each vertex $v\in S\setminus \{u\}$, $d_{(G,S\setminus \{u\})}(u,v)$ is the length of the shortest path in $〈V(G)-((S-\{u\})-\{v\})〉$ between $u$ and $v$ if such a path exists, and $\infty$ otherwise. For a vertex $u\in S$, let ${\omega }_{(G,S\setminus \{u\})}(u)={\sum }_{v\in S\setminus \{u\}}{(\frac{1}{2})}^{d_{(G,S\setminus \{u\})}(u,v)-1}$ where $\left(\right.\frac{1}{2}{\left)\right.}^{\infty }=0$. Jäger and Rautenbach [27] define a set $S$ of vertices to be exponential independent if ${\omega }_{(G,S\setminus \{u\})}(u)<1$ for every vertex $u$ in $S$. The exponential independence number ${\alpha }_e(G)$ of $G$ is the maximum order of an exponential independent set. In this paper, we give a general theorem and we examine exponential independence number of some tree graphs and thorn graph of some graphs.

Community detection is significative in the complex network. This paper focuses on community detection based on clustering algorithms. We tend to find out the central nodes of the communities by centrality algorithms. Firstly, we define the distance between nodes using similarity. Then, a new centrality measuring the local density of nodes is put forward. Combining the independence of the centrality, the nodes in the network can be divided into four classes. Leveraging the product of centrality and independence, the central nodes in the network are easily identified. We also find that we can distinguish bridge nodes from central nodes using centrality and independence. This research designs a community detection algorithm combining centrality and independence. Simulation results reveal that our centrality is more effective than existing centralities in measuring local density and identifying community centers. Compared with other community detection algorithms, results prove the effectiveness of our algorithm. This paper just shows one application of independence of the centrality. There may be more useful applications of it.

This paper is concerned with the pseudo-randomicity of a discrete spatiotemporal system of the form

In this paper we propose an operational interpretation of general fuzzy measures. On the basis of this interpretation, we define the concept of coherence with respect to a partial information, and propose a rule of inference similar to the natural extension ⁷. We also suggest a definition of independence for fuzzy measures.

Due to their simple applicability score systems are in widespread use as a tool for decision making.

Unfortunately, as we all feel, they are somehow not apt to take into account interdependencies among the values which are input to them when trying to decide an actual application case; a drawback which is overcome by the more powerful probabilistic systems. In order to analyze which assumptions are inherent in score systems, we translate them as faithfully as possible into probabilistic systems thus making available the technical machinery of the latter for this analysis task.

Such a translation (as also given in¹) reveals indeed some properties of score systems, but leads to an exponential number of probabilistic rules, which rules it out for practical use. For this reason we also developed further translations into probabilistic systems, which keep the simplicity of a score system (i.e. they use the same amount of rules as the score system). Moreover, the resulting probabilistic systems show their structure more explicitly than score systems, and they are also open to the addition of further knowledge.

A new hierarchical uncertainty model for combining different evidence about a system of statistically independent random variable is studied in the paper. It is assumed that the first-order level of the model is represented by sets of lower and upper previsions (expectations) of random variables and the second-order level is represented by sets of lower and upper probabilities which can be viewed as confidence weights for interval-valued expectations of the first-order level. The model is rather general and allows us to compute probability bounds and "average" bounds for previsions of a function of random variables. A numerical example illustrates this model.

One of the most common performance measures in selection and management of projects is the Net Present Value (NPV). In the paper, we study a case when initial data about the NPV parameters (cash flows and the discount rate) are represented in the form of intervals supplied by experts. A method for computing the NPV based on using random set theory is proposed and three conditions of independence of the parameters are taken into account. Moreover, the imprecise Dirichlet model for obtaining more cautious bounds for the NPV is considered. Numerical examples illustrate the proposed approach for computing the NPV.

This paper presents the independence of fuzzy variables as well as its applications in fuzzy random optimization. First, the independence of fuzzy variables is defined based on the concept of marginal possibility distribution function, and a discussion about the relationship between the independent fuzzy variables and the noninteractive (unrelated) fuzzy variables is included. Second, we discuss some properties of the independent fuzzy variables, and establish the necessary and sufficient conditions for the independent fuzzy variables. Third, we propose the independence of fuzzy events, and deal with its fundamental properties. Finally, we apply the properties of the independent fuzzy variables to a class of fuzzy random programming problems to study their convexity.

In an expert system having a consistent set of linear constraints it is known that the Method of Tribus may be used to determine a probability distribution which exhibits maximised entropy. The method is extended here to include independence constraints (Accommodation).

The paper proceeds to discusses this extension, and its limitations, then goes on to advance a technique for determining a small set of independencies which can be added to the linear constraints required in a particular representation of an expert system called a causal network, so that the Maximum Entropy and Causal Networks methodologies give matching distributions (Emulation). This technique may also be applied in cases where no initial independencies are given and the linear constraints are incomplete, in order to provide an optimal ME fill-in for the missing information.

The belief structure resulting from the combination of consonant and independent marginal random sets is not, in general, consonant. Also, the complexity of such a structure grows exponentially with the number of combined random sets, making it quickly intractable for computations. In this paper, we propose a simple guaranteed consonant outer approximation of this structure. The complexity of this outer approximation does not increase with the number of marginal random sets (i.e., of dimensions), making it easier to handle in uncertainty propagation. Features and advantages of this outer approximation are then discussed, with the help of some illustrative examples.

We deal with conditional decomposable information measures, directly defined as functions on a suitable set of conditional events satisfying a class of axioms. For these general measures we introduce a notion of independence and study its main properties in order to compare it with classical definitions present in the literature. The particular case of Wiener-Shannon information measure is taken in consideration and the links between the provided independence for information measures and the independence for the underlying probability are analyzed.

This article is devoted to the propagation of families of variability intervals through multivariate functions comprising the semantics of confidence limits. At fixed confidence level, local random sets are defined whose aggregation admits the calculation of upper probabilities of events. In the multivariate case, a number of ways of combination is highlighted to encompass independence and unknown interaction using random set independence and Fréchet bounds. For all cases we derive formulas for the corresponding upper probabilities and elaborate how they relate. An example from structural mechanics is used to exemplify the method.

A notion of "quasi-universal product" for algebraic probability spaces is introduced as a generalization of Speicher's "universal product". It is proved that there exist only five quasi-universal products, namely, tensor product, free product, Boolean product, monotone product and anti-monotone product. This result means that, in a sense, there exist only five independences which have nice properties of "associativity" and "(quasi-)universality".

It is known that there are exactly five natural products, which are universal products fulfilling two normalization conditions simultaneously. We classify universal products without these extra conditions. We find a two-parameter deformation of the Boolean product, which we call (r, s)-products. Our main result states that, besides degnerate cases, these are the only new universal products. Furthermore, we introduce a GNS-construction for not necessarily positive linear functionals on algebras and study the GNS-construction for (r, s)-product functionals.

We present some new set and class theoretic independence results from ZFC and NBGC that are particularly simple and close to the primitives of membership and equality (see Secs. 4 and 5). They are shown to be equivalent to familiar small large cardinal hypotheses. We modify these independendent statements in order to give an example of a sentence in set theory with 5 quantifiers which is independent of ZFC (see Sec. 6). It is known that all 3 quantifier sentences are decided in a weak fragment of ZF without power set (see [4]).

We combine two notions in AECs, tameness and good λ-frames, and show that they together give a very well-behaved nonforking notion in all cardinalities. This helps to fill a longstanding gap in classification theory of tame AECs and increases the applicability of frames. Along the way, we prove a complete stability transfer theorem and uniqueness of limit models in these AECs.

We explore a notion of pseudofinite dimension, introduced by Hrushovski and Wagner, on an infinite ultraproduct of finite structures. Certain conditions on pseudofinite dimension are identified that guarantee simplicity or supersimplicity of the underlying theory, and that a drop in pseudofinite dimension is equivalent to forking. Under a suitable assumption, a measure-theoretic condition is shown to be equivalent to local stability. Many examples are explored, including vector spaces over finite fields viewed as 2-sorted finite structures, and homocyclic groups. Connections are made to products of sets in finite groups, in particular to word maps, and a generalization of Tao's Algebraic Regularity Lemma is noted.

We show that there is a $\beta$-model of second-order arithmetic in which the choice scheme holds, but the dependent choice scheme fails for a ${\mathrm{\Pi }}_2^1$-assertion, confirming a conjecture of Stephen Simpson. We obtain as a corollary that the Reflection Principle, stating that every formula reflects to a transitive set, can fail in models of ${\mathrm{\text{ZFC}}}^{-}$. This work is a rediscovery by the first two authors of a result obtained by the third author in [V. G. Kanovei, On descriptive forms of the countable axiom of choice, Investigations on nonclassical logics and set theory, Work Collect., Moscow, 3-136 (1979)].

Tests to determine the dependence or independence of random variables X and Y are well established. Recently, criteria based on reproducing kernel Hilbert spaces has received much attentions. They are developed in the setting of norm of Hilbert spaces. In this paper we propose tests in the setting of constraints of coefficients of functions. Some estimates of tests are constructed. In particular the error between the test of constrained covariance and the estimate is bounded.