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.

SEPARATION DIMENSION OF BOUNDED DEGREE GRAPHS

The separation dimension of a graph G is the smallest natural number k for which the vertices of G can be embedded in R-k such that any pair of disjoint edges in G can be separated by a hyperplane normal to one of the axes. Equivalently, it is the smallest possible cardinality of a family F of total orders of the vertices of G such that for any two disjoint edges of G, there exists at least one total order in F in which all the vertices in one edge precede those in the other. In general, the maximum separation dimension of a graph on n vertices is Theta(log n). In this article, we focus on bounded degree graphs and show that the separation dimension of a graph with maximum degree d is at most 2(9) (log*d)d. We also demonstrate that the above bound is nearly tight by showing that, for every d, almost all d-regular graphs have separation dimension at least d/2]

Jet substructure and probes of CP violation in Vh production

We analyse the hVV (V = W, Z) vertex in a model independent way using Vh production. To that end, we consider possible corrections to the Standard Model Higgs Lagrangian, in the form of higher dimensional operators which parametrise the effects of new physics. In our analysis, we pay special attention to linear observables that can be used to probe CP violation in the same. By considering the associated production of a Higgs boson with a vector boson (W or Z), we use jet substructure methods to define angular observables which are sensitive to new physics effects, including an asymmetry which is linearly sensitive to the presence of CP odd effects. We demonstrate how to use these observables to place bounds on the presence of higher dimensional operators, and quantify these statements using a log likelihood analysis. Our approach allows one to probe separately the hZZ and hWW vertices, involving arbitrary combinations of BSM operators, at the Large Hadron Collider.

Boxicity and cubicity of product graphs

The boxicity (cubicity) of a graph G is the minimum natural number k such that G can be represented as an intersection graph of axis-parallel rectangular boxes (axis-parallel unit cubes) in R-k. In this article, we give estimates on the boxicity and the cubicity of Cartesian, strong and direct products of graphs in terms of invariants of the component graphs. In particular, we study the growth, as a function of d, of the boxicity and the cubicity of the dth power of a graph with respect to the three products. Among others, we show a surprising result that the boxicity and the cubicity of the dth Cartesian power of any given finite graph is, respectively, in O(log d/ log log d) and circle dot(d/ log d). On the other hand, we show that there cannot exist any sublinear bound on the growth of the boxicity of powers of a general graph with respect to strong and direct products. (C) 2015 Elsevier Ltd. All rights reserved.

Heterochromatic paths in edge colored graphs without small cycles and heterochromatic-triangle-free graphs

Conditions for the existence of heterochromatic Hamiltonian paths and cycles in edge colored graphs are well investigated in literature. A related problem in this domain is to obtain good lower bounds for the length of a maximum heterochromatic path in an edge colored graph G. This problem is also well explored by now and the lower bounds are often specified as functions of the minimum color degree of G - the minimum number of distinct colors occurring at edges incident to any vertex of G - denoted by v(G). Initially, it was conjectured that the lower bound for the length of a maximum heterochromatic path for an edge colored graph G would be 2v(G)/3]. Chen and Li (2005) showed that the length of a maximum heterochromatic path in an edge colored graph G is at least v(G) - 1, if 1 <= v(G) <= 7, and at least 3v(G)/5] + 1 if v(G) >= 8. They conjectured that the tight lower bound would be v(G) - 1 and demonstrated some examples which achieve this bound. An unpublished manuscript from the same authors (Chen, Li) reported to show that if v(G) >= 8, then G contains a heterochromatic path of length at least 120 + 1. In this paper, we give lower bounds for the length of a maximum heterochromatic path in edge colored graphs without small cycles. We show that if G has no four cycles, then it contains a heterochromatic path of length at least v(G) - o(v(G)) and if the girth of G is at least 4 log(2)(v(G)) + 2, then it contains a heterochromatic path of length at least v(G) - 2, which is only one less than the bound conjectured by Chen and Li (2005). Other special cases considered include lower bounds for the length of a maximum heterochromatic path in edge colored bipartite graphs and triangle-free graphs: for triangle-free graphs we obtain a lower bound of 5v(G)/6] and for bipartite graphs we obtain a lower bound of 6v(G)-3/7]. In this paper, it is also shown that if the coloring is such that G has no heterochromatic triangles, then G contains a heterochromatic path of length at least 13v(G)/17)]. This improves the previously known 3v(G)/4] bound obtained by Chen and Li (2011). We also give a relatively shorter and simpler proof showing that any edge colored graph G contains a heterochromatic path of length at least (C) 2015 Elsevier Ltd. All rights reserved.

