Rainbow Connection Number of Graph Power and Graph Products

Rainbow connection number, rc(G), of a connected graph G is the minimum number of colors needed to color its edges so that every pair of vertices is connected by at least one path in which no two edges are colored the same (note that the coloring need not be proper). In this paper we study the rainbow connection number with respect to three important graph product operations (namely the Cartesian product, the lexicographic product and the strong product) and the operation of taking the power of a graph. In this direction, we show that if G is a graph obtained by applying any of the operations mentioned above on non-trivial graphs, then rc(G) a parts per thousand currency sign 2r(G) + c, where r(G) denotes the radius of G and . In general the rainbow connection number of a bridgeless graph can be as high as the square of its radius 1]. This is an attempt to identify some graph classes which have rainbow connection number very close to the obvious lower bound of diameter (and thus the radius). The bounds reported are tight up to additive constants. The proofs are constructive and hence yield polynomial time -factor approximation algorithms.

Surrogate Regret Bounds for Bipartite Ranking via Strongly Proper Losses

The problem of bipartite ranking, where instances are labeled positive or negative and the goal is to learn a scoring function that minimizes the probability of mis-ranking a pair of positive and negative instances (or equivalently, that maximizes the area under the ROC curve), has been widely studied in recent years. A dominant theoretical and algorithmic framework for the problem has been to reduce bipartite ranking to pairwise classification; in particular, it is well known that the bipartite ranking regret can be formulated as a pairwise classification regret, which in turn can be upper bounded using usual regret bounds for classification problems. Recently, Kotlowski et al. (2011) showed regret bounds for bipartite ranking in terms of the regret associated with balanced versions of the standard (non-pairwise) logistic and exponential losses. In this paper, we show that such (non-pairwise) surrogate regret bounds for bipartite ranking can be obtained in terms of a broad class of proper (composite) losses that we term as strongly proper. Our proof technique is much simpler than that of Kotlowski et al. (2011), and relies on properties of proper (composite) losses as elucidated recently by Reid and Williamson (2010, 2011) and others. Our result yields explicit surrogate bounds (with no hidden balancing terms) in terms of a variety of strongly proper losses, including for example logistic, exponential, squared and squared hinge losses as special cases. An important consequence is that standard algorithms minimizing a (non-pairwise) strongly proper loss, such as logistic regression and boosting algorithms (assuming a universal function class and appropriate regularization), are in fact consistent for bipartite ranking; moreover, our results allow us to quantify the bipartite ranking regret in terms of the corresponding surrogate regret. We also obtain tighter surrogate bounds under certain low-noise conditions via a recent result of Clemencon and Robbiano (2011).

Energy-efficient, delay-constrained, QoS-aware broadcast for cooperative wireless sensor networks

The problem of delay-constrained, energy-efficient broadcast in cooperative wireless networks is NP-complete. While centralised setting allows some heuristic solutions, designing heuristics in distributed implementation poses significant challenges. This is more so in wireless sensor networks (WSNs) where nodes are deployed randomly and topology changes dynamically due to node failure/join and environment conditions. This paper demonstrates that careful design of network infrastructure can achieve guaranteed delay bounds and energy-efficiency, and even meet quality of service requirements during broadcast. The paper makes three prime contributions. First, we present an optimal lower bound on energy consumption for broadcast that is tighter than what has been previously proposed. Next, iSteiner, a lightweight, distributed and deterministic algorithm for creation of network infrastructure is discussed. iPercolate is the algorithm that exploits this structure to cooperatively broadcast information with guaranteed delivery and delay bounds, while allowing real-time traffic to pass undisturbed.

High Temperatures Result in Smaller Nurseries which Lower Reproduction of Pollinators and Parasites in a Brood Site Pollination Mutualism

