An (O)over-bar(m(2)n) randomized algorithm to compute a minimum cycle basis of a directed graph

We consider the problem of computing a minimum cycle basis in a directed graph G. The input to this problem is a directed graph whose arcs have positive weights. In this problem a {- 1, 0, 1} incidence vector is associated with each cycle and the vector space over Q 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 weights of the cycles is minimum is called a minimum cycle basis of G. The current fastest algorithm for computing a minimum cycle basis in a directed graph with m arcs and n vertices runs in O(m(w+1)n) time (where w < 2.376 is the exponent of matrix multiplication). If one allows randomization, then an (O) over tilde (m(3)n) algorithm is known for this problem. In this paper we present a simple (O) over tilde (m(2)n) randomized algorithm for this problem. The problem of computing a minimum cycle basis in an undirected graph has been well-studied. 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 the graph. The fastest known algorithm for computing a minimum cycle basis in an undirected graph runs in O(m(2)n + mn(2) logn) time and our randomized algorithm for directed graphs almost matches this running time.

Statistical properties of entropy-consuming fluctuations in jammed states of laponite suspensions: Fluctuation relations and generalized Gumbel distribution

We report a universal large deviation behavior of spatially averaged global injected power just before the rejuvenation of the jammed state formed by an aging suspension of laponite clay under an applied stress. The probability distribution function (PDF) of these entropy consuming strongly non-Gaussian fluctuations follow an universal large deviation functional form described by the generalized Gumbel (GG) distribution like many other equilibrium and nonequilibrium systems with high degree of correlations but do not obey the Gallavotti-Cohen steady-state fluctuation relation (SSFR). However, far from the unjamming transition (for smaller applied stresses) SSFR is satisfied for both Gaussian as well as non-Gaussian PDF. The observed slow variation of the mean shear rate with system size supports a recent theoretical prediction for observing GG distribution.

Transport in nanoporous zeolites: Relationships between sorbate size, entropy, and diffusivity

Molecular dynamics simulations have been performed on monatomic sorbates confined within zeolite NaY to obtain the dependence of entropy and self-diffusivity on the sorbate diameter. Previously, molecular dynamics simulations by Santikary and Yashonath J. Phys. Chem. 98, 6368 (1994)], theoretical analysis by Derouane J. Catal. 110, 58 (1988)] as well as experiments by Kemball Adv. Catal. 2, 233 (1950)] found that certain sorbates in certain adsorbents exhibit unusually high self-diffusivity. Experiments showed that the loss of entropy for certain sorbates in specific adsorbents was minimum. Kemball suggested that such sorbates will have high self-diffusivity in these adsorbents. Entropy of the adsorbed phase has been evaluated from the trajectory information by two alternative methods: two-phase and multiparticle expansion. The results show that anomalous maximum in entropy is also seen as a function of the sorbate diameter. Further, the experimental observation of Kemball that minimum loss of entropy is associated with maximum in self-diffusivity is found to be true for the system studied here. A suitably scaled dimensionless self-diffusivity shows an exponential dependence on the excess entropy of the adsorbed phase, analogous to excess entropy scaling rules seen in many bulk and confined fluids. The two trajectory-based estimators for the entropy show good semiquantitative agreement and provide some interesting microscopic insights into entropy changes associated with confinement.

On maximum entropy and minimum KL-divergence optimization by Grobner basis methods

In this paper we study constrained maximum entropy and minimum divergence optimization problems, in the cases where integer valued sufficient statistics exists, using tools from computational commutative algebra. We show that the estimation of parametric statistical models in this case can be transformed to solving a system of polynomial equations. We give an implicit description of maximum entropy models by embedding them in algebraic varieties for which we give a Grobner basis method to compute it. In the cases of minimum KL-divergence models we show that implicitization preserves specialization of prior distribution. This result leads us to a Grobner basis method to embed minimum KL-divergence models in algebraic varieties. (C) 2012 Elsevier Inc. All rights reserved.

Bond Graph Modeling for Energy-Harvesting Wireless Sensor Networks

Researchers can use bond graph modeling, a tool that takes into account the energy conservation principle, to accurately assess the dynamic behavior of wireless sensor networks on a continuous basis.

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.

Factor graph based joint detection/decoding for LDPC coded large-MIMO systems

In this paper, we employ message passing algorithms over graphical models to jointly detect and decode symbols transmitted over large multiple-input multiple-output (MIMO) channels with low density parity check (LDPC) coded bits. We adopt a factor graph based technique to integrate the detection and decoding operations. A Gaussian approximation of spatial interference is used for detection. This serves as a low complexity joint detection/decoding approach for large dimensional MIMO systems coded with LDPC codes of large block lengths. This joint processing achieves significantly better performance than the individual detection and decoding scheme.

Role of Specific Cations and Water Entropy on the Stability of Branched DNA Motif Structures

DNA three-way junctions (TWJs) are important intermediates in various cellular processes and are the simplest of a family of branched nucleic acids being considered as scaffolds for biomolecular nanotechnology. Branched nucleic acids are stabilized by divalent cations such as Mg2+, presumably due to condensation and neutralization of the negatively charged DNA backbone. However, electrostatic screening effects point to more complex solvation dynamics and a large role of interfacial waters in thermodynamic stability. Here, we report extensive computer simulations in explicit water and salt on a model TWJ and use free energy calculations to quantify the role of ionic character and strength on stability. We find that enthalpic stabilization of the first and second hydration shells by Mg2+ accounts for 1/3 and all of the free energy gain in 50% and pure MgCl2 solutions, respectively. The more distorted DNA molecule is actually destabilized in pure MgCl2 compared to pure NaCl. Notably, the first shell, interfacial waters have very low translational and rotational entropy (i.e., mobility) compared to the bulk, an entropic loss that is overcompensated by increased enthalpy from additional electrostatic interactions with Mg2+. In contrast, the second hydration shell has anomalously high entropy as it is trapped between an immobile and bulklike layer. The nonmonotonic entropic signature and long-range perturbations of the hydration shells to Mg2+ may have implications in the molecular recognition of these motifs. For example, we find that low salt stabilizes the parallel configuration of the three-way junction, whereas at normal salt we find antiparallel configurations deduced from the NMR. We use the 2PT analysis to follow the thermodynamics of this transition and find that the free energy barrier is dominated by entropic effects that result from the decreased surface area of the antiparallel form which has a smaller number of low entropy waters in the first monolayer.

Exploiting the Structure of the Constraint Graph for Efficient Points-to Analysis

Points-to analysis is a key compiler analysis. Several memory related optimizations use points-to information to improve their effectiveness. Points-to analysis is performed by building a constraint graph of pointer variables and dynamically updating it to propagate more and more points-to information across its subset edges. So far, the structure of the constraint graph has been only trivially exploited for efficient propagation of information, e.g., in identifying cyclic components or to propagate information in topological order. We perform a careful study of its structure and propose a new inclusion-based flow-insensitive context-sensitive points-to analysis algorithm based on the notion of dominant pointers. We also propose a new kind of pointer-equivalence based on dominant pointers which provides significantly more opportunities for reducing the number of pointers tracked during the analysis. Based on this hitherto unexplored form of pointer-equivalence, we develop a new context-sensitive flow-insensitive points-to analysis algorithm which uses incremental dominator update to efficiently compute points-to information. Using a large suite of programs consisting of SPEC 2000 benchmarks and five large open source programs we show that our points-to analysis is 88% faster than BDD-based Lazy Cycle Detection and 2x faster than Deep Propagation. We argue that our approach of detecting dominator-based pointer-equivalence is a key to improve points-to analysis efficiency.

Quantum phases of dimerized and frustrated Heisenberg spin chains with s=1/2, 1 and 3/2: an entanglement entropy and fidelity study

We study here different regions in phase diagrams of the spin-1/2, spin-1 and spin-3/2 one-dimensional antiferromagnetic Heisenberg systems with frustration (next-nearest-neighbor interaction J(2)) and dimerization (delta). In particular, we analyze the behaviors of the bipartite entanglement entropy and fidelity at the gapless to gapped phase transitions and across the lines separating different phases in the J(2)-delta plane. All the calculations in this work are based on numerical exact diagonalizations of finite systems.

Representing a cubic graph as the intersection graph of axis-parallel boxes in three dimensions

We show that every graph of maximum degree 3 can be represented as the intersection graph of axis parallel boxes in three dimensions, that is, every vertex can be mapped to an axis parallel box such that two boxes intersect if and only if their corresponding vertices are adjacent. In fact, we construct a representation in which any two intersecting boxes just touch at their boundaries. Further, this construction can be realized in linear time.

On the secret key capacity of the harary graph PIN model

A pairwise independent network (PIN) model consists of pairwise secret keys (SKs) distributed among m terminals. The goal is to generate, through public communication among the terminals, a group SK that is information-theoretically secure from an eavesdropper. In this paper, we study the Harary graph PIN model, which has useful fault-tolerant properties. We derive the exact SK capacity for a regular Harary graph PIN model. Lower and upper bounds on the fault-tolerant SK capacity of the Harary graph PIN model are also derived.

Entanglement entropy in higher derivative holography

We consider holographic entanglement entropy in higher derivative gravity theories. Recently Lewkowycz and Maldacena 1] have provided a method to derive the equations for the entangling surface from first principles. We use this method to compute the entangling surface in four derivative gravity. Certain interesting differences compared to the two derivative case are pointed out. For Gauss-Bonnet gravity, we show that in the regime where this method is applicable, the resulting equations coincide with proposals in the literature as well as with what follows from considerations of the stress tensor on the entangling surface. Finally we demonstrate that the area functional in Gauss-Bonnet holography arises as a counterterm needed to make the Euclidean action free of power law divergences.

Entropy of quantum states: Ambiguities

The von Neumann entropy of a generic quantum state is not unique unless the state can be uniquely decomposed as a sum of extremal or pure states. As pointed out to us by Sorkin, this happens if the GNS representation (of the algebra of observables in some quantum state) is reducible, and some representations in the decomposition occur with non-trivial degeneracy. This non-unique entropy can occur at zero temperature. We will argue elsewhere in detail that the degeneracies in the GNS representation can be interpreted as an emergent broken gauge symmetry, and play an important role in the analysis of emergent entropy due to non-Abelian anomalies. Finally, we establish the analogue of an H-theorem for this entropy by showing that its evolution is Markovian, determined by a stochastic matrix.