A constant factor approximation algorithm for boxicity of circular arc graphs

Boxicity of a graph G(V, E) is the minimum integer k such that G can be represented as the intersection graph of k-dimensional axis parallel boxes in Rk. Equivalently, it is the minimum number of interval graphs on the vertex set V such that the intersection of their edge sets is E. It is known that boxicity cannot be approximated even for graph classes like bipartite, co-bipartite and split graphs below O(n0.5-ε)-factor, for any ε > 0 in polynomial time unless NP = ZPP. Till date, there is no well known graph class of unbounded boxicity for which even an nε-factor approximation algorithm for computing boxicity is known, for any ε < 1. In this paper, we study the boxicity problem on Circular Arc graphs - intersection graphs of arcs of a circle. We give a (2+ 1/k)-factor polynomial time approximation algorithm for computing the boxicity of any circular arc graph along with a corresponding box representation, where k ≥ 1 is its boxicity. For Normal Circular Arc(NCA) graphs, with an NCA model given, this can be improved to an additive 2-factor approximation algorithm. The time complexity of the algorithms to approximately compute the boxicity is O(mn+n2) in both these cases and in O(mn+kn2) which is at most O(n3) time we also get their corresponding box representations, where n is the number of vertices of the graph and m is its number of edges. The additive 2-factor algorithm directly works for any Proper Circular Arc graph, since computing an NCA model for it can be done in polynomial time.

Fast acoustic likelihood computation using low-rank matrix approximation

Acoustic modeling using mixtures of multivariate Gaussians is the prevalent approach for many speech processing problems. Computing likelihoods against a large set of Gaussians is required as a part of many speech processing systems and it is the computationally dominant phase for LVCSR systems. We express the likelihood computation as a multiplication of matrices representing augmented feature vectors and Gaussian parameters. The computational gain of this approach over traditional methods is by exploiting the structure of these matrices and efficient implementation of their multiplication.In particular, we explore direct low-rank approximation of the Gaussian parameter matrix and indirect derivation of low-rank factors of the Gaussian parameter matrix by optimum approximation of the likelihood matrix. We show that both the methods lead to similar speedups but the latter leads to far lesser impact on the recognition accuracy. Experiments on a 1138 word vocabulary RM1 task using Sphinx 3.7 system show that, for a typical case the matrix multiplication approach leads to overall speedup of 46%. Both the low-rank approximation methods increase the speedup to around 60%, with the former method increasing the word error rate (WER) from 3.2% to 6.6%, while the latter increases the WER from 3.2% to 3.5%.

A nested linear codes approach to distributed function computation over subspaces

In this paper, we consider a distributed function computation setting, where there are m distributed but correlated sources X1,...,Xm and a receiver interested in computing an s-dimensional subspace generated by [X1,...,Xm]Γ for some (m × s) matrix Γ of rank s. We construct a scheme based on nested linear codes and characterize the achievable rates obtained using the scheme. The proposed nested-linear-code approach performs at least as well as the Slepian-Wolf scheme in terms of sum-rate performance for all subspaces and source distributions. In addition, for a large class of distributions and subspaces, the scheme improves upon the Slepian-Wolf approach. The nested-linear-code scheme may be viewed as uniting under a common framework, both the Korner-Marton approach of using a common linear encoder as well as the Slepian-Wolf approach of employing different encoders at each source. Along the way, we prove an interesting and fundamental structural result on the nature of subspaces of an m-dimensional vector space V with respect to a normalized measure of entropy. Here, each element in V corresponds to a distinct linear combination of a set {Xi}im=1 of m random variables whose joint probability distribution function is given.

Quadrature approximation properties of the spiral-phase quadrature transform

The notion of the 1-D analytic signal is well understood and has found many applications. At the heart of the analytic signal concept is the Hilbert transform. The problem in extending the concept of analytic signal to higher dimensions is that there is no unique multidimensional definition of the Hilbert transform. Also, the notion of analyticity is not so well under stood in higher dimensions. Of the several 2-D extensions of the Hilbert transform, the spiral-phase quadrature transform or the Riesz transform seems to be the natural extension and has attracted a lot of attention mainly due to its isotropic properties. From the Riesz transform, Larkin et al. constructed a vortex operator, which approximates the quadratures based on asymptotic stationary-phase analysis. In this paper, we show an alternative proof for the quadrature approximation property by invoking the quasi-eigenfunction property of linear, shift-invariant systems. We show that the vortex operator comes up as a natural consequence of applying this property. We also characterize the quadrature approximation error in terms of its energy as well as the peak spatial-domain error. Such results are available for 1-D signals, but their counter part for 2-D signals have not been provided. We also provide simulation results to supplement the analytical calculations.

Point Spread Function Engineering for Super-Resolution Single-Photon and Multiphoton Fluorescence Microscopy