In a nursery pollination mutualism, we asked whether environmental factors affected reproduction of mutualistic pollinators, non-mutualistic parasites and seed production via seasonal changes in plant traits such as inflorescence size and within-tree reproductive phenology. We examined seasonal variation in reproduction in Ficus racemosa community members that utilise enclosed inflorescences called syconia as nurseries. Temperature, relative humidity and rainfall defined four seasons: winter; hot days, cold nights; summer and wet seasons. Syconium volumes were highest in winter and lowest in summer, and affected syconium contents positively across all seasons. Greater transpiration from the nurseries was possibly responsible for smaller syconia in summer. The 3-5 degrees C increase in mean temperatures between the cooler seasons and summer reduced fig wasp reproduction and increased seed production nearly two-fold. Yet, seed and pollinator progeny production were never negatively related in any season confirming the mutualistic fig-pollinator association across seasons. Non-pollinator parasites affected seed production negatively in some seasons, but had a surprisingly positive relationship with pollinators in most seasons. While within-tree reproductive phenology did not vary across seasons, its effect on syconium inhabitants varied with season. In all seasons, within-tree reproductive asynchrony affected parasite reproduction negatively, whereas it had a positive effect on pollinator reproduction in winter and a negative effect in summer. Seasonally variable syconium volumes probably caused the differential effect of within-tree reproductive phenology on pollinator reproduction. Within-tree reproductive asynchrony itself was positively affected by intra-tree variation in syconium contents and volume, creating a unique feedback loop which varied across seasons. Therefore, nursery size affected fig wasp reproduction, seed production and within-tree reproductive phenology via the feedback cycle in this system. Climatic factors affecting plant reproductive traits cause biotic relationships between plants, mutualists and parasites to vary seasonally and must be accorded greater attention, especially in the context of climate change.

Outer Bounds on the Secrecy Rate of the 2-User Symmetric Deterministic Interference Channel with Transmitter Cooperation

This paper derives outer bounds for the 2-user symmetric linear deterministic interference channel (SLDIC) with limited-rate transmitter cooperation and perfect secrecy constraints at the receivers. Five outer bounds are derived, under different assumptions of providing side information to receivers and partitioning the encoded message/output depending on the relative strength of the signal and the interference. The usefulness of these outer bounds is shown by comparing the bounds with the inner bound on the achievable secrecy rate derived by the authors in a previous work. Also, the outer bounds help to establish that sharing random bits through the cooperative link can achieve the optimal rate in the very high interference regime.

Relay Selection with Channel Probing in Sleep-Wake Cycling Wireless Sensor Networks

In geographical forwarding of packets in a large wireless sensor network (WSN) with sleep-wake cycling nodes, we are interested in the local decision problem faced by a node that has ``custody'' of a packet and has to choose one among a set of next-hop relay nodes to forward the packet toward the sink. Each relay is associated with a ``reward'' that summarizes the benefit of forwarding the packet through that relay. We seek a solution to this local problem, the idea being that such a solution, if adopted by every node, could provide a reasonable heuristic for the end-to-end forwarding problem. Toward this end, we propose a local relay selection problem consisting of a forwarding node and a collection of relay nodes, with the relays waking up sequentially at random times. At each relay wake-up instant, the forwarder can choose to probe a relay to learn its reward value, based on which the forwarder can then decide whether to stop (and forward its packet to the chosen relay) or to continue to wait for further relays to wake up. The forwarder's objective is to select a relay so as to minimize a combination of waiting delay, reward, and probing cost. The local decision problem can be considered as a variant of the asset selling problem studied in the operations research literature. We formulate the local problem as a Markov decision process (MDP) and characterize the solution in terms of stopping sets and probing sets. We provide results illustrating the structure of the stopping sets, namely, the (lower bound) threshold and the stage independence properties. Regarding the probing sets, we make an interesting conjecture that these sets are characterized by upper bounds. Through simulation experiments, we provide valuable insights into the performance of the optimal local forwarding and its use as an end-to-end forwarding heuristic.

Generalized Spatial Modulation in Large-Scale Multiuser MIMO Systems

Generalized spatial modulation (GSM) uses n(t) transmit antenna elements but fewer transmit radio frequency (RF) chains, n(rf). Spatial modulation (SM) and spatial multiplexing are special cases of GSM with n(rf) = 1 and n(rf) = n(t), respectively. In GSM, in addition to conveying information bits through n(rf) conventional modulation symbols (for example, QAM), the indices of the n(rf) active transmit antennas also convey information bits. In this paper, we investigate GSM for large-scale multiuser MIMO communications on the uplink. Our contributions in this paper include: 1) an average bit error probability (ABEP) analysis for maximum-likelihood detection in multiuser GSM-MIMO on the uplink, where we derive an upper bound on the ABEP, and 2) low-complexity algorithms for GSM-MIMO signal detection and channel estimation at the base station receiver based on message passing. The analytical upper bounds on the ABEP are found to be tight at moderate to high signal-to-noise ratios (SNR). The proposed receiver algorithms are found to scale very well in complexity while achieving near-optimal performance in large dimensions. Simulation results show that, for the same spectral efficiency, multiuser GSM-MIMO can outperform multiuser SM-MIMO as well as conventional multiuser MIMO, by about 2 to 9 dB at a bit error rate of 10(-3). Such SNR gains in GSM-MIMO compared to SM-MIMO and conventional MIMO can be attributed to the fact that, because of a larger number of spatial index bits, GSM-MIMO can use a lower-order QAM alphabet which is more power efficient.

