Random-Restart Reactive Tabu Search Algorithm for Detection in Large-MIMO Systems

We present a low-complexity algorithm based on reactive tabu search (RTS) for near maximum likelihood (ML) detection in large-MIMO systems. The conventional RTS algorithm achieves near-ML performance for 4-QAM in large-MIMO systems. But its performance for higher-order QAM is far from ML performance. Here, we propose a random-restart RTS (R3TS) algorithm which achieves significantly better bit error rate (BER) performance compared to that of the conventional RTS algorithm in higher-order QAM. The key idea is to run multiple tabu searches, each search starting with a random initial vector and choosing the best among the resulting solution vectors. A criterion to limit the number of searches is also proposed. Computer simulations show that the R3TS algorithm achieves almost the ML performance in 16 x 16 V-BLAST MIMO system with 16-QAM and 64-QAM at significantly less complexities than the sphere decoder. Also, in a 32 x 32 V-BLAST MIMO system, the R3TS performs close to ML lower bound within 1.6 dB for 16-QAM (128 bps/Hz), and within 2.4 dB for 64-QAM (192 bps/Hz) at 10(-3) BER.

Temperature dependent free energy surface of polymer folding from equilibrium and quench studies

Langevin dynamics simulation studies have been employed to calculate the temperature dependent free energy surface and folding characteristics of a 500 monomer long linear alkane (polyethylene) chain with a realistic interaction potential. Both equilibrium and temperature quench simulation studies have been carried out. Using the shape anisotropy parameter (S) of the folded molecule as the order parameter, we find a weakly first order phase transition between the high-temperature molten globule and low-temperature rodlike crystalline states separated by a small barrier of the order of k(B)T. Near the melting temperature (580 K), we observe an intriguing intermittent fluctuation with pronounced ``1/f noise characteristics'' between these two states with large difference in shape and structure. We have also studied the possibilities of different pathways of folding to states much below the melting point. At 300 K starting from the all-trans linear configuration, the chain folds stepwise into a very regular fourfold crystallite with very high shape anisotropy. Whereas, when quenched from a high temperature (900 K) random coil regime, we identify a two step transition from the random coiled state to a molten globulelike state and, further, to a anisotropic rodlike state. The trajectory reveals an interesting coupling between the two order parameters, namely, radius of gyration (R-g) and the shape anisotropy parameter (S). The rodlike final state of the quench trajectory is characterized by lower shape anisotropy parameter and significantly larger number of gauche defects as compared to the final state obtained through equilibrium simulation starting from all-trans linear chain. The quench study shows indication of a nucleationlike pathway from the molten globule to the rodlike state involving an underlying rugged energy landscape. (C) 2010 American Institute of Physics. doi:10.1063/1.3509398]

Modelling multiple disulphide loop containing polypeptides by random conformation generation. The test cases of α-conotoxin GI and edothelin I

A general procedure for arriving at 3-D models of disulphiderich olypeptide systems based on the covalent cross-link constraints has been developed. The procedure, which has been coded as a computer program, RANMOD, assigns a large number of random, permitted backbone conformations to the polypeptide and identifies stereochemically acceptable structures as plausible models based on strainless disulphide bridge modelling. Disulphide bond modelling is performed using the procedure MODIP developed earlier, in connection with the choice of suitable sites where disulphide bonds could be engineered in proteins (Sowdhamini,R., Srinivasan,N., Shoichet,B., Santi,D.V., Ramakrishnan,C. and Balaram,P. (1989) Protein Engng, 3, 95-103). The method RANMOD has been tested on small disulphide loops and the structures compared against preferred backbone conformations derived from an analysis of putative disulphide subdatabase and model calculations. RANMOD has been applied to disulphiderich peptides and found to give rise to several stereochemically acceptable structures. The results obtained on the modelling of two test cases, a-conotoxin GI and endothelin I, are presented. Available NMR data suggest that such small systems exhibit conformational heterogeneity in solution. Hence, this approach for obtaining several distinct models is particularly attractive for the study of conformational excursions.

Normal mode sound propagation in an ocean with random narrow-band surface waves

