Algorithms for Colouring Random k-colourable Graphs

The k-colouring problem is to colour a given k-colourable graph with k colours. This problem is known to be NP-hard even for fixed k greater than or equal to 3. The best known polynomial time approximation algorithms require n(delta) (for a positive constant delta depending on k) colours to colour an arbitrary k-colourable n-vertex graph. The situation is entirely different if we look at the average performance of an algorithm rather than its worst-case performance. It is well known that a k-colourable graph drawn from certain classes of distributions can be ii-coloured almost surely in polynomial time. In this paper, we present further results in this direction. We consider k-colourable graphs drawn from the random model in which each allowed edge is chosen independently with probability p(n) after initially partitioning the vertex set into ii colour classes. We present polynomial time algorithms of two different types. The first type of algorithm always runs in polynomial time and succeeds almost surely. Algorithms of this type have been proposed before, but our algorithms have provably exponentially small failure probabilities. The second type of algorithm always succeeds and has polynomial running time on average. Such algorithms are more useful and more difficult to obtain than the first type of algorithms. Our algorithms work as long as p(n) greater than or equal to n(-1+is an element of) where is an element of is a constant greater than 1/4.

Probability Distribution of the Eigenvalues of the Random String Equation

The probability distribution of the eigenvalues of a second-order stochastic boundary value problem is considered. The solution is characterized in terms of the zeros of an associated initial value problem. It is further shown that the probability distribution is related to the solution of a first-order nonlinear stochastic differential equation. Solutions of this equation based on the theory of Markov processes and also on the closure approximation are presented. A string with stochastic mass distribution is considered as an example for numerical work. The theoretical probability distribution functions are compared with digital simulation results. The comparison is found to be reasonably good.

Narrowband random excitation of a limit cycle system

The response of the Van der Pol oscillator to stationary narrowband Gaussian excitation is considered. The central frequency of excitation is taken to be in the neighborhood of the system limit cycle frequency. The solution is obtained using a non-Gaussian closure approximation on the probability density function of the response. The validity of the solution is examined with the help of a stochastic stability analysis. Solution based on Stratonovich''s quasistatic averaging technique is also obtained. The comparison of the theoretical solutions with the digital simulations shows that the theoretical estimates are reasonably good.

Rocking response of rectangular rigid blocks under random noise base excitations

The response of a rigid rectangular block resting on a rigid foundation and acted upon simultaneously by a horizontal and a vertical random white-noise excitation is considered. In the equation of motion, the energy dissipation is modeled through a viscous damping term. Under the assumption that the body does not topple, the steady-state joint probability density function of the rotation and the rotational velocity is obtained using the Fokker-Planck equation approach. Closed form solution is obtained for a specific combination of system parameters. A more general but approximate solution to the joint probability density function based on the method of equivalent non-linearization is also presented. Further, the problem of overturning of the block is approached in the framework of the diffusion methods for first passage failure studies. The overturning of the block is deemed incipient when the response trajectories in the phase plane cross the separatrix of the conservative unforced system. Expressions for the moments of first passage time are obtained via a series solution to the governing generalized Pontriagin-Vitt equations. Numerical results illustra- tive of the theoretical solutions are presented and their validity is examined through limited amount of digital simulations.

On a Ratio of Functions of Exponential Random Variables and Some Applications

Consider L independent and identically distributed exponential random variables (r.vs) X-1, X-2 ,..., X-L and positive scalars b(1), b(2) ,..., b(L). In this letter, we present the probability density function (pdf), cumulative distribution function and the Laplace transform of the pdf of the composite r.v Z = (Sigma(L)(j=1) X-j)(2) / (Sigma(L)(j=1) b(j)X(j)). We show that the r.v Z appears in various communication systems such as i) maximal ratio combining of signals received over multiple channels with mismatched noise variances, ii)M-ary phase-shift keying with spatial diversity and imperfect channel estimation, and iii) coded multi-carrier code-division multiple access reception affected by an unknown narrow-band interference, and the statistics of the r.v Z derived here enable us to carry out the performance analysis of such systems in closed-form.

A critical re-examination and a revised phase diagram of La1-xSrxCoO3