Outer Bounds on the Sum Rate of the K-User MIMO Gaussian Interference Channel

This paper derives outer bounds on the sum rate of the K-user MIMO Gaussian interference channel (GIC). Three outer bounds are derived, under different assumptions of cooperation and providing side information to receivers. The novelty in the derivation lies in the careful selection of side information, which results in the cancellation of the negative differential entropy terms containing signal components, leading to a tractable outer bound. The overall outer bound is obtained by taking the minimum of the three outer bounds. The derived bounds are simplified for the MIMO Gaussian symmetric IC to obtain outer bounds on the generalized degrees of freedom (GDOF). The relative performance of the bounds yields insight into the performance limits of multiuser MIMO GICs and the relative merits of different schemes for interference management. These insights are confirmed by establishing the optimality of the bounds in specific cases using an inner bound on the GDOF derived by the authors in a previous work. It is also shown that many of the existing results on the GDOF of the GIC can be obtained as special cases of the bounds, e. g., by setting K = 2 or the number of antennas at each user to 1.

On the Bounds of Certain Maximal Linear Codes in a Projective Space

The set of all subspaces of F-q(n) is denoted by P-q(n). The subspace distance d(S)(X, Y) = dim(X) + dim(Y)-2dim(X boolean AND Y) defined on P-q(n) turns it into a natural coding space for error correction in random network coding. A subset of P-q(n) is called a code and the subspaces that belong to the code are called codewords. Motivated by classical coding theory, a linear coding structure can be imposed on a subset of P-q(n). Braun et al. conjectured that the largest cardinality of a linear code, that contains F-q(n), is 2(n). In this paper, we prove this conjecture and characterize the maximal linear codes that contain F-q(n).

Lower-Bound Axisymmetric Formulation for Geomechanics Problems Using Nonlinear Optimization

A lower-bound limit analysis formulation, by using two-dimensional finite elements, the three-dimensional Mohr-Coulomb yield criterion, and nonlinear optimization, has been given to deal with an axisymmetric geomechanics stability problem. The optimization was performed using an interior point method based on the logarithmic barrier function. The yield surface was smoothened (1) by removing the tip singularity at the apex of the pyramid in the meridian plane and (2) by eliminating the stress discontinuities at the corners of the yield hexagon in the pi-plane. The circumferential stress (sigma(theta)) need not be assumed. With the proposed methodology, for a circular footing, the bearing-capacity factors N-c, N-q, and N-gamma for different values of phi have been computed. For phi = 0, the variation of N-c with changes in the factor m, which accounts for a linear increase of cohesion with depth, has been evaluated. Failure patterns for a few cases have also been drawn. The results from the formulation provide a good match with the solutions available from the literature. (C) 2014 American Society of Civil Engineers.

Bearing capacity of circular footings over rock mass by using axisymmetric quasi lower bound finite element limit analysis

The ultimate bearing capacity of a circular footing, placed over rock mass, is evaluated by using the lower bound theorem of the limit analysis in conjunction with finite elements and nonlinear optimization. The generalized Hoek-Brown (HB) failure criterion, but by keeping a constant value of the exponent, alpha = 0.5, was used. The failure criterion was smoothened both in the meridian and pi planes. The nonlinear optimization was carried out by employing an interior point method based on the logarithmic barrier function. The results for the obtained bearing capacity were presented in a non-dimensional form for different values of GSI, m(i), sigma(ci)/(gamma b) and q/sigma(ci). Failure patterns were also examined for a few cases. For validating the results, computations were also performed for a strip footing as well. The results obtained from the analysis compare well with the data reported in literature. Since the equilibrium conditions are precisely satisfied only at the centroids of the elements, not everywhere in the domain, the obtained lower bound solution will be approximate not true. (C) 2015 Elsevier Ltd. All rights reserved.