Normal mode sound propagation in an isovelocity ocean with random narrow-band surface waves is considered, assuming the root-mean-square wave height to be small compared to the acoustic wavelength. Nonresonant interaction among the normal modes is studied straightforward perturbation technique. The more interesting case of resonant interaction is investigated using the method of multiple scales to obtain a pair of stochastic coupled amplitude equations which are solved using the Peano-Baker expansion technique. Equations for the spatial evolution of the first and second moments of the mode amplitudes are also derived and solved. It is shown that, irrespective of the initial conditions, the mean values of the mode amplitudes tend to zero asymptotically with increasing range, the mean-square amplitudes tend towards a state of equipartition of energy, and the total energy of the modes is conserved.

On infinitesimal σ-fields generated by random processes

It is proved that the infinitesimal look-ahead and look-back σ-fields of a random process disagree at atmost countably many time instants.

On the Nash-Williams′ Lemma in Graph Reconstruction Theory

A generalization of Nash-Williams′ lemma is proved for the Structure of m-uniform null (m − k)-designs. It is then applied to various graph reconstruction problems. A short combinatorial proof of the edge reconstructibility of digraphs having regular underlying undirected graphs (e.g., tournaments) is given. A type of Nash-Williams′ lemma is conjectured for the vertex reconstruction problem.

Random sequential multilayer deposition of different‐sized k mers on a one dimensional infinite substrate

Kinetics of random sequential, irreversible multilayer deposition of macromolecules of two different sizes on a one dimensional infinite lattice is analyzed at the mean field level. A formal solution for the corresponding rate equation is obtained. The Jamming limits and the distribution of gaps of exact sizes are discussed. In the absence of screening, the jamming limits are shown to be the same for all the layers. A detailed analysis for the components differing by one monomer unit is presented. The small and large time behaviors and the dependence of the individual jamming limits of the k mers and (k−1) mers on k and the rate parameters are analyzed.

A Shapley Value-Based Approach to Discover Influential Nodes in Social Networks

Our study concerns an important current problem, that of diffusion of information in social networks. This problem has received significant attention from the Internet research community in the recent times, driven by many potential applications such as viral marketing and sales promotions. In this paper, we focus on the target set selection problem, which involves discovering a small subset of influential players in a given social network, to perform a certain task of information diffusion. The target set selection problem manifests in two forms: 1) top-k nodes problem and 2) lambda-coverage problem. In the top-k nodes problem, we are required to find a set of k key nodes that would maximize the number of nodes being influenced in the network. The lambda-coverage problem is concerned with finding a set of k key nodes having minimal size that can influence a given percentage lambda of the nodes in the entire network. We propose a new way of solving these problems using the concept of Shapley value which is a well known solution concept in cooperative game theory. Our approach leads to algorithms which we call the ShaPley value-based Influential Nodes (SPINs) algorithms for solving the top-k nodes problem and the lambda-coverage problem. We compare the performance of the proposed SPIN algorithms with well known algorithms in the literature. Through extensive experimentation on four synthetically generated random graphs and six real-world data sets (Celegans, Jazz, NIPS coauthorship data set, Netscience data set, High-Energy Physics data set, and Political Books data set), we show that the proposed SPIN approach is more powerful and computationally efficient. Note to Practitioners-In recent times, social networks have received a high level of attention due to their proven ability in improving the performance of web search, recommendations in collaborative filtering systems, spreading a technology in the market using viral marketing techniques, etc. It is well known that the interpersonal relationships (or ties or links) between individuals cause change or improvement in the social system because the decisions made by individuals are influenced heavily by the behavior of their neighbors. An interesting and key problem in social networks is to discover the most influential nodes in the social network which can influence other nodes in the social network in a strong and deep way. This problem is called the target set selection problem and has two variants: 1) the top-k nodes problem, where we are required to identify a set of k influential nodes that maximize the number of nodes being influenced in the network and 2) the lambda-coverage problem which involves finding a set of influential nodes having minimum size that can influence a given percentage lambda of the nodes in the entire network. There are many existing algorithms in the literature for solving these problems. In this paper, we propose a new algorithm which is based on a novel interpretation of information diffusion in a social network as a cooperative game. Using this analogy, we develop an algorithm based on the Shapley value of the underlying cooperative game. The proposed algorithm outperforms the existing algorithms in terms of generality or computational complexity or both. Our results are validated through extensive experimentation on both synthetically generated and real-world data sets.

Computation of restoration of ligand response in the random kinetics of a prostate cancer cell signaling pathway