Super-resolution imaging techniques are of paramount interest for applications in bioimaging and fluorescence microscopy. Recent advances in bioimaging demand application-tailored point spread functions. Here, we present some approaches for generating application-tailored point spread functions along with fast imaging capabilities. Aperture engineering techniques provide interesting solutions for obtaining desired system point spread functions. Specially designed spatial filters—realized by optical mask—are outlined both in a single-lens and 4Pi configuration. Applications include depth imaging, multifocal imaging, and super-resolution imaging. Such an approach is suitable for fruitful integration with most existing state-of-art imaging microscopy modalities.

A fully discrete C-0 interior penalty Galerkin approximation of the extended Fisher-Kolmogorov equation

A fully discrete C-0 interior penalty finite element method is proposed and analyzed for the Extended Fisher-Kolmogorov (EFK) equation u(t) + gamma Delta(2)u - Delta u + u(3) - u = 0 with appropriate initial and boundary conditions, where gamma is a positive constant. We derive a regularity estimate for the solution u of the EFK equation that is explicit in gamma and as a consequence we derive a priori error estimates that are robust in gamma. (C) 2013 Elsevier B.V. All rights reserved.

Clusters of bound particles in the derivative delta-function Bose gas

In this paper we discuss a novel procedure for constructing clusters of bound particles in the case of a quantum integrable derivative delta-function Bose gas in one dimension. It is shown that clusters of bound particles can be constructed for this Bose gas for some special values of the coupling constant, by taking the quasi-momenta associated with the corresponding Bethe state to be equidistant points on a single circle in the complex momentum plane. We also establish a connection between these special values of the coupling constant and some fractions belonging to the Farey sequences in number theory. This connection leads to a classification of the clusters of bound particles associated with the derivative delta-function Bose gas and allows us to study various properties of these clusters like their size and their stability under the variation of the coupling constant. (C) 2013 Elsevier B.V. All rights reserved.

On the zeta function of a periodic-finite-type shift

