VC dimension and inner product space induced by Bayesian networks

Bayesian networks are graphical tools used to represent a high-dimensional probability distribution. They are used frequently in machine learning and many applications such as medical science. This paper studies whether the concept classes induced by a Bayesian network can be embedded into a low-dimensional inner product space. We focus on two-label classification tasks over the Boolean domain. For full Bayesian networks and almost full Bayesian networks with n variables, we show that VC dimension and the minimum dimension of the inner product space induced by them are 2ⁿ-1. Also, for each Bayesian network we show that if the network constructed from by removing X_n satisfies either (i) is a full Bayesian network with n-1 variables, i is the number of parents of X_n, and i<n-1 or (ii) is an almost full Bayesian network, the set of all parents of X_n PA_n={X₁,X₂,X_n3,…,X_ni} and 2i<n-1. Our results in the paper are useful in evaluating the VC dimension and the minimum dimension of the inner product space of concept classes induced by other Bayesian networks.     

Broadcasting algorithms in radio networks with unknown topology

In this paper we present new randomized and deterministic algorithms for the classical problem of broadcasting in radio networks with unknown topology. We consider directed n-node radio networks with specified eccentricity D (maximum distance from the source node to any other node). Bar-Yehuda et al. presented an algorithm that for any n-node radio network with eccentricity D completes the broadcasting in time, with high probability. This result is almost optimal, since as it has been shown by Kushilevitz and Mansour and Alon et al., every randomized algorithm requires Ω(Dlog(n/D)+log²n) expected time to complete broadcasting.Our first main result closes the gap between the lower and upper bound: we describe an optimal randomized broadcasting algorithm whose running time complexity is , with high probability. In particular, we obtain a randomized algorithm that completes broadcasting in any n-node radio network in time , with high probability.The main source of our improvement is a better “selecting sequence” used by the algorithm that brings some stronger property and improves the broadcasting time. Two types of “selecting sequences” are considered: randomized and deterministic ones. The algorithm with a randomized sequence is easier (more intuitive) to analyze but both randomized and deterministic sequences give algorithms of the same asymptotic complexity.Next, we demonstrate how to apply our approach to deterministic broadcasting, and describe a deterministic oblivious algorithm that completes broadcasting in time , which improves upon best known algorithms in this case. The fastest previously known algorithm had the broadcasting time of , it was non-oblivious and significantly more complicated; our algorithm can be seen as a natural extension of our randomized algorithm. In this part of the paper we assume that each node knows the eccentricity D.Finally, we show how our randomized broadcasting algorithm can be used to improve the randomized complexity of the gossiping problem.     

Optical grooming with grooming ratio nine

Grooming uniform all-to-all traffic in optical ring networks with grooming ratio C requires the determination of graph decompositions of the complete graph into subgraphs each having at most C edges. The drop cost of such a grooming is the total number of vertices of nonzero degree in these subgraphs, and the grooming is optimal when the drop cost is minimum. The minimum drop cost is determined for grooming ratio 9. Previously this bound was shown to be met when with two exceptions and eleven additional possible exceptions for n, and also when with one exception and one possible exception for n. In this paper it is shown that the bound is met for all with four exceptions for n∈{8,11,14,17} and one possible exception for n=20. Using this result, it is further shown that when and n is sufficiently large, the bound is also met.     

A new characterization of projections of quadrics in finite projective spaces of even characteristic

We will classify, up to linear representations, all geometries fully embedded in an affine space with the property that for every antiflag {p,L} of the geometry there are either 0, α, or q lines through p intersecting L. An example of such a geometry with α=2 is the following well known geometry . Let Q_n+1 be a nonsingular quadric in a finite projective space , n≥3, q even. We project Q_n+1 from a point r∉Q_n+1, distinct from its nucleus if n+1 is even, on a hyperplane not through r. This yields a partial linear space whose points are the points p of , such that the line 〈p,r〉 is a secant to Q_n+1, and whose lines are the lines of which contain q such points. This geometry is fully embedded in an affine subspace of and satisfies the antiflag property mentioned. As a result of our classification theorem we will give a new characterization theorem of this geometry.     

Cycles in 2-connected graphs