We report the results of a comprehensive study on dc magnetization, ac susceptibility, and the magnetotransport properties of the La1-xSrxCoO3(0 <= x <= 0.5) system. At higher Sr doping (x >= 0.18), the system exhibits Brillouin-like field cooled magnetization (M-FC). However, for x < 0.18, the system exhibits a kink in the M-FC, a peak at the intermediate field in the thermoremnant magnetization and a non-saturating tendency in the M-H plot that all point towards the characteristic of spin glass behavior. More interestingly, dc magnetization studies for x < 0.18 do not suggest the existence of ferromagnetic correlation that can give rise to an irreversible line in the spin glass regime. The ac susceptibility study for x > 0.2 exhibits apparently no frequency dependent peak shift around the ferromagnetic transition region. However, a feeble signature of glassiness is verified by studying the frequency dependent shoulder position in chi `' (T) and the memory effect below the Curie temperature. But, for x < 0.18, the ac susceptibility study exhibits a considerable frequency dependent peak shift, time dependent memory effect, and the characteristic spin relaxation time scale tau(0) similar to 10(-13) s. The reciprocal susceptibility versus temperature plot adheres to Curie-Weiss behavior and does not provide any signature of preformed ferromagnetic clusters well above the Curie temperature. The magnetotransport study reveals a cross over from metallic to semiconducting-like behavior for x <= 0.18. On the semiconducting side, the system exhibits a large value of magnetoresistance (upto 75%) towards low temperature and it is strongly connected to the spin dependent part of the random potential distribution in the spin glass phase. Based on the above observations, we have reconstructed a new magnetic phase diagram and characterized each phase with associated properties.

Monte-Carlo estimation of time-dependent statistical characteristics of random dynamical systems

The problem of estimating the time-dependent statistical characteristics of a random dynamical system is studied under two different settings. In the first, the system dynamics is governed by a differential equation parameterized by a random parameter, while in the second, this is governed by a differential equation with an underlying parameter sequence characterized by a continuous time Markov chain. We propose, for the first time in the literature, stochastic approximation algorithms for estimating various time-dependent process characteristics of the system. In particular, we provide efficient estimators for quantities such as the mean, variance and distribution of the process at any given time as well as the joint distribution and the autocorrelation coefficient at different times. A novel aspect of our approach is that we assume that information on the parameter model (i.e., its distribution in the first case and transition probabilities of the Markov chain in the second) is not available in either case. This is unlike most other work in the literature that assumes availability of such information. Also, most of the prior work in the literature is geared towards analyzing the steady-state system behavior of the random dynamical system while our focus is on analyzing the time-dependent statistical characteristics which are in general difficult to obtain. We prove the almost sure convergence of our stochastic approximation scheme in each case to the true value of the quantity being estimated. We provide a general class of strongly consistent estimators for the aforementioned statistical quantities with regular sample average estimators being a specific instance of these. We also present an application of the proposed scheme on a widely used model in population biology. Numerical experiments in this framework show that the time-dependent process characteristics as obtained using our algorithm in each case exhibit excellent agreement with exact results. (C) 2010 Elsevier Inc. All rights reserved.

Effect of dynamical asymmetry on the viscosity of a random copolymer melt

The variation of the viscosity as a function of the sequence distribution in an A-B random copolymer melt is determined. The parameters that characterize the random copolymer are the fraction of A monomers f, the parameter lambda which determines the correlation in the monomer identities along a chain and the Flory chi parameter chi(F) which determines the strength of the enthalpic repulsion between monomers of type A and B. For lambda>0, there is a greater probability of finding like monomers at adjacent positions along the chain, and for lambda<0 unlike monomers are more likely to be adjacent to each other. The traditional Markov model for the random copolymer melt is altered to remove ultraviolet divergences in the equations for the renormalized viscosity, and the phase diagram for the modified model has a binary fluid type transition for lambda>0 and does not exhibit a phase transition for lambda<0. A mode coupling analysis is used to determine the renormalization of the viscosity due to the dependence of the bare viscosity on the local concentration field. Due to the dissipative nature of the coupling. there are nonlinearities both in the transport equation and in the noise correlation. The concentration dependence of the transport coefficient presents additional difficulties in the formulation due to the Ito-Stratonovich dilemma, and there is some ambiguity about the choice of the concentration to be used while calculating the noise correlation. In the Appendix, it is shown using a diagrammatic perturbation analysis that the Ito prescription for the calculation of the transport coefficient, when coupled with a causal discretization scheme, provides a consistent formulation that satisfies stationarity and the fluctuation dissipation theorem. This functional integral formalism is used in the present analysis, and consistency is verified for the present problem as well. The upper critical dimension for this type of renormaliaation is 2, and so there is no divergence in the viscosity in the vicinity of a critical point. The results indicate that there is a systematic dependence of the viscosity on lambda and chi(F). The fluctuations tend to increase the viscosity for lambda<0, and decrease the viscosity for lambda>0, and an increase in chi(F) tends to decrease the viscosity. (C) 1996 American Institute of Physics.

Low electric field, easily reversible electrical set and reset processes in a Ge15Te83Si2 glass for phase change memory applications

We report here an easily reversible set-reset process in a new Ge15Te83Si2 glass that could be a promising candidate for phase change random access memory applications. The I-V characteristics of the studied sample show a comparatively low threshold electric field (E-th) of 7.3 kV/cm. Distinct differences in the type of switching behavior are achieved by means of controlling the on state current. It enables the observation of a threshold type for less than 0.7 mA beyond memory type (set) switching. The set and reset processes have been achieved with a similar magnitude of 1 mA, and with a triangular current pulse for the set process and a short duration rectangular pulse of 10 msec width for the reset operation. Further, a self-resetting effect is seen in this material upon excitation with a saw-tooth/square pulse, and their response of leading and trailing edges are discussed. About 6.5 x 10(4) set-reset cycles have been undertaken without any damage to the device. (C) 2011 American Institute of Physics. doi: 10.1063/1.3574659]

Lasing in active, sub-mean-free path-sized systems with dense, random, weak scatterers

We report enhanced emission and gain narrowing in Rhodamine 590 perchlorate dye in an aqueous suspension of polystyrene microspheres. A systematic experimental study of the threshold condition for and the gain narrowing of the stimulated emission over a wide range of dye concentrations and scatterer number densities showed several interesting features, even though the transport mean free path far exceeded the system size. The conventional diffusive-reactive approximation to radiative transfer in an inhomogeneously illuminated random amplifying medium, which is valid for a transport mean-free path much smaller than the system size, is clearly inapplicable here. We propose a new probabilistic approach for the present case of dense, random, weak scatterers involving the otherwise rare and ignorable sub-mean-free-path scatterings, now made effective by the high gain in the medium, which is consistent: with experimentally observed features. (C) 1997 Optical Society of America.

Muon-spin rotation spectra in the mixed phase of high-T-c superconductors: Thermal fluctuations and disorder effects

We study muon-spin rotation (mu SR) spectra in the mixed phase of highly anisotropic layered superconductors, specifically Bi2+xSr2-xCaCu2O8+delta (BSCCO), by modeling the fluid and solid phases of pancake Vortices using liquid-state and density functional methods. The role of thermal fluctuations in causing motional narrowing of mu SR line shapes is quantified in terms of a first-principles theory of the flux-lattice melting transition. The effects of random point pinning are investigated using a replica treatment of liquid-state correlations and a replicated density functional theory. Our results indicate that motional narrowing in the pure system, although substantial, cannot account for the remarkably small linewidths obtained experimentally at relatively high fields and low temperatures. We find that satisfactory agreement with the mu SR data for BSCCO in this regime can be obtained through the ansatz that this ''phase'' is characterized by frozen short-range positional correlations reflecting the structure of the liquid just above the melting transition. This proposal is consistent with recent suggestions of a ''pinned liquid'' or ''glassy'' state of pancake Vortices in the presence of pinning disorder. Our results for the high-temperature liquid phase indicate that measurable linewidths may be obtained in this phase as a consequence of density inhomogeneities induced by the pinning disorder. The results presented here comprise a unified, first-principles theoretical treatment of mu SR spectra in highly anisotropic layered superconductors in terms of a controlled set of approximations. [S0163-1829(99)08033-9].

Phase separation in a simple model with dynamical asymmetry

We perform computer simulations of a Cahn-Hilliard model of phase separation that has dynamical asymmetry between the two coexisting phases. The dynamical asymmetry is incorporated by considering a mobility function that is order parameter dependent. Simulations of this model reveal morphological features similar to those observed in viscoelastic phase separation. In the early stages, the minority phase domains form a percolating structure that shrinks with time, eventually leading to the formation of disconnected regions that are characterized by the presence of random interfaces as well as isolated droplets. The domains grow as L(t)similar to t(1/3) in the very late stages. Although dynamical scaling is violated in the area shrinking regime, it is restored at late times. However, the form of the scaling function is found to depend on the extent of dynamical asymmetry. [S1063-651X(99)12101-9].

Performance analysis of the random early detection algorithm

In this article we consider a finite queue with its arrivals controlled by the random early detection algorithm. This is one of the most prominent congestion avoidance schemes in the Internet routers. The aggregate arrival stream from the population of transmission control protocol sources is locally considered stationary renewal or Markov modulated Poisson process with general packet length distribution. We study the exact dynamics of this queue and provide the stability and the rates of convergence to the stationary distribution and obtain the packet loss probability and the waiting time distribution. Then we extend these results to a two traffic class case with each arrival stream renewal. However, computing the performance indices for this system becomes computationally prohibitive. Thus, in the latter half of the article, we approximate the dynamics of the average queue length process asymptotically via an ordinary differential equation. We estimate the error term via a diffusion approximation. We use these results to obtain approximate transient and stationary performance of the system. Finally, we provide some computational examples to show the accuracy of these approximations.

Theory and Algorithms for Hop-Count-Based Localization with Random Geometric Graph Models of Dense Sensor Networks

Wireless sensor networks can often be viewed in terms of a uniform deployment of a large number of nodes in a region of Euclidean space. Following deployment, the nodes self-organize into a mesh topology with a key aspect being self-localization. Having obtained a mesh topology in a dense, homogeneous deployment, a frequently used approximation is to take the hop distance between nodes to be proportional to the Euclidean distance between them. In this work, we analyze this approximation through two complementary analyses. We assume that the mesh topology is a random geometric graph on the nodes; and that some nodes are designated as anchors with known locations. First, we obtain high probability bounds on the Euclidean distances of all nodes that are h hops away from a fixed anchor node. In the second analysis, we provide a heuristic argument that leads to a direct approximation for the density function of the Euclidean distance between two nodes that are separated by a hop distance h. This approximation is shown, through simulation, to very closely match the true density function. Localization algorithms that draw upon the preceding analyses are then proposed and shown to perform better than some of the well-known algorithms present in the literature. Belief-propagation-based message-passing is then used to further enhance the performance of the proposed localization algorithms. To our knowledge, this is the first usage of message-passing for hop-count-based self-localization.

Fast acoustic likelihood computation using low-rank matrix approximation

Acoustic modeling using mixtures of multivariate Gaussians is the prevalent approach for many speech processing problems. Computing likelihoods against a large set of Gaussians is required as a part of many speech processing systems and it is the computationally dominant phase for LVCSR systems. We express the likelihood computation as a multiplication of matrices representing augmented feature vectors and Gaussian parameters. The computational gain of this approach over traditional methods is by exploiting the structure of these matrices and efficient implementation of their multiplication.In particular, we explore direct low-rank approximation of the Gaussian parameter matrix and indirect derivation of low-rank factors of the Gaussian parameter matrix by optimum approximation of the likelihood matrix. We show that both the methods lead to similar speedups but the latter leads to far lesser impact on the recognition accuracy. Experiments on a 1138 word vocabulary RM1 task using Sphinx 3.7 system show that, for a typical case the matrix multiplication approach leads to overall speedup of 46%. Both the low-rank approximation methods increase the speedup to around 60%, with the former method increasing the word error rate (WER) from 3.2% to 6.6%, while the latter increases the WER from 3.2% to 3.5%.