Periodic-finite-type shifts (PFT's) are sofic shifts which forbid the appearance of finitely many pre-specified words in a periodic manner. The class of PFT's strictly includes the class of shifts of finite type (SFT's). The zeta function of a PET is a generating function for the number of periodic sequences in the shift. For a general sofic shift, there exists a formula, attributed to Manning and Bowen, which computes the zeta function of the shift from certain auxiliary graphs constructed from a presentation of the shift. In this paper, we derive an interesting alternative formula computable from certain ``word-based graphs'' constructed from the periodically-forbidden word description of the PET. The advantages of our formula over the Manning-Bowen formula are discussed.

Cl-35 NQR frequency and spin lattice relaxation time in 3,4-dichlorophenol as a function of pressure and temperature

The pressure dependences of Cl-35 nuclear quadrupole resonance (NQR) frequency, temperature and pressure variation of spin lattice relaxation time (T-1) were investigated in 3,4-dichlorophenol. T-1 was measured in the temperature range 77-300 K. Furthermore, the NQR frequency and T-1 for these compounds were measured as a function of pressure up to 5 kbar at 300 K. The temperature dependence of the average torsional lifetimes of the molecules and the transition probabilities W-1 and W-2 for the Delta m = +/- 1 and Delta m = +/- 2 transitions were also obtained. A nonlinear variation of NQR frequency with pressure has been observed and the pressure coefficients were observed to be positive. A thermodynamic analysis of the data was carried out to determine the constant volume temperature coefficients of the NQR frequency. An attempt is made to compare the torsional frequencies evaluated from NQR data with those obtained by IR spectra. On selecting the appropriate mode from IR spectra, a good agreement with torsional frequency obtained from NQR data is observed. The previously mentioned approach is a good illustration of the supplementary nature of the data from IR studies, in relation to NQR studies of compounds in solid state.

Determination of electric field at and near the focus of a cylindrical lens for applications in fluorescence microscopy

We present an explicit computable integral solution of the electric field generated at the focal region of a cylindrical lens. This representation is based on vectorial diffraction theory and further enables the computation of the system point spread function of a cylindrical lens. It is assumed that there is no back-scattering and the contribution from the evanescent field is negligible. Stationary phase approximation along with the Fresnel transmission coefficients are employed for evaluating the polarization dependent electric field components. Studies were carried out to determine the polarization effects and to calculate the system resolution. The effect of s -, p - and randomly polarized light is studied on the fixed sample (electric dipole is fixed in space). Proposed approach allows better understanding of electric field effects at the focus of a cylindrical aplanatic system. This opens up future developments in the field of fluorescence microscopy and optical imaging. (C) 2013 Author(s). All article content, except where otherwise noted, is licensed under a Creative Commons Attribution 3.0 Unported License.

Synthesis and application of weight function for edge cracked semicircular disk (ECSD)

We analyze the utility of edge cracked semicircular disk (ECSD) for rapid assessment of fracture toughness using compressive loading. Continuing our earlier work on ECSD, a theoretical examination here leads to a novel way for synthesizing weight functions using two distinct form factors. The efficacy of ECSD mode-I weight function synthesized using displacement and form factor methods is demonstrated by comparing with finite element results. Theory of elasticity in conjunction with finite element method is utilized to analyze crack opening potency of ECSD under eccentric compression to explore newer configurations of ECSD for fracture testing.

Case for multiple views of function in design based on a common definition

Functions are important in designing. However, several issues hinder progress with the understanding and usage of functions: lack of a clear and overarching definition of function, lack of overall justifications for the inevitability of the multiple views of function, and scarcity of systematic attempts to relate these views with one another. To help resolve these, the objectives of this research are to propose a common definition of function that underlies the multiple views in literature and to identify and validate the views of function that are logically justified to be present in designing. Function is defined as a change intended by designers between two scenarios: before and after the introduction of the design. A framework is proposed that comprises the above definition of function and an empirically validated model of designing, extended generate, evaluate, modify, and select of state-change, and an action, part, phenomenon, input, organ, and effect model of causality (Known as GEMS of SAPPhIRE), comprising the views of activity, outcome, requirement-solution-information, and system-environment. The framework is used to identify the logically possible views of function in the context of designing and is validated by comparing these with the views of function in the literature. Describing the different views of function using the proposed framework should enable comparisons and determine relationships among the various views, leading to better understanding and usage of functions in designing.

Multiwalled-carbon-nanotube-induced miscibility in near-critical PS/PVME blends: assessment through concentration fluctuations and segmental relaxation

The effects of multiwalled carbon nanotubes (MWNTs) on the concentration fluctuations, interfacial driven elasticity, phase morphology, and local segmental dynamics of chains for near-critical compositions of polystyrene/poly(vinyl to methyl ether) (PS/PVME) blends were systematically investigated using dynamic shear rheology and dielectric spectroscopy. The contribution of the correlation length (xi) of the concentration fluctuations to the evolving stresses was monitored in situ to probe the different stages of demixing in the blends. The classical upturn in the dynamic moduli was taken as the rheological demixing temperature (T-rheo), which was also observed to be in close agreement with those obtained using concentration fluctuation variance, <(delta phi)(2)>, versus temperature curves. Further, Fredrickson and Larson's approach involving the mean-field approximation and the double-reptation self-concentration (DRSC) model was employed to evaluate the spinodal decomposition temperature (T-s). Interestingly, the values of both T-rheo and T-s shifted upward in the blends in the presence of MWNTs, manifesting in molecular-level miscibility. These phenomenal changes were further observed to be a function of the concentration of MWNTs. The evolution of morphology as a function of temperature was studied using polarized optical microscopy (POM). It was observed that PVME, which evolved as an interconnected network during the early stages of demixing, coarsened into a matrix-droplet morphology in the late stages. The preferential wetting of PVME onto MWNTs as a result of physicochemical interactions retained the interconnected network of PVME for longer time scales, as supported by POM and atomic force microscopy (AFM) images. Microscopic heterogeneity in macroscopically miscible systems was studied by dielectric relaxation spectroscopy. The slowing of segmental relaxations in PVME was observed in the presence of both ``frozen'' PS and MWNTs interestingly at temperatures much below the calorimetric glass transition temperature (T-g). This phenomenon was observed to be local rather than global and was addressed by monitoring the evolution of the relaxation spectra near and above the demixing temperature.

Transverse single spin asymmetry in e plus p(up arrow) -> e plus J/psi plus X and transverse momentum dependent evolution of the Sivers function

We extend our analysis of transverse single spin asymmetry in electroproduction of J/psi to include the effect of the scale evolution of the transverse momentum dependent (TMD) parton distribution functions and gluon Sivers function. We estimate single spin asymmetry for JLab, HERMES, COMPASS, and eRHIC energies using the color evaporation model of charmonium production, using an analytically obtained approximate solution of TMD evolution equations discussed in the literature. We find that there is a reduction in the asymmetry compared with our predictions for the earlier case considered by us, wherein the Q(2) dependence came only from DGLAP evolution of the unpolarized gluon densities and a different parametrization of the TMD Sivers function was used.

Expansions of tau hadronic spectral function moments in a nonpower QCD perturbation theory with tamed large order behavior

The moments of the hadronic spectral functions are of interest for the extraction of the strong coupling alpha(s) and other QCD parameters from the hadronic decays of the tau lepton. Motivated by the recent analyses of a large class of moments in the standard fixed-order and contour-improved perturbation theories, we consider the perturbative behavior of these moments in the framework of a QCD nonpower perturbation theory, defined by the technique of series acceleration by conformal mappings, which simultaneously implements renormalization-group summation and has a tame large-order behavior. Two recently proposed models of the Adler function are employed to generate the higher-order coefficients of the perturbation series and to predict the exact values of the moments, required for testing the properties of the perturbative expansions. We show that the contour-improved nonpower perturbation theories and the renormalization-group-summed nonpower perturbation theories have very good convergence properties for a large class of moments of the so-called ``reference model,'' including moments that are poorly described by the standard expansions. The results provide additional support for the plausibility of the description of the Adler function in terms of a small number of dominant renormalons.