Let be a class of graphs on n vertices. For an integer c, let be the smallest integer such that if G is a graph in with more than edges, then G contains a cycle of length more than c. A classical result of Erdös and Gallai is that if is the class of all simple graphs on n vertices, then . The result is best possible when n-1 is divisible by c-1, in view of the graph consisting of copies of K_c all having exactly one vertex in common. Woodall improved the result by giving best possible bounds for the remaining cases when n-1 is not divisible by c-1, and conjectured that if is the class of all 2-connected simple graphs on n vertices, thenwhere , 2tc/2, is the number of edges in the graph obtained from K_c+1-t by adding n-(c+1-t) isolated vertices each joined to the same t vertices of K_c+1-t. By using a result of Woodall together with an edge-switching technique, we confirm Woodall's conjecture in this paper.     

More Efficient Parallel Totally Monotone Matrix Searching

We give a parallel algorithm for computing all row minima in a totally monotonen × nmatrix which is simpler and more work efficient than previous polylog-time algorithms. It runs inO(lg n lg lg n) time doingwork on aCRCW PRAM, inO(lg n(lg lg n)²) time doingwork on aCREW PRAM, and intime doingwork on anEREW PRAM. Since finding the row minima of a totally monotone matrix has been shown to be fundamental in the efficient solution of a host of geometric and combinatorial problems, our algorithm leads directly to improved parallel solutions of many algorithms in terms of their work efficiency.     

Normalizers of non-split Cartan subgroups, modular curves, and the class number one problem

Let be the open non-cuspidal locus of the modular curve associated to the normalizer of a non-split Cartan subgroup of level n. As Serre pointed out, an imaginary quadratic field of class number one gives rise to an integral point on for suitably chosen n. In this note, we give a genus formula for the modular curves and we give three new solutions to the class number one problem using the modular curves for n=16,20,21. These are the only such modular curves of genus ?2 that had not yet been exploited.     

Erdős–Ko–Rado theorems for permutations and set partitions

Let Sym([n]) denote the collection of all permutations of [n]={1,…,n}. Suppose is a family of permutations such that any two of its elements (when written in its cycle decomposition) have at least t cycles in common. We prove that for sufficiently large n, with equality if and only if is the stabilizer of t fixed points. Similarly, let denote the collection of all set partitions of [n] and suppose is a family of set partitions such that any two of its elements have at least t blocks in common. It is proved that, for sufficiently large n, with equality if and only if consists of all set partitions with t fixed singletons, where B_n is the nth Bell number.     

On the irrationality of factorial series III

In this paper we derive some irrationality and linear independence results for series of the form where is either a non-negative integer sequence with υ_n = o(log n/log log n) or a non-decreasing integer sequence with .     

On some algebraic difference equations in , related to families of conics or cubics: generalization of the Lyness' sequences

In this paper and in a forthcoming one, we study difference equations in of the types (2)(4)(6) which are linked to families of conics, cubics and quartics, respectively. These equations generalize Lyness' one u_n+2u_n=a+u_n+1 studied in several papers, whose behavior was completely elucidated in [G. Bastien, M. Rogalski, in press] through methods which are transposed in the present paper for the study of (1) and (2), and in the forthcoming one for (3). In particular we prove in the present paper a form of chaotic behavior for solutions of difference equations (1) and (2), and find all the possible periods for these solutions.     

Higher order log-concavity in Euler’s difference table

For 0≤k≤n, let be the entries in Euler’s difference table and let . Dumont and Randrianarivony showed equals the number of permutations on [n] whose fixed points are contained in {1,2,…,k}. Rakotondrajao found a combinatorial interpretation of the number in terms of k-fixed-points-permutations of [n]. We show that for any n≥1, the sequence is essentially 2-log-concave and reverse ultra log-concave.     

Pointwise characterizations of Besov and Triebel–Lizorkin spaces and quasiconformal mappings

In this paper, the authors characterize, in terms of pointwise inequalities, the classical Besov spaces and Triebel–Lizorkin spaces for all s∈(0,1) and p,q∈(n/(n+s),∞], both in Rn and in the metric measure spaces enjoying the doubling and reverse doubling properties. Applying this characterization, the authors prove that quasiconformal mappings preserve on Rn for all s∈(0,1) and q∈(n/(n+s),∞]. A metric measure space version of the above morphism property is also established.     