Cytotoxicity of Ultrasmall Gold Nanoparticles on Planktonic and Biofilm Encapsulated Gram-Positive Staphylococci

The emergence of multidrug resistant bacteria, especially biofilm-associated Staphylococci, urgently requires novel antimicrobial agents. The antibacterial activity of ultrasmall gold nanoparticles (AuNPs) is tested against two gram positive: S. aureus and S. epidermidis and two gram negative: Escherichia coli and Pseudomonas aeruginosa strains. Ultrasmall AuNPs with core diameters of 0.8 and 1.4 nm and a triphenylphosphine-monosulfonate shell (Au0.8MS and Au1.4MS) both have minimum inhibitory concentration (MIC) and minimum bactericidal concentration of 25 x 10(-6)m Au]. Disc agar diffusion test demonstrates greater bactericidal activity of the Au0.8MS nanoparticles over Au1.4MS. In contrast, thiol-stabilized AuNPs with a diameter of 1.9 nm (AuroVist) cause no significant toxicity in any of the bacterial strains. Ultrasmall AuNPs cause a near 5 log bacterial growth reduction in the first 5 h of exposure, and incomplete recovery after 21 h. Bacteria show marked membrane blebbing and lysis in biofilm-associated bacteria treated with ultrasmall AuNP. Importantly, a twofold MIC dosage of Au0.8MS and Au1.4MS each cause around 80%-90% reduction in the viability of Staphylococci enveloped in biofilms. Altogether, this study demonstrates potential therapeutic activity of ultrasmall AuNPs as an effective treatment option against staphylococcal infections.

Seismic hazard maps and spectrum for Patna considering region-specific seismotectonic parameters