Lower Bound Axisymmetric Limit Analysis Using Drucker-Prager Yield Cone and Simulation with Mohr-Coulomb Pyramid

This paper presents a lower bound limit analysis approach for solving an axisymmetric stability problem by using the Drucker-Prager (D-P) yield cone in conjunction with finite elements and nonlinear optimization. In principal stress space, the tip of the yield cone has been smoothened by applying the hyperbolic approximation. The nonlinear optimization has been performed by employing an interior point method based on the logarithmic barrier function. A new proposal has also been given to simulate the D-P yield cone with the Mohr-Coulomb hexagonal yield pyramid. For the sake of illustration, bearing capacity factors N-c, N-q and N-gamma have been computed, as a function of phi, both for smooth and rough circular foundations. The results obtained from the analysis compare quite well with the solutions reported from literature.

Bearing capacity factors for a conical footing using lower- and upper-bound finite elements limit analysis

Bearing capacity factors, N-c, N-q, and N-gamma, for a conical footing are determined by using the lower and upper bound axisymmetric formulation of the limit analysis in combination with finite elements and optimization. These factors are obtained in a bound form for a wide range of the values of cone apex angle (beta) and phi with delta = 0, 0.5 phi, and phi. The bearing capacity factors for a perfectly rough (delta = phi) conical footing generally increase with a decrease in beta. On the contrary, for delta = 0 degrees, the factors N-c and N-q reduce gradually with a decrease in beta. For delta = 0 degrees, the factor N-gamma for phi >= 35 degrees becomes a minimum for beta approximate to 90 degrees. For delta = 0 degrees, N-gamma for phi <= 30 degrees, as in the case of delta = phi, generally reduces with an increase in beta. The failure and nodal velocity patterns are also examined. The results compare well with different numerical solutions and centrifuge tests' data available from the literature.

An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas

We show here a 2(Omega(root d.log N)) size lower bound for homogeneous depth four arithmetic formulas. That is, we give an explicit family of polynomials of degree d on N variables (with N = d(3) in our case) with 0, 1-coefficients such that for any representation of a polynomial f in this family of the form f = Sigma(i) Pi(j) Q(ij), where the Q(ij)'s are homogeneous polynomials (recall that a polynomial is said to be homogeneous if all its monomials have the same degree), it must hold that Sigma(i,j) (Number of monomials of Q(ij)) >= 2(Omega(root d.log N)). The above mentioned family, which we refer to as the Nisan-Wigderson design-based family of polynomials, is in the complexity class VNP. Our work builds on the recent lower bound results 1], 2], 3], 4], 5] and yields an improved quantitative bound as compared to the quasi-polynomial lower bound of 6] and the N-Omega(log log (N)) lower bound in the independent work of 7].

Status of the MSSM Higgs sector using global analysis and direct search bounds, and future prospects at the High Luminosity LHC

In this paper, we search for the regions of the phenomenological minimal supersymmetric standard model (pMSSM) parameter space where one can expect to have moderate Higgs mixing angle (alpha) with relatively light (up to 600 GeV) additional Higgses after satisfying the current LHC data. We perform a global fit analysis using most updated data (till December 2014) from the LHC and Tevatron experiments. The constraints coming from the precision measurements of the rare b-decays B-s -> mu(+)mu(-) and b -> s gamma are also considered. We find that low M-A(less than or similar to 350) and high tan beta(greater than or similar to 25) regions are disfavored by the combined effect of the global analysis and flavor data. However, regions with Higgs mixing angle alpha similar to 0.1-0.8 are still allowed by the current data. We then study the existing direct search bounds on the heavy scalar/pseudoscalar (H/A) and charged Higgs boson (H-+/-) masses and branchings at the LHC. It has been found that regions with low to moderate values of tan beta with light additional Higgses (mass <= 600 GeV) are unconstrained by the data, while the regions with tan beta > 20 are excluded considering the direct search bounds by the LHC-8 data. The possibility to probe the region with tan beta <= 20 at the high luminosity run of LHC are also discussed, giving special attention to the H -> hh, H/A -> t (t) over bar and H/A -> tau(+)tau(-) decay modes.