Detecting symmetry in scalar fields using augmented extremum graphs

Visualizing symmetric patterns in the data often helps the domain scientists make important observations and gain insights about the underlying experiment. Detecting symmetry in scalar fields is a nascent area of research and existing methods that detect symmetry are either not robust in the presence of noise or computationally costly. We propose a data structure called the augmented extremum graph and use it to design a novel symmetry detection method based on robust estimation of distances. The augmented extremum graph captures both topological and geometric information of the scalar field and enables robust and computationally efficient detection of symmetry. We apply the proposed method to detect symmetries in cryo-electron microscopy datasets and the experiments demonstrate that the algorithm is capable of detecting symmetry even in the presence of significant noise. We describe novel applications that use the detected symmetry to enhance visualization of scalar field data and facilitate their exploration.

Universal binding energy relation for cleaved and structurally relaxed surfaces

The universal binding energy relation (UBER), derived earlier to describe the cohesion between two rigid atomic planes, does not accurately capture the cohesive properties when the cleaved surfaces are allowed to relax. We suggest a modified functional form of UBER that is analytical and at the same time accurately models the properties of surfaces relaxed during cleavage. We demonstrate the generality as well as the validity of this modified UBER through first-principles density functional theory calculations of cleavage in a number of crystal systems. Our results show that the total energies of all the relaxed surfaces lie on a single (universal) energy surface, that is given by the proposed functional form which contains an additional length-scale associated with structural relaxation. This functional form could be used in modelling the cohesive zones in crack growth simulation studies. We find that the cohesive law (stress-displacement relation) differs significantly in the case where cracked surfaces are allowed to relax, with lower peak stresses occurring at higher displacements.

`Universal' recession curves and their geomorphological interpretation

The study of recession flows offers fundamental insights into basin hydrological processes and, in particular, into the collective behavior of the governing dominant subsurface flows and properties. We use here an existing geomorphological interpretation of recession dynamics, which links the exponent in the classic recession curve -dQ/dt - kQ(alpha) to the geometric properties of the time-varying drainage network to study the general properties of recession curves across a wide variety of river basins. In particular, we show how the parameter k depends on the initial soil moisture state of the basin and can be made to explicitly depend on an index discharge, representative of initial sub-subsurface storage. Through this framework we obtain a non-dimensional, event-independent, recession curve. We subsequently quantify the variability of k across different basins on the basis of their geometry, and, by rescaling, collapse curves from different events and basins to obtain a generalized, or `universal', recession curve. Finally, we analyze the resulting normalized recession curves and explain their universal characteristics, lending further support to the notion that the statistical properties of observed recession curves bear the signature of the geomorphological structure of the networks producing them. (C) 2014 Elsevier Ltd. All rights reserved.

Universal Conductance Fluctuations as a direct probe to valley coherence and universality class of disordered graphene

We demonstrate that the universal conductance fluctuations (UCF) can be used as a direct probe to study the valley quantum states in disordered graphene. The UCF magnitude in graphene is suppressed by a factor of four at high carrier densities where the short-range disorder essentially breaks the valley degeneracy of the K and K' valleys, leading to a density dependent crossover of symmetry class from symplectic near the Dirac point to orthogonal at high densities.

Achieving universal rural energy access in india: A low carbon pathway

India's energy challenges are three pronged: presence of majority energy poor lacking access to modern energy; need for expanding energy system to bridge this access gap as well as to meet the requirements of fast-growing economy; and the desire to partner with global economies in mitigating the threat of climate change. The presence of 364 million people without access to electricity and 726 million relying on biomass for cooking out of a total rural population of 809 million indicate the seriousness of challenge. In this paper, we discuss an innovative approach to address this challenge, which intends to take advantage of recent global developments and untapped capabilities possessed by India. Intention is to use climate change mitigation imperative as a stimulus and adopt a public-private-partnership-driven ‘business model' with innovative institutional, regulatory, financing, and delivery mechanisms. Some of the innovations are: creation of rural energy access authorities within the government system as leadership institutions; establishment of energy access funds to enable transitions from the regime of "investment/fuel subsidies" to "incentive-linked" delivery of energy services; integration of business principles to facilitate affordable and equitable energy sales and carbon trade; and treatment of entrepreneurs as implementation targets. This proposal targets 100% access to modern energy carriers by 2030 through a judicious mix of conventional and biomass energy systems with an investment of US$35 billion over 20 years. The estimated annual cost of universal energy access is about US$9 billion for a GHG mitigation potential of 213Tg CO2e at an abatement cost of US$41/tCO2e. It is a win-win situation for all stakeholders. Households benefit from modern energy carriers at affordable cost; entrepreneurs run profitable energy enterprises; carbon markets have access to CERs; the government has the satisfaction of securing energy access to rural people; and globally, there is a benefit of climate change mitigation.

Raman spectroscopy explores molecular structural signatures of hidden materials in depth: Universal Multiple Angle Raman Spectroscopy

Non-invasive 3D imaging in materials and medical research involves methodologies such as X-ray imaging, MRI, fluorescence and optical coherence tomography, NIR absorption imaging, etc., providing global morphological/density/absorption changes of the hidden components. However, molecular information of such buried materials has been elusive. In this article we demonstrate observation of molecular structural information of materials hidden/buried in depth using Raman scattering. Typically, Raman spectroscopic observations are made at fixed collection angles, such as, 906, 1356, and 1806, except in spatially offset Raman scattering (SORS) (only back scattering based collection of photons) and transmission techniques. Such specific collection angles restrict the observations of Raman signals either from or near the surface of the materials. Universal Multiple Angle Raman Spectroscopy (UMARS) presented here employs the principle of (a) penetration depth of photons and then diffuse propagation through non-absorbing media by multiple scattering and (b) detection of signals from all the observable angles.

Universal power law in crossover from integrability to quantum chaos

We study models of interacting fermions in one dimension to investigate the crossover from integrability to nonintegrability, i.e., quantum chaos, as a function of system size. Using exact diagonalization of finite-sized systems, we study this crossover by obtaining the energy level statistics and Drude weight associated with transport. Our results reinforce the idea that for system size L -> infinity nonintegrability sets in for an arbitrarily small integrability-breaking perturbation. The crossover value of the perturbation scales as a power law similar to L-eta when the integrable system is gapless. The exponent eta approximate to 3 appears to be robust to microscopic details and the precise form of the perturbation. We conjecture that the exponent in the power law is characteristic of the random matrix ensemble describing the nonintegrable system. For systems with a gap, the crossover scaling appears to be faster than a power law.

A constant factor approximation algorithm for boxicity of circular arc graphs

The boxicity (resp. cubicity) of a graph G(V, E) is the minimum integer k such that G can be represented as the intersection graph of axis parallel boxes (resp. cubes) in R-k. Equivalently, it is the minimum number of interval graphs (resp. unit interval graphs) on the vertex set V, such that the intersection of their edge sets is E. The problem of computing boxicity (resp. cubicity) is known to be inapproximable, even for restricted graph classes like bipartite, co-bipartite and split graphs, within an O(n(1-epsilon))-factor for any epsilon > 0 in polynomial time, unless NP = ZPP. For any well known graph class of unbounded boxicity, there is no known approximation algorithm that gives n(1-epsilon)-factor approximation algorithm for computing boxicity in polynomial time, for any epsilon > 0. In this paper, we consider the problem of approximating the boxicity (cubicity) of circular arc graphs intersection graphs of arcs of a circle. Circular arc graphs are known to have unbounded boxicity, which could be as large as Omega(n). We give a (2 + 1/k) -factor (resp. (2 + log n]/k)-factor) polynomial time approximation algorithm for computing the boxicity (resp. cubicity) of any circular arc graph, where k >= 1 is the value of the optimum solution. For normal circular arc (NCA) graphs, with an NCA model given, this can be improved to an additive two approximation algorithm. The time complexity of the algorithms to approximately compute the boxicity (resp. cubicity) is O(mn + n(2)) in both these cases, and in O(mn + kn(2)) = O(n(3)) time we also get their corresponding box (resp. cube) representations, where n is the number of vertices of the graph and m is its number of edges. Our additive two approximation algorithm directly works for any proper circular arc graph, since their NCA models can be computed in polynomial time. (C) 2014 Elsevier B.V. All rights reserved.

2-Connecting outerplanar graphs without blowing up the pathwidth

Given a connected outerplanar graph G of pathwidth p, we give an algorithm to add edges to G to get a supergraph of G, which is 2-vertex-connected, outerplanar and of pathwidth O(p). This settles an open problem raised by Biedl 1], in the context of computing minimum height planar straight line drawings of outerplanar graphs, with their vertices placed on a two-dimensional grid. In conjunction with the result of this paper, the constant factor approximation algorithm for this problem obtained by Biedl 1] for 2-vertex-connected outerplanar graphs will work for all outer planar graphs. (C) 2014 Elsevier B.V. All rights reserved.

Parameterized Algorithms for MAX COLORABLE INDUCED SUBGRAPH Problem on Perfect Graphs

We address the parameterized complexity ofMaxColorable Induced Subgraph on perfect graphs. The problem asks for a maximum sized q-colorable induced subgraph of an input graph G. Yannakakis and Gavril IPL 1987] showed that this problem is NP-complete even on split graphs if q is part of input, but gave a n(O(q)) algorithm on chordal graphs. We first observe that the problem is W2]-hard parameterized by q, even on split graphs. However, when parameterized by l, the number of vertices in the solution, we give two fixed-parameter tractable algorithms. The first algorithm runs in time 5.44(l) (n+#alpha(G))(O(1)) where #alpha(G) is the number of maximal independent sets of the input graph. The second algorithm runs in time q(l+o()l())n(O(1))T(alpha) where T-alpha is the time required to find a maximum independent set in any induced subgraph of G. The first algorithm is efficient when the input graph contains only polynomially many maximal independent sets; for example split graphs and co-chordal graphs. The running time of the second algorithm is FPT in l alone (whenever T-alpha is a polynomial in n), since q <= l for all non-trivial situations. Finally, we show that (under standard complexitytheoretic assumptions) the problem does not admit a polynomial kernel on split and perfect graphs in the following sense: (a) On split graphs, we do not expect a polynomial kernel if q is a part of the input. (b) On perfect graphs, we do not expect a polynomial kernel even for fixed values of q >= 2.

Vertex Cover Gets Faster and Harder on Low Degree Graphs

The problem of finding an optimal vertex cover in a graph is a classic NP-complete problem, and is a special case of the hitting set question. On the other hand, the hitting set problem, when asked in the context of induced geometric objects, often turns out to be exactly the vertex cover problem on restricted classes of graphs. In this work we explore a particular instance of such a phenomenon. We consider the problem of hitting all axis-parallel slabs induced by a point set P, and show that it is equivalent to the problem of finding a vertex cover on a graph whose edge set is the union of two Hamiltonian Paths. We show the latter problem to be NP-complete, and also give an algorithm to find a vertex cover of size at most k, on graphs of maximum degree four, whose running time is 1.2637(k) n(O(1)).

Universal correction to higher spin entanglement entropy

We consider conformal field theories in 1 + 1 dimensions with W-algebra symmetries, deformed by a chemical potential mu for the spin-three current. We show that the order mu(2) correction to the Renyi and entanglement entropies of a single interval in the deformed theory, on the infinite spatial line and at finite temperature, is universal. The correction is completely determined by the operator product expansion of two spin-three currents, and by the expectation values of the stress tensor, its descendants and its composites, evaluated on the n-sheeted Riemann surface branched along the interval. This explains the recently found agreement of the order mu(2) correction across distinct free field CFTs and higher spin black hole solutions holographically dual to CFTs with W symmetry.

LOWER BOUNDS FOR BOXICITY

An axis-parallel b-dimensional box is a Cartesian product R-1 x R-2 x ... x R-b where R-i is a closed interval of the form a(i),b(i)] on the real line. For a graph G, its boxicity box(G) is the minimum dimension b, such that G is representable as the intersection graph of boxes in b-dimensional space. Although boxicity was introduced in 1969 and studied extensively, there are no significant results on lower bounds for boxicity. In this paper, we develop two general methods for deriving lower bounds. Applying these methods we give several results, some of which are listed below: 1. The boxicity of a graph on n vertices with no universal vertices and minimum degree delta is at least n/2(n-delta-1). 2. Consider the g(n,p) model of random graphs. Let p <= 1 - 40logn/n(2.) Then with high `` probability, box(G) = Omega(np(1 - p)). On setting p = 1/2 we immediately infer that almost all graphs have boxicity Omega(n). Another consequence of this result is as follows: For any positive constant c < 1, almost all graphs on n vertices and m <= c((n)(2)) edges have boxicity Omega(m/n). 3. Let G be a connected k-regular graph on n vertices. Let lambda be the second largest eigenvalue in absolute value of the adjacency matrix of G. Then, the boxicity of G is a least (kappa(2)/lambda(2)/log(1+kappa(2)/lambda(2))) (n-kappa-1/2n). 4. For any positive constant c 1, almost all balanced bipartite graphs on 2n vertices and m <= cn(2) edges have boxicity Omega(m/n).

Codes with Locality for Two Erasures

In this paper, we study codes with locality that can recover from two erasures via a sequence of two local, parity-check computations. By a local parity-check computation, we mean recovery via a single parity-check equation associated with small Hamming weight. Earlier approaches considered recovery in parallel; the sequential approach allows us to potentially construct codes with improved minimum distance. These codes, which we refer to as locally 2-reconstructible codes, are a natural generalization along one direction, of codes with all-symbol locality introduced by Gopalan et al, in which recovery from a single erasure is considered. By studying the generalized Hamming weights of the dual code, we derive upper bounds on the minimum distance of locally 2-reconstructible codes and provide constructions for a family of codes based on Turan graphs, that are optimal with respect to this bound. The minimum distance bound derived here is universal in the sense that no code which permits all-symbol local recovery from 2 erasures can have larger minimum distance regardless of approach adopted. Our approach also leads to a new bound on the minimum distance of codes with all-symbol locality for the single-erasure case.

A Modified Sum-Product Algorithm over Graphs with Isolated Short Cycles

We investigate into the limitations of the sum-product algorithm in the probability domain over graphs with isolated short cycles. By considering the statistical dependency of messages passed in a cycle of length 4, we modify the update equations for the beliefs at the variable and check nodes. We highlight an approximate log domain algebra for the modified variable node update to ensure numerical stability. At higher signal-to-noise ratios (SNR), the performance of decoding over graphs with isolated short cycles using the modified algorithm is improved compared to the original message passing algorithm (MPA).