The objective of this paper was to develop the seismic hazard maps of Patna district considering the region-specific maximum magnitude and ground motion prediction equation (GMPEs) by worst-case deterministic and classical probabilistic approaches. Patna, located near Himalayan active seismic region has been subjected to destructive earthquakes such as 1803 and 1934 Bihar-Nepal earthquakes. Based on the past seismicity and earthquake damage distribution, linear sources and seismic events have been considered at radius of about 500 km around Patna district center. Maximum magnitude (M (max)) has been estimated based on the conventional approaches such as maximum observed magnitude (M (max) (obs) ) and/or increment of 0.5, Kijko method and regional rupture characteristics. Maximum of these three is taken as maximum probable magnitude for each source. Twenty-seven ground motion prediction equations (GMPEs) are found applicable for Patna region. Of these, suitable region-specific GMPEs are selected by performing the `efficacy test,' which makes use of log-likelihood. Maximum magnitude and selected GMPEs are used to estimate PGA and spectral acceleration at 0.2 and 1 s and mapped for worst-case deterministic approach and 2 and 10 % period of exceedance in 50 years. Furthermore, seismic hazard results are used to develop the deaggregation plot to quantify the contribution of seismic sources in terms of magnitude and distance. In this study, normalized site-specific design spectrum has been developed by dividing the hazard map into four zones based on the peak ground acceleration values. This site-specific response spectrum has been compared with recent Sikkim 2011 earthquake and Indian seismic code IS1893.

Inner Bound on the GDOF of the K-User MIMO Gaussian Symmetric Interference Channel

The K-user multiple input multiple output (MIMO) Gaussian symmetric interference channel where each transmitter has M antennas and each receiver has N antennas is studied from a generalized degrees of freedom (GDOF) perspective. An inner bound on the GDOF is derived using a combination of techniques such as treating interference as noise, zero forcing (ZF) at the receivers, interference alignment (IA), and extending the Han-Kobayashi (HK) scheme to K users, as a function of the number of antennas and the log INR/log SNR level. Several interesting conclusions are drawn from the derived bounds. It is shown that when K > N/M + 1, a combination of the HK and IA schemes performs the best among the schemes considered. When N/M < K <= N/M + 1, the HK-scheme outperforms other schemes and is found to be GDOF optimal in many cases. In addition, when the SNR and INR are at the same level, ZF-receiving and the HK-scheme have the same GDOF performance.

Minimization Problems Based on Relative alpha-Entropy II: Reverse Projection

In part I of this two-part work, certain minimization problems based on a parametric family of relative entropies (denoted I-alpha) were studied. Such minimizers were called forward I-alpha-projections. Here, a complementary class of minimization problems leading to the so-called reverse I-alpha-projections are studied. Reverse I-alpha-projections, particularly on log-convex or power-law families, are of interest in robust estimation problems (alpha > 1) and in constrained compression settings (alpha < 1). Orthogonality of the power-law family with an associated linear family is first established and is then exploited to turn a reverse I-alpha-projection into a forward I-alpha-projection. The transformed problem is a simpler quasi-convex minimization subject to linear constraints.

Transport properties of solution processed Cu2SnS3/AZnO heterostructure for low cost photovoltaics

Cu2SnS3 thin films were deposited by a facile sot-gel technique followed by annealing. The annealed films were structurally characterized by grazing incidence X-ray diffraction (GIXRD) and transmission electron microscopy (TEM). The crystal structure was found to be tetragonal with crystallite sizes of 2.4-3 nm. Texture coefficient calculations from the GIXRD revealed the preferential orientation of the film along the (112) plane. The morphological investigations of the films were carried out using field emission scanning electron microscopy (FESEM) and the composition using electron dispersive spectroscopy (EDS). The temperature dependent current, voltage characteristics of the Cu2SnS3/AZnO heterostructure were studied. The log I-log V plot exhibited three regions of different slopes showing linear ohmic behavior and non-linear behavior following the power law. The temperature dependent current voltage characteristics revealed the variation in ideality factor and barrier height with temperature. The Richardson constant was calculated and its deviation from the theoretical value revealed the inhomogeneity of the barrier heights. Transport characteristics were modeled using the thermionic emission model. The Gaussian distribution of barrier heights was applied and from the modified Richardson plot the value of the Richardson constant was found to be 47.18 A cm(-2) K-2. (c) 2015 Elsevier B.V. All rights reserved.

An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas

We show here a 2(Omega(root d.log N)) size lower bound for homogeneous depth four arithmetic formulas. That is, we give an explicit family of polynomials of degree d on N variables (with N = d(3) in our case) with 0, 1-coefficients such that for any representation of a polynomial f in this family of the form f = Sigma(i) Pi(j) Q(ij), where the Q(ij)'s are homogeneous polynomials (recall that a polynomial is said to be homogeneous if all its monomials have the same degree), it must hold that Sigma(i,j) (Number of monomials of Q(ij)) >= 2(Omega(root d.log N)). The above mentioned family, which we refer to as the Nisan-Wigderson design-based family of polynomials, is in the complexity class VNP. Our work builds on the recent lower bound results 1], 2], 3], 4], 5] and yields an improved quantitative bound as compared to the quasi-polynomial lower bound of 6] and the N-Omega(log log (N)) lower bound in the independent work of 7].

Influence of Anisotropy on Pavement Responses Using Adaptive Sparse Polynomial Chaos Expansion

Modeling the spatial variability that exists in pavement systems can be conveniently represented by means of random fields; in this study, a probabilistic analysis that considers the spatial variability, including the anisotropic nature of the pavement layer properties, is presented. The integration of the spatially varying log-normal random fields into a linear-elastic finite difference analysis has been achieved through the expansion optimal linear estimation method. For the estimation of the critical pavement responses, metamodels based on polynomial chaos expansion (PCE) are developed to replace the computationally expensive finite-difference model. The sparse polynomial chaos expansion based on an adaptive regression-based algorithm, and enhanced by the combined use of the global sensitivity analysis (GSA) is used, with significant savings in computational effort. The effect of anisotropy in each layer on the pavement responses was studied separately, and an effort is made to identify the pavement layer wherein the introduction of anisotropic characteristics results in the most significant impact on the critical strains. It is observed that the anisotropy in the base layer has a significant but diverse effect on both critical strains. While the compressive strain tends to be considerably higher than that observed for the isotropic section, the tensile strains show a decrease in the mean value with the introduction of base-layer anisotropy. Furthermore, asphalt-layer anisotropy also tends to decrease the critical tensile strain while having little effect on the critical compressive strain. (C) 2015 American Society of Civil Engineers.

Potential source identification for aerosol concentrations over a site in Northwestern India

The collocated measurements of aerosols size distribution (ASD) and aerosol optical thickness (AOT) are analyzed simultaneously using Grimm aerosol spectrometer and MICROTOP II Sunphotometer over Jaipur, capital of Rajasthan in India. The contrast temperature characteristics during winter and summer seasons of year 2011 are investigated in the present study. The total aerosol number concentration (TANC, 0.3-20 mu m) during winter season was observed higher than in summer time and it was dominated by fine aerosol number concentration (FANC < 2 mu m). Particles smaller than 0.8 mu m (at aerodynamic size) constitute similar to 99% of all particles in winter and similar to 90% of particles in summer season. However, particles greater than 2 mu m contribute similar to 3% and similar to 0.2% in summer and winter seasons respectively. The aerosols optical thickness shows nearly similar AOT values during summer and winter but corresponding low Angstrom Exponent (AE) values during summer than winter, respectively. In this work, Potential Source Contribution Function (PSCF) analysis is applied to identify locations of sources that influenced concentrations of aerosols over study area in two different seasons. PSCF analysis shows that the dust particles from That Desert contribute significantly to the coarse aerosol number concentration (CANC). Higher values of the PSCF in north from Jaipur showed the industrial areas in northern India to be the likely sources of fine particles. The variation in size distribution of aerosols during two seasons is clearly reflected in the log normal size distribution curves. The log normal size distribution curves reveals that the particle size less than 0.8 pm is the key contributor in winter for higher ANC. (C) 2015 Elsevier B.V. All rights reserved.

DETERMINISTIC ALGORITHMS FOR MATCHING AND PACKING PROBLEMS BASED ON REPRESENTATIVE SETS

In this work, we study the well-known r-DIMENSIONAL k-MATCHING ((r, k)-DM), and r-SET k-PACKING ((r, k)-SP) problems. Given a universe U := U-1 ... U-r and an r-uniform family F subset of U-1 x ... x U-r, the (r, k)-DM problem asks if F admits a collection of k mutually disjoint sets. Given a universe U and an r-uniform family F subset of 2(U), the (r, k)-SP problem asks if F admits a collection of k mutually disjoint sets. We employ techniques based on dynamic programming and representative families. This leads to a deterministic algorithm with running time O(2.851((r-1)k) .vertical bar F vertical bar. n log(2)n . logW) for the weighted version of (r, k)-DM, where W is the maximum weight in the input, and a deterministic algorithm with running time O(2.851((r-0.5501)k).vertical bar F vertical bar.n log(2) n . logW) for the weighted version of (r, k)-SP. Thus, we significantly improve the previous best known deterministic running times for (r, k)-DM and (r, k)-SP and the previous best known running times for their weighted versions. We rely on structural properties of (r, k)-DM and (r, k)-SP to develop algorithms that are faster than those that can be obtained by a standard use of representative sets. Incorporating the principles of iterative expansion, we obtain a better algorithm for (3, k)-DM, running in time O(2.004(3k).vertical bar F vertical bar . n log(2)n). We believe that this algorithm demonstrates an interesting application of representative families in conjunction with more traditional techniques. Furthermore, we present kernels of size O(e(r)r(k-1)(r) logW) for the weighted versions of (r, k)-DM and (r, k)-SP, improving the previous best known kernels of size O(r!r(k-1)(r) logW) for these problems.

Exact Phase Retrieval in Principal Shift-Invariant Spaces

We address the problem of phase retrieval from Fourier transform magnitude spectrum for continuous-time signals that lie in a shift-invariant space spanned by integer shifts of a generator kernel. The phase retrieval problem for such signals is formulated as one of reconstructing the combining coefficients in the shift-invariant basis expansion. We develop sufficient conditions on the coefficients and the bases to guarantee exact phase retrieval, by which we mean reconstruction up to a global phase factor. We present a new class of discrete-domain signals that are not necessarily minimum-phase, but allow for exact phase retrieval from their Fourier magnitude spectra. We also establish Hilbert transform relations between log-magnitude and phase spectra for this class of discrete signals. It turns out that the corresponding continuous-domain counterparts need not satisfy a Hilbert transform relation; notwithstanding, the continuous-domain signals can be reconstructed from their Fourier magnitude spectra. We validate the reconstruction guarantees through simulations for some important classes of signals such as bandlimited signals and piecewise-smooth signals. We also present an application of the proposed phase retrieval technique for artifact-free signal reconstruction in frequency-domain optical-coherence tomography (FDOCT).