Mutation and/or dysfunction of signaling proteins in the mitogen activated protein kinase (MAPK) signal transduction pathway are frequently observed in various kinds of human cancer. Consistent with this fact, in the present study, we experimentally observe that the epidermal growth factor (EGF) induced activation profile of MAP kinase signaling is not straightforward dose-dependent in the PC3 prostate cancer cells. To find out what parameters and reactions in the pathway are involved in this departure from the normal dose-dependency, a model-based pathway analysis is performed. The pathway is mathematically modeled with 28 rate equations yielding those many ordinary differential equations (ODE) with kinetic rate constants that have been reported to take random values in the existing literature. This has led to us treating the ODE model of the pathways kinetics as a random differential equations (RDE) system in which the parameters are random variables. We show that our RDE model captures the uncertainty in the kinetic rate constants as seen in the behavior of the experimental data and more importantly, upon simulation, exhibits the abnormal EGF dose-dependency of the activation profile of MAP kinase signaling in PC3 prostate cancer cells. The most likely set of values of the kinetic rate constants obtained from fitting the RDE model into the experimental data is then used in a direct transcription based dynamic optimization method for computing the changes needed in these kinetic rate constant values for the restoration of the normal EGF dose response. The last computation identifies the parameters, i.e., the kinetic rate constants in the RDE model, that are the most sensitive to the change in the EGF dose response behavior in the PC3 prostate cancer cells. The reactions in which these most sensitive parameters participate emerge as candidate drug targets on the signaling pathway. (C) 2011 Elsevier Ireland Ltd. All rights reserved.

New Approximation Algorithms for Minimum Cycle Bases of Graphs

We consider the problem of computing an approximate minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. Although in most such applications any cycle basis can be used, a low weight cycle basis often translates to better performance and/or numerical stability. Despite the fact that the problem can be solved exactly in polynomial time, we design approximation algorithms since the performance of the exact algorithms may be too expensive for some practical applications. We present two new algorithms to compute an approximate minimum cycle basis. For any integer k >= 1, we give (2k - 1)-approximation algorithms with expected running time O(kmn(1+2/k) + mn((1+1/k)(omega-1))) and deterministic running time O(n(3+2/k) ), respectively. Here omega is the best exponent of matrix multiplication. It is presently known that omega < 2.376. Both algorithms are o(m(omega)) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Theta(m(omega) ) bound. We also present a 2-approximation algorithm with expected running time O(M-omega root n log n), a linear time 2-approximation algorithm for planar graphs and an O(n(3)) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.

Central Limit Theorem for truncated heavy tailed Banach valued random vectors

In this paper the question of the extent to which truncated heavy tailed random vectors, taking values in a Banach space, retain the characteristic features of heavy tailed random vectors, is answered from the point of view of the central limit theorem.

Localization of light in coherently amplifying random media

We derive and analyze the statistics of reflection coefficient of light backscattered coherently from an amplifying and disordered optical medium modeled by a spatially random refractive index having a uniform imaginary part in one dimension. We find enhancement of reflected intensity owing to a synergy between wave confinement by Anderson localization and coherent amplification by the active medium. This is not the same as that due to enhanced optical path lengths expected from photon diffusion in the random active medium. Our study is relevant to the physical realizability of a mirrorless laser by photon confinement due to Anderson localization.

Probing the inter-tube transport in aligned and random multiwall carbon nanotubes

The temperature and magnetic field dependence of conductivity has been used to probe the inter-tube transport in multiwall carbon nanotubes (MWNTs). The scanning electron microscopy images show highly aligned and random distribution of MWNTs. The conductivity in aligned carbon nanotube (ACNT) and random carbon nanotube (RCNT) samples at low temperature follows T-1/2 (at T < 8 K) and T-3/4 (at T > 8 K) dependence in accordance with the weak localization and electron-electron (e-e) interaction model. The values of diffusion coefficient in ACNT and RCNT are 0.25 x 10(-2) and 0.71 x 10(-2) cm(2) s(-1), respectively, indicating that larger number of inter-tube junctions in later enhances the bulk transport. The positive magnetoconductance (MC) data in both samples show that the weak localization contribution is dominant. However, the saturation of MC at higher fields and lower temperatures indicate that e-e interaction is quite significant in RCNT. The T-3/4 and T-1/2 dependence of inelastic scattering length (l(in)) in ACNT and RCNT samples show that the inelastic e-e scattering is more important in aligned tubes. (C) 2011 American Institute of Physics. doi:10.1063/1.3552911]