Parallel Flow-Sensitive Pointer Analysis by Graph-Rewriting

Precise pointer analysis is a problem of interest to both the compiler and the program verification community. Flow-sensitivity is an important dimension of pointer analysis that affects the precision of the final result computed. Scaling flow-sensitive pointer analysis to millions of lines of code is a major challenge. Recently, staged flow-sensitive pointer analysis has been proposed, which exploits a sparse representation of program code created by staged analysis. In this paper we formulate the staged flow-sensitive pointer analysis as a graph-rewriting problem. Graph-rewriting has already been used for flow-insensitive analysis. However, formulating flow-sensitive pointer analysis as a graph-rewriting problem adds additional challenges due to the nature of flow-sensitivity. We implement our parallel algorithm using Intel Threading Building Blocks and demonstrate considerable scaling (upto 2.6x) for 8 threads on a set of 10 benchmarks. Compared to the sequential implementation of staged flow-sensitive analysis, a single threaded execution of our implementation performs better in 8 of the benchmarks.

Confining Dirac electrons on a topological insulator surface using potentials and a magnetic field

We study the effects of extended and localized potentials and a magnetic field on the Dirac electrons residing at the surface of a three-dimensional topological insulator like Bi2Se3. We use a lattice model to numerically study the various states; we show how the potentials can be chosen in a way which effectively avoids the problem of fermion doubling on a lattice. We show that extended potentials of different shapes can give rise to states which propagate freely along the potential but decay exponentially away from it. For an infinitely long potential barrier, the dispersion and spin structure of these states are unusual and these can be varied continuously by changing the barrier strength. In the presence of a magnetic field applied perpendicular to the surface, these states become separated from the gapless surface states by a gap, thereby giving rise to a quasi-one-dimensional system. Similarly, a magnetic field along with a localized potential can give rise to exponentially localized states which are separated from the surface states by a gap and thereby form a zero-dimensional system. Finally, we show that a long barrier and an impurity potential can produce bound states which are localized at the impurity, and an ``L''-shaped potential can have both bound states at the corner of the L and extended states which travel along the arms of the potential. Our work opens the way to constructing wave guides for Dirac electrons.

Edge states of a three-dimensional topological insulator

We use the bulk Hamiltonian for a three-dimensional topological insulator such as Bi-2 Se-3 to study the states which appear on its various surfaces and along the edge between two surfaces. We use both analytical methods based on the surface Hamiltonians (which are derived from the bulk Hamiltonian) and numerical methods based on a lattice discretization of the bulk Hamiltonian. We find that the application of a potential barrier along an edge can give rise to states localized at that edge. These states have an unusual energy-momentum dispersion which can be controlled by applying a potential along the edge; in particular, the velocity of these states can be tuned to zero. The scattering and conductance across the edge is studied as a function of the edge potential. We show that a magnetic field in a particular direction can also give rise to zero energy states on certain edges. We point out possible experimental ways of looking for the various edge states.

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 touch just at their boundaries.

BELIEF PROPAGATION FOR OPTIMAL EDGE COVER IN THE RANDOM COMPLETE GRAPH

We apply the objective method of Aldous to the problem of finding the minimum-cost edge cover of the complete graph with random independent and identically distributed edge costs. The limit, as the number of vertices goes to infinity, of the expected minimum cost for this problem is known via a combinatorial approach of Hessler and Wastlund. We provide a proof of this result using the machinery of the objective method and local weak convergence, which was used to prove the (2) limit of the random assignment problem. A proof via the objective method is useful because it provides us with more information on the nature of the edge's incident on a typical root in the minimum-cost edge cover. We further show that a belief propagation algorithm converges asymptotically to the optimal solution. This can be applied in a computational linguistics problem of semantic projection. The belief propagation algorithm yields a near optimal solution with lesser complexity than the known best algorithms designed for optimality in worst-case settings.

Rainbow Connection Number of Graph Power and Graph Products

Rainbow connection number, rc(G), of a connected graph G is the minimum number of colors needed to color its edges so that every pair of vertices is connected by at least one path in which no two edges are colored the same (note that the coloring need not be proper). In this paper we study the rainbow connection number with respect to three important graph product operations (namely the Cartesian product, the lexicographic product and the strong product) and the operation of taking the power of a graph. In this direction, we show that if G is a graph obtained by applying any of the operations mentioned above on non-trivial graphs, then rc(G) a parts per thousand currency sign 2r(G) + c, where r(G) denotes the radius of G and . In general the rainbow connection number of a bridgeless graph can be as high as the square of its radius 1]. This is an attempt to identify some graph classes which have rainbow connection number very close to the obvious lower bound of diameter (and thus the radius). The bounds reported are tight up to additive constants. The proofs are constructive and hence yield polynomial time -factor approximation algorithms.

Belief propagation for minimum weight many-to-one matchings in the random complete graph

In a complete bipartite graph with vertex sets of cardinalities n and n', assign random weights from exponential distribution with mean 1, independently to each edge. We show that, as n -> infinity, with n' = n/alpha] for any fixed alpha > 1, the minimum weight of many-to-one matchings converges to a constant (depending on alpha). Many-to-one matching arises as an optimization step in an algorithm for genome sequencing and as a measure of distance between finite sets. We prove that a belief propagation (BP) algorithm converges asymptotically to the optimal solution. We use the objective method of Aldous to prove our results. We build on previous works on minimum weight matching and minimum weight edge cover problems to extend the objective method and to further the applicability of belief propagation to random combinatorial optimization problems.

PERCOLATION ON THE INFORMATION-THEORETICALLY SECURE SIGNAL TO INTERFERENCE RATIO GRAPH

We consider a continuum percolation model consisting of two types of nodes, namely legitimate and eavesdropper nodes, distributed according to independent Poisson point processes in R-2 of intensities lambda and lambda(E), respectively. A directed edge from one legitimate node A to another legitimate node B exists provided that the strength of the signal transmitted from node A that is received at node B is higher than that received at any eavesdropper node. The strength of the signal received at a node from a legitimate node depends not only on the distance between these nodes, but also on the location of the other legitimate nodes and an interference suppression parameter gamma. The graph is said to percolate when there exists an infinitely connected component. We show that for any finite intensity lambda(E) of eavesdropper nodes, there exists a critical intensity lambda(c) < infinity such that for all lambda > lambda(c) the graph percolates for sufficiently small values of the interference parameter. Furthermore, for the subcritical regime, we show that there exists a lambda(0) such that for all lambda < lambda(0) <= lambda(c) a suitable graph defined over eavesdropper node connections percolates that precludes percolation in the graphs formed by the legitimate nodes.

Robust local and nonlocal transport in the topological Kondo insulator SmB6 in the presence of a high magnetic field

SmB6 has been predicted to be a Kondo topological insulator with topologically protected conducting surface states. We have studied quantitatively the electrical transport through surface states in high-quality single crystals of SmB6. We observe a large nonlocal surface signal at temperatures lower than the bulk Kondo gap scale. Measurements and finite-element simulations allow us to distinguish unambiguously between the contributions from different transport channels. In contrast to general expectations, the electrical transport properties of the surface channels were found to be insensitive to high magnetic fields. We propose possible scenarios that might explain this unexpected finding. Local and nonlocal magnetoresistance measurements allowed us to identify possible signatures of helical spin states and strong interband scattering at the surface.

Divide and Conquer: Efficient Large-Scale Structure from Motion Using Graph Partitioning

Despite significant advances in recent years, structure-from-motion (SfM) pipelines suffer from two important drawbacks. Apart from requiring significant computational power to solve the large-scale computations involved, such pipelines sometimes fail to correctly reconstruct when the accumulated error in incremental reconstruction is large or when the number of 3D to 2D correspondences are insufficient. In this paper we present a novel approach to mitigate the above-mentioned drawbacks. Using an image match graph based on matching features we partition the image data set into smaller sets or components which are reconstructed independently. Following such reconstructions we utilise the available epipolar relationships that connect images across components to correctly align the individual reconstructions in a global frame of reference. This results in both a significant speed up of at least one order of magnitude and also mitigates the problems of reconstruction failures with a marginal loss in accuracy. The effectiveness of our approach is demonstrated on some large-scale real world data sets.

Graph Modification Problems: A Modern Perspective

We give an overview of recent results and techniques in parameterized algorithms for graph modification problems.

Query Click and Text Similarity Graph for Query Suggestions

Query suggestion is an important feature of the search engine with the explosive and diverse growth of web contents. Different kind of suggestions like query, image, movies, music and book etc. are used every day. Various types of data sources are used for the suggestions. If we model the data into various kinds of graphs then we can build a general method for any suggestions. In this paper, we have proposed a general method for query suggestion by combining two graphs: (1) query click graph which captures the relationship between queries frequently clicked on common URLs and (2) query text similarity graph which finds the similarity between two queries using Jaccard similarity. The proposed method provides literally as well as semantically relevant queries for users' need. Simulation results show that the proposed algorithm outperforms heat diffusion method by providing more number of relevant queries. It can be used for recommendation tasks like query, image, and product suggestion.

Kinematics and dynamics of Jansen leg mechanism: A bond graph approach

The Jansen mechanism is a one degree-of-freedom, planar, 12-link, leg mechanism that can be used in mobile robotic applications and in gait analysis. This paper presents the kinematics and dynamics of the Jansen leg mechanism. The forward kinematics, accomplished using circle intersection method, determines the trajectories of various points on the mechanism in the chassis (stationary link) reference frame. From the foot point trajectory, the step length is shown to vary linearly while step height varies non-linearly with change in crank radius. A dynamic model for the Jansen leg mechanism is proposed using bond graph approach with modulated multiport transformers. For given ground reaction force pattern and crank angular speed, this model helps determine the motor torque profile as well as the link and joint stresses. The model can therefore be used to rate the actuator torque and in design of the hardware and controller for such a system. The kinematics of the mechanism can also be obtained from this dynamic model. The proposed model is thus a useful tool for analysis and design of systems based on the Jansen leg mechanism. (C) 2015 Elsevier B.V. All rights reserved.

Bulk-Induced 1/f Noise at the Surface of Three-Dimensional Topological Insulators

Slow intrinsic fluctuations of resistance, also known as the flicker noise or 1/f-noise, in the surface transport of strong topological insulators (TIs) is a poorly understood phenomenon. Here, we have systematically explored the 1/f-noise in field-effect transistors (FET) of mechanically exfoliated Bi1.6Sb0.4Te2Se TI films when transport occurs predominantly via the surface states. We find that the slow kinetics of the charge disorder within the bulk of the TI induces mobility fluctuations at the surface, providing a new source of intrinsic 1/f-noise that is unique to bulk TI systems. At small channel thickness, the noise magnitude can be extremely small, corresponding to the phenomenological Hooge parameter gamma(H) as low as approximate to 10(-4), but it increases rapidly when channel thickness exceeds similar to 1 mu m. From the temperature (T)-dependence of noise, which displayed sharp peaks at characteristic values of T, we identified generation-recombination processes from interband transitions within the TI bulk as the dominant source of the mobility fluctuations in surface transport. Our experiment not only establishes an intrinsic microscopic origin of noise in TI surface channels, but also reveals a unique spectroscopic information on the impurity bands that can be useful in bulk TI systems in general.

Falcon: A Graph Manipulation Language for Heterogeneous Systems

Graph algorithms have been shown to possess enough parallelism to keep several computing resources busy-even hundreds of cores on a GPU. Unfortunately, tuning their implementation for efficient execution on a particular hardware configuration of heterogeneous systems consisting of multicore CPUs and GPUs is challenging, time consuming, and error prone. To address these issues, we propose a domain-specific language (DSL), Falcon, for implementing graph algorithms that (i) abstracts the hardware, (ii) provides constructs to write explicitly parallel programs at a higher level, and (iii) can work with general algorithms that may change the graph structure (morph algorithms). We illustrate the usage of our DSL to implement local computation algorithms (that do not change the graph structure) and morph algorithms such as Delaunay mesh refinement, survey propagation, and dynamic SSSP on GPU and multicore CPUs. Using a set of benchmark graphs, we illustrate that the generated code performs close to the state-of-the-art hand-tuned implementations.