Problems arising from jackknifing the estimate of a Kaplan-Meier integral

Stute and Wang (1994) considered the problem of estimating the integral S^θ = ∫ θ dF, based on a possibly censored sample from a distribution F, where θ is an F-integrable function. They proposed a Kaplan-Meier integral to approximate S^θ and derived an explicit formula for the delete-1 jackknife estimate . differs from only when the largest observation, X_(n), is not censored (δ_(n) = 1 and next-to-the-largest observation, X_(n-1), is censored (δ_(n-1) = 0). In this note, it will pointed out that when X_(n) is censored is based on a defective distribution, and therefore can badly underestimate . We derive an explicit formula for the delete-2 jackknife estimate . However, on comparing the expressions of and , their difference is negligible. To improve the performance of and , we propose a modified estimator according to Efron (1980). Simulation results demonstrate that is much less biased than and and .     

On the layered nearest neighbour estimate, the bagged nearest neighbour estimate and the random forest method in regression and classification

Let be identically distributed random vectors in R^d, independently drawn according to some probability density. An observation is said to be a layered nearest neighbour (LNN) of a point if the hyperrectangle defined by and contains no other data points. We first establish consistency results on , the number of LNN of . Then, given a sample of independent identically distributed random vectors from R^d×R, one may estimate the regression function by the LNN estimate , defined as an average over the Y_i’s corresponding to those which are LNN of . Under mild conditions on r, we establish the consistency of towards 0 as n→∞, for almost all and all p≥1, and discuss the links between r_n and the random forest estimates of Breiman (2001) [8]. We finally show the universal consistency of the bagged (bootstrap-aggregated) nearest neighbour method for regression and classification.     

On the complexity of submodular function minimisation on diamonds

Let (L;?,?) be a finite lattice and let n be a positive integer. A function f:Lⁿ→R is said to be submodular if for all . In this article we study submodular functions when L is a diamond. Given oracle access to f we are interested in finding such that as efficiently as possible. We establish

• • 

  a min–max theorem, which states that the minimum of the submodular function is equal to the maximum of a certain function defined over a certain polyhedron; and

• • 

  a good characterisation of the minimisation problem, i.e., we show that given an oracle for computing a submodular f:Ln→Z and an integer m such that , there is a proof of this fact which can be verified in time polynomial in n and ; and

• • 

  a pseudopolynomial-time algorithm for the minimisation problem, i.e., given an oracle for computing a submodular f:Ln→Z one can find in time bounded by a polynomial in n and .

     

Unconditional constants and polynomial inequalities

If P is a polynomial on R^m of degree at most n, given by , and P_n(R^m) is the space of such polynomials, then we define the polynomial |P| by . Now if is a convex set, we define the norm on P_n(R^m), and then we investigate the inequality providing sharp estimates on for some specific spaces of polynomials. These ’s happen to be the unconditional constants of the canonical bases of the considered spaces.     

An endpoint space–time estimate for the Schrödinger equation

We obtain endpoint estimates for the Schrödinger operator f→eitΔf in with initial data f in the homogeneous Sobolev space . The exponents and regularity index satisfy and . For n=2 we prove the estimates in the range q>16/5, and for n?3 in the range q>2+4/(n+1).     

On the size of the symmetry group of a perfect code

It is shown that for every nonlinear perfect code C of length n and rank r with n−log(n+1)+1≤r≤n−1, where denotes the group of symmetries of C. This bound considerably improves a bound of Malyugin.     

Perfect packings with complete graphs minus an edge

Let denote the graph obtained from K_r by deleting one edge. We show that for every integer r≥4 there exists an integer n₀=n₀(r) such that every graph G whose order n≥n₀ is divisible by r and whose minimum degree is at least contains a perfect -packing, i.e. a collection of disjoint copies of which covers all vertices of G. Here is the critical chromatic number of . The bound on the minimum degree is best possible and confirms a conjecture of Kawarabayashi for large n.