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.

Entanglement entropy from the holographic stress tensor

We consider entanglement entropy in the context of gauge/gravity duality for conformal field theories in even dimensions. The holographic prescription due to Ryu and Takayanagi (RT) leads to an equation describing how the entangling surface extends into the bulk geometry. We show that setting to zero, the timetime component of the Brown-York stress tensor evaluated on the co-dimension 1 entangling surface, leads to the same equation. By considering a spherical entangling surface as an example, we observe that the Euclidean actionmethods in AdS/CFT will lead to the RT area functional arising as a counterterm needed to regularize the stress tensor. We present arguments leading to a justification for the minimal area prescription.

ENTANGLEMENT ENTROPY FROM SURFACE TERMS IN GENERAL RELATIVITY

Entanglement entropy in local quantum field theories is typically ultraviolet divergent due to short distance effects in the neighborhood of the entangling region. In the context of gauge/gravity duality, we show that surface terms in general relativity are able to capture this entanglement entropy. In particular, we demonstrate that for 1+1-dimensional (1 + 1d) conformal field theories (CFTs) at finite temperature whose gravity dual is Banados-Teitelboim-Zanelli (BTZ) black hole, the Gibbons-Hawking-York term precisely reproduces the entanglement entropy which can be computed independently in the field theory.

On generalized gravitational entropy, squashed cones and holography

We consider generalized gravitational entropy in various higher derivative theories of gravity dual to four dimensional CFTs using the recently proposed regularization of squashed cones. We derive the universal terms in the entanglement entropy for spherical and cylindrical surfaces. This is achieved by constructing the Fefferman-Graham expansion for the leading order metrics for the bulk geometry and evaluating the generalized gravitational entropy. We further show that the Wald entropy evaluated in the bulk geometry constructed for the regularized squashed cones leads to the correct universal parts of the entanglement entropy for both spherical and cylindrical entangling surfaces. We comment on the relation with the Iyer-Wald formula for dynamical horizons relating entropy to a Noether charge. Finally we show how to derive the entangling surface equation in Gauss-Bonnet holography.

3D flat holography: entropy and logarithmic corrections

We compute the leading corrections to the Bekenstein-Hawking entropy of the Flat Space Cosmological (FSC) solutions in 3D flat spacetimes, which are the flat analogues of the BTZ black holes in AdS(3). The analysis is done by a computation of density of states in the dual 2D Galilean Conformal Field Theory and the answer obtained by this matches with the limiting value of the expected result for the BTZ inner horizon entropy as well as what is expected for a generic thermodynamic system. Along the way, we also develop other aspects of holography of 3D flat spacetimes.

Generative Maximum Entropy Learning for Multiclass Classification

Maximum entropy approach to classification is very well studied in applied statistics and machine learning and almost all the methods that exists in literature are discriminative in nature. In this paper, we introduce a maximum entropy classification method with feature selection for large dimensional data such as text datasets that is generative in nature. To tackle the curse of dimensionality of large data sets, we employ conditional independence assumption (Naive Bayes) and we perform feature selection simultaneously, by enforcing a `maximum discrimination' between estimated class conditional densities. For two class problems, in the proposed method, we use Jeffreys (J) divergence to discriminate the class conditional densities. To extend our method to the multi-class case, we propose a completely new approach by considering a multi-distribution divergence: we replace Jeffreys divergence by Jensen-Shannon (JS) divergence to discriminate conditional densities of multiple classes. In order to reduce computational complexity, we employ a modified Jensen-Shannon divergence (JS(GM)), based on AM-GM inequality. We show that the resulting divergence is a natural generalization of Jeffreys divergence to a multiple distributions case. As far as the theoretical justifications are concerned we show that when one intends to select the best features in a generative maximum entropy approach, maximum discrimination using J-divergence emerges naturally in binary classification. Performance and comparative study of the proposed algorithms have been demonstrated on large dimensional text and gene expression datasets that show our methods scale up very well with large dimensional datasets.

Higher spin entanglement entropy from CFT

We consider free fermion and free boson CFTs in two dimensions, deformed by a chemical potential mu for the spin-three current. For the CFT on the infinite spatial line, we calculate the finite temperature entanglement entropy of a single interval perturbatively to second order in mu in each of the theories. We find that the result in each case is given by the same non-trivial function of temperature and interval length. Remarkably, we further obtain the same formula using a recent Wilson line proposal for the holographic entanglement entropy, in holomorphically factorized form, associated to the spin-three black hole in SL(3, R) x SL(3, R) Chern-Simons theory. Our result suggests that the order mu(2) correction to the entanglement entropy may be universal for W-algebra CFTs with spin-three chemical potential, and constitutes a check of the holographic entanglement entropy proposal for higher spin theories of gravity in AdS(3).