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.

On linear series and a conjecture of D. C. Butler

Let C be a smooth irreducible projective curve of genus g and L a line bundle of degree d generated by a linear subspace V of H-0 (L) of dimension n+1. We prove a conjecture of D. C. Butler on the semistability of the kernel of the evaluation map V circle times O-C -> L and obtain new results on the stability of this kernel. The natural context for this problem is the theory of coherent systems on curves and our techniques involve wall crossing formulae in this theory.

A provably tight delay-driven concurrently congestion mitigating global routing algorithm

Routing is a very important step in VLSI physical design. A set of nets are routed under delay and resource constraints in multi-net global routing. In this paper a delay-driven congestion-aware global routing algorithm is developed, which is a heuristic based method to solve a multi-objective NP-hard optimization problem. The proposed delay-driven Steiner tree construction method is of O(n(2) log n) complexity, where n is the number of terminal points and it provides n-approximation solution of the critical time minimization problem for a certain class of grid graphs. The existing timing-driven method (Hu and Sapatnekar, 2002) has a complexity O(n(4)) and is implemented on nets with small number of sinks. Next we propose a FPTAS Gradient algorithm for minimizing the total overflow. This is a concurrent approach considering all the nets simultaneously contrary to the existing approaches of sequential rip-up and reroute. The algorithms are implemented on ISPD98 derived benchmarks and the drastic reduction of overflow is observed. (C) 2014 Elsevier Inc. All rights reserved.

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.

A Statistical Model of Current Loops and Magnetic Monopoles

We formulate a natural model of loops and isolated vertices for arbitrary planar graphs, which we call the monopole-dimer model. We show that the partition function of this model can be expressed as a determinant. We then extend the method of Kasteleyn and Temperley-Fisher to calculate the partition function exactly in the case of rectangular grids. This partition function turns out to be a square of a polynomial with positive integer coefficients when the grid lengths are even. Finally, we analyse this formula in the infinite volume limit and show that the local monopole density, free energy and entropy can be expressed in terms of well-known elliptic functions. Our technique is a novel determinantal formula for the partition function of a model of isolated vertices and loops for arbitrary graphs.

Taming Control Divergence in GPUs through Control Flow Linearization

Branch divergence is a very commonly occurring performance problem in GPGPU in which the execution of diverging branches is serialized to execute only one control flow path at a time. Existing hardware mechanism to reconverge threads using a stack causes duplicate execution of code for unstructured control flow graphs. Also the stack mechanism cannot effectively utilize the available parallelism among diverging branches. Further, the amount of nested divergence allowed is also limited by depth of the branch divergence stack. In this paper we propose a simple and elegant transformation to handle all of the above mentioned problems. The transformation converts an unstructured CFG to a structured CFG without duplicating user code. It incurs only a linear increase in the number of basic blocks and also the number of instructions. Our solution linearizes the CFG using a predicate variable. This mechanism reconverges the divergent threads as early as possible. It also reduces the depth of the reconvergence stack. The available parallelism in nested branches can be effectively extracted by scheduling the basic blocks to reduce the effect of stalls due to memory accesses. It can also increase execution efficiency of nested loops with different trip counts for different threads. We implemented the proposed transformation at PTX level using the Ocelot compiler infrastructure. We evaluated the technique using various benchmarks to show that it can be effective in handling the performance problem due to divergence in unstructured CFGs.

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.

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.

Magnetic structures and magnetic phase transitions in the Mn-doped orthoferrite TbFeO3 studied by neutron powder diffraction

The magnetic structures and the magnetic phase transitions in the Mn-doped orthoferrite TbFeO3 studied using neutron powder diffraction are reported. Magnetic phase transitions are identified at T-N(Fe/Mn) approximate to 295K where a paramagnetic-to-antiferromagnetic transition occurs in the Fe/Mn sublattice, T-SR(Fe/Mn) approximate to 26K where a spin-reorientation transition occurs in the Fe/Mn sublattice and T-N(R) approximate to 2K where Tb-ordering starts to manifest. At 295 K, the magnetic structure of the Fe/Mn sublattice in TbFe0.5Mn0.5O3 belongs to the irreducible representation Gamma(4) (G(x)A(y)F(z) or Pb'n'm). A mixed-domain structure of (Gamma(1) + Gamma(4)) is found at 250K which remains stable down to the spin re-orientation transition at T-SR(Fe/Mn) approximate to 26K. Below 26K and above 250 K, the majority phase (>80%) is that of Gamma(4). Below 10K the high-temperature phase Gamma(4) remains stable till 2K. At 2 K, Tb develops a magnetic moment value of 0.6(2) mu(B)/f.u. and orders long-range in F-z compatible with the Gamma(4) representation. Our study confirms the magnetic phase transitions reported already in a single crystal of TbFe0.5Mn0.5O3 and, in addition, reveals the presence of mixed magnetic domains. The ratio of these magnetic domains as a function of temperature is estimated from Rietveld refinement of neutron diffraction data. Indications of short-range magnetic correlations are present in the low-Q region of the neutron diffraction patterns at T < T-SR(Fe/Mn). These results should motivate further experimental work devoted to measure electric polarization and magnetocapacitance of TbFe0.5Mn0.5O3. (C) 2016 AIP Publishing LLC.

Magnetic structures and magnetic phase transitions in the Mn-doped orthoferrite TbFeO3 studied by neutron powder diffraction

The magnetic structures and the magnetic phase transitions in the Mn-doped orthoferrite TbFeO3 studied using neutron powder diffraction are reported. Magnetic phase transitions are identified at T-N(Fe/Mn) approximate to 295K where a paramagnetic-to-antiferromagnetic transition occurs in the Fe/Mn sublattice, T-SR(Fe/Mn) approximate to 26K where a spin-reorientation transition occurs in the Fe/Mn sublattice and T-N(R) approximate to 2K where Tb-ordering starts to manifest. At 295 K, the magnetic structure of the Fe/Mn sublattice in TbFe0.5Mn0.5O3 belongs to the irreducible representation Gamma(4) (G(x)A(y)F(z) or Pb'n'm). A mixed-domain structure of (Gamma(1) + Gamma(4)) is found at 250K which remains stable down to the spin re-orientation transition at T-SR(Fe/Mn) approximate to 26K. Below 26K and above 250 K, the majority phase (>80%) is that of Gamma(4). Below 10K the high-temperature phase Gamma(4) remains stable till 2K. At 2 K, Tb develops a magnetic moment value of 0.6(2) mu(B)/f.u. and orders long-range in F-z compatible with the Gamma(4) representation. Our study confirms the magnetic phase transitions reported already in a single crystal of TbFe0.5Mn0.5O3 and, in addition, reveals the presence of mixed magnetic domains. The ratio of these magnetic domains as a function of temperature is estimated from Rietveld refinement of neutron diffraction data. Indications of short-range magnetic correlations are present in the low-Q region of the neutron diffraction patterns at T < T-SR(Fe/Mn). These results should motivate further experimental work devoted to measure electric polarization and magnetocapacitance of TbFe0.5Mn0.5O3. (C) 2016 AIP Publishing LLC.

Moduli spaces of vector bundles on a singular rational ruled surface

We study moduli spaces M-X (r, c(1), c(2)) parametrizing slope semistable vector bundles of rank r and fixed Chern classes c(1), c(2) on a ruled surface whose base is a rational nodal curve. We showthat under certain conditions, these moduli spaces are irreducible, smooth and rational (when non-empty). We also prove that they are non-empty in some cases. We show that for a rational ruled surface defined over real numbers, the moduli space M-X (r, c(1), c(2)) is rational as a variety defined over R.

Homogeneous Hermitian holomorphic vector bundles and the Cowen-Douglas class over bounded symmetric domains

It is known that all the vector bundles of the title can be obtained by holomorphic induction from representations of a certain parabolic group on finite-dimensional inner product spaces. The representations, and the induced bundles, have composition series with irreducible factors. We write down an equivariant constant coefficient differential operator that intertwines the bundle with the direct sum of its irreducible factors. As an application, we show that in the case of the closed unit ball in C-n all homogeneous n-tuples of Cowen-Douglas operators are similar to direct sums of certain basic n-tuples. (c) 2015 Academie des sciences. Published by Elsevier Masson SAS. All rights reserved.

Magnetic structures and magnetic phase transitions in the Mn-doped orthoferrite TbFeO3 studied by neutron powder diffraction

The magnetic structures and the magnetic phase transitions in the Mn-doped orthoferrite TbFeO3 studied using neutron powder diffraction are reported. Magnetic phase transitions are identified at T-N(Fe/Mn) approximate to 295K where a paramagnetic-to-antiferromagnetic transition occurs in the Fe/Mn sublattice, T-SR(Fe/Mn) approximate to 26K where a spin-reorientation transition occurs in the Fe/Mn sublattice and T-N(R) approximate to 2K where Tb-ordering starts to manifest. At 295 K, the magnetic structure of the Fe/Mn sublattice in TbFe0.5Mn0.5O3 belongs to the irreducible representation Gamma(4) (G(x)A(y)F(z) or Pb'n'm). A mixed-domain structure of (Gamma(1) + Gamma(4)) is found at 250K which remains stable down to the spin re-orientation transition at T-SR(Fe/Mn) approximate to 26K. Below 26K and above 250 K, the majority phase (>80%) is that of Gamma(4). Below 10K the high-temperature phase Gamma(4) remains stable till 2K. At 2 K, Tb develops a magnetic moment value of 0.6(2) mu(B)/f.u. and orders long-range in F-z compatible with the Gamma(4) representation. Our study confirms the magnetic phase transitions reported already in a single crystal of TbFe0.5Mn0.5O3 and, in addition, reveals the presence of mixed magnetic domains. The ratio of these magnetic domains as a function of temperature is estimated from Rietveld refinement of neutron diffraction data. Indications of short-range magnetic correlations are present in the low-Q region of the neutron diffraction patterns at T < T-SR(Fe/Mn). These results should motivate further experimental work devoted to measure electric polarization and magnetocapacitance of TbFe0.5Mn0.5O3. (C) 2016 AIP Publishing LLC.

Magnetic structures and magnetic phase transitions in the Mn-doped orthoferrite TbFeO3 studied by neutron powder diffraction

The magnetic structures and the magnetic phase transitions in the Mn-doped orthoferrite TbFeO3 studied using neutron powder diffraction are reported. Magnetic phase transitions are identified at T-N(Fe/Mn) approximate to 295K where a paramagnetic-to-antiferromagnetic transition occurs in the Fe/Mn sublattice, T-SR(Fe/Mn) approximate to 26K where a spin-reorientation transition occurs in the Fe/Mn sublattice and T-N(R) approximate to 2K where Tb-ordering starts to manifest. At 295 K, the magnetic structure of the Fe/Mn sublattice in TbFe0.5Mn0.5O3 belongs to the irreducible representation Gamma(4) (G(x)A(y)F(z) or Pb'n'm). A mixed-domain structure of (Gamma(1) + Gamma(4)) is found at 250K which remains stable down to the spin re-orientation transition at T-SR(Fe/Mn) approximate to 26K. Below 26K and above 250 K, the majority phase (>80%) is that of Gamma(4). Below 10K the high-temperature phase Gamma(4) remains stable till 2K. At 2 K, Tb develops a magnetic moment value of 0.6(2) mu(B)/f.u. and orders long-range in F-z compatible with the Gamma(4) representation. Our study confirms the magnetic phase transitions reported already in a single crystal of TbFe0.5Mn0.5O3 and, in addition, reveals the presence of mixed magnetic domains. The ratio of these magnetic domains as a function of temperature is estimated from Rietveld refinement of neutron diffraction data. Indications of short-range magnetic correlations are present in the low-Q region of the neutron diffraction patterns at T < T-SR(Fe/Mn). These results should motivate further experimental work devoted to measure electric polarization and magnetocapacitance of TbFe0.5Mn0.5O3. (C) 2016 AIP Publishing LLC.