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.

Multivariate juggling probabilities

We consider refined versions of Markov chains related to juggling introduced by Warrington. We further generalize the construction to juggling with arbitrary heights as well as infinitely many balls, which are expressed more succinctly in terms of Markov chains on integer partitions. In all cases, we give explicit product formulas for the stationary probabilities. The normalization factor in one case can be explicitly written as a homogeneous symmetric polynomial. We also refine and generalize enriched Markov chains on set partitions. Lastly, we prove that in one case, the stationary distribution is attained in bounded time.

L-p estimates for the wave equation associated to the Grushin operator

We prove that the solution of the wave equation associated to the Grushin operator G = -Delta -vertical bar x vertical bar(2)partial derivative(2)(t) is bounded on L-P (Rn+1), with 1 < p < infinity, when vertical bar 1/p - 1/2 vertical bar < 1/n+2.

Quadrature Domains in C-n

We prove two density theorems for quadrature domains in , . It is shown that quadrature domains are dense in the class of all product domains of the form , where is a smoothly bounded domain satisfying Bell's Condition R and is a smoothly bounded domain and also in the class of all smoothly bounded complete Hartogs domains in C-2.

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.

Mesoporous silica-chondroitin sulphate hybrid nanoparticles for targeted and bio-responsive drug delivery

This work proposes the fabrication of a novel targeted drug delivery system based on mesoporous silica-biopolymer hybrids that can release drugs in response to biological stimuli present in cancer cells. The proposed system utilizes mesoporous silica nanoparticles as a carrier to host the drug molecules. A bio-polymer cap is attached onto these particles which serves the multiple functions of drug retention, targeting and bio-responsive drug release. The biopolymer chondroitin sulphate used here is a glycosaminoglycan that can specifically bind to receptors over-expressed in cancer cells. This molecule also possesses the property of disintegrating upon exposure to enzymes over-expressed in cancer cells. When these particles interact with cancer cells, the chondroitin sulphate present on the surface recognizes and attaches onto the CD44 receptors facilitating the uptake of these particles. The phagocytised particles are then exposed to the degradative enzymes, such as hyaluronidase present inside the cancer cells, which degrade the cap resulting in drug release. By utilizing a cervical cancer cell line we have demonstrated the targetability and intracellular delivery of hydrophobic drugs encapsulated in these particles. It was observed that the system was capable of enhancing the anticancer activity of the hydrophobic drug curcumin. Overall, we believe that this system might prove to be a valuable candidate for targeted and bioresponsive drug delivery.

Directed Nonabelian Sandpile Models on Trees

We define two general classes of nonabelian sandpile models on directed trees (or arborescences), as models of nonequilibrium statistical physics. Unlike usual applications of the well-known abelian sandpile model, these models have the property that sand grains can enter only through specified reservoirs. In the Trickle-down sandpile model, sand grains are allowed to move one at a time. For this model, we show that the stationary distribution is of product form. In the Landslide sandpile model, all the grains at a vertex topple at once, and here we prove formulas for all eigenvalues, their multiplicities, and the rate of convergence to stationarity. The proofs use wreath products and the representation theory of monoids.

Rainbow matchings in strongly edge-colored graphs

A rainbow matching of an edge-colored graph G is a matching in which no two edges have the same color. There have been several studies regarding the maximum size of a rainbow matching in a properly edge-colored graph G in terms of its minimum degree 3(G). Wang (2011) asked whether there exists a function f such that a properly edge-colored graph G with at least f (delta(G)) vertices is guaranteed to contain a rainbow matching of size delta(G). This was answered in the affirmative later: the best currently known function Lo and Tan (2014) is f(k) = 4k - 4, for k >= 4 and f (k) = 4k - 3, for k <= 3. Afterwards, the research was focused on finding lower bounds for the size of maximum rainbow matchings in properly edge-colored graphs with fewer than 4 delta(G) - 4 vertices. Strong edge-coloring of a graph G is a restriction of proper edge-coloring where every color class is required to be an induced matching, instead of just being a matching. In this paper, we give lower bounds for the size of a maximum rainbow matching in a strongly edge-colored graph Gin terms of delta(G). We show that for a strongly edge-colored graph G, if |V(G)| >= 2 |3 delta(G)/4|, then G has a rainbow matching of size |3 delta(G)/4|, and if |V(G)| < 2 |3 delta(G)/4|, then G has a rainbow matching of size |V(G)|/2] In addition, we prove that if G is a strongly edge-colored graph that is triangle-free, then it contains a rainbow matching of size at least delta(G). (C) 2015 Elsevier B.V. All rights reserved.

Detection of G-Quadruplex DNA Using Primer Extension as a Tool

DNA sequence and structure play a key role in imparting fragility to different regions of the genome. Recent studies have shown that non-B DNA structures play a key role in causing genomic instability, apart from their physiological roles at telomeres and promoters. Structures such as G-quadruplexes, cruciforms, and triplexes have been implicated in making DNA susceptible to breakage, resulting in genomic rearrangements. Hence, techniques that aid in the easy identification of such non-B DNA motifs will prove to be very useful in determining factors responsible for genomic instability. In this study, we provide evidence for the use of primer extension as a sensitive and specific tool to detect such altered DNA structures. We have used the G-quadruplex motif, recently characterized at the BCL2 major breakpoint region as a proof of principle to demonstrate the advantages of the technique. Our results show that pause sites corresponding to the non-B DNA are specific, since they are absent when the G-quadruplex motif is mutated and their positions change in tandem with that of the primers. The efficiency of primer extension pause sites varied according to the concentration of monovalant cations tested, which support G-quadruplex formation. Overall, our results demonstrate that primer extension is a strong in vitro tool to detect non-B DNA structures such as G-quadruplex on a plasmid DNA, which can be further adapted to identify non-B DNA structures, even at the genomic level.

GLOBAL REGISTRATION OF MULTIPLE POINT CLOUDS USING SEMIDEFINITE PROGRAMMING

Consider N points in R-d and M local coordinate systems that are related through unknown rigid transforms. For each point, we are given (possibly noisy) measurements of its local coordinates in some of the coordinate systems. Alternatively, for each coordinate system, we observe the coordinates of a subset of the points. The problem of estimating the global coordinates of the N points (up to a rigid transform) from such measurements comes up in distributed approaches to molecular conformation and sensor network localization, and also in computer vision and graphics. The least-squares formulation of this problem, although nonconvex, has a well-known closed-form solution when M = 2 (based on the singular value decomposition (SVD)). However, no closed-form solution is known for M >= 3. In this paper, we demonstrate how the least-squares formulation can be relaxed into a convex program, namely, a semidefinite program (SDP). By setting up connections between the uniqueness of this SDP and results from rigidity theory, we prove conditions for exact and stable recovery for the SDP relaxation. In particular, we prove that the SDP relaxation can guarantee recovery under more adversarial conditions compared to earlier proposed spectral relaxations, and we derive error bounds for the registration error incurred by the SDP relaxation. We also present results of numerical experiments on simulated data to confirm the theoretical findings. We empirically demonstrate that (a) unlike the spectral relaxation, the relaxation gap is mostly zero for the SDP (i.e., we are able to solve the original nonconvex least-squares problem) up to a certain noise threshold, and (b) the SDP performs significantly better than spectral and manifold-optimization methods, particularly at large noise levels.

A gap theorem for Ricci-flat 4-manifolds

Let (M, g) be a compact Ricci-fiat 4-manifold. For p is an element of M let K-max(P) (respectively K-min(p)) denote the maximum (respectively the minimum) of sectional curvatures at p. We prove that if K-max(p) <= -cK(min)(P) for all p is an element of M, for some constant c with 0 <= c < 2+root 6/4 then (M, g) is fiat. We prove a similar result for compact Ricci-flat Kahler surfaces. Let (M, g) be such a surface and for p is an element of M let H-max(p) (respectively H-min(P)) denote the maximum (respectively the minimum) of holomorphic sectional curvatures at p. If H-max(P) <= -cH(min)(P) for all p is an element of M, for some constant c with 0 <= c < 1+root 3/2, then (M, g) is flat. (C) 2015 Elsevier B.V. All rights reserved.

Performance Enhancement of Piezoelectric Energy Harvesters Using Multilayer and Multistep Beam Configurations

Low-power requirements of contemporary sensing technology attract research on alternate power sources that can replace batteries. Energy harvesters absorb ambient energy and function as power sources for sensors and other low-power devices. Piezoelectric bimorphs have been demonstrating the preeminence in converting the mechanical energy in ambient vibrations into electrical energy. Improving the performance of these harvesters is pivotal as the energy in ambient vibrations is innately low. In this paper, we focus on enhancing the performance of piezoelectric harvesters through a multilayer and, in particular, a multistep configuration. Partial coverage of piezoelectric material in steps along the length of a cantilever beam results in a multistep piezoelectric energy harvester. We also discuss obtaining an approximate deformation curve for the beam with multiple steps in a computationally efficient manner. We find that the power generated by a multistep beam is almost 90% more than that by a multilayer harvester made out of the same volume of polyvinylidinefluoride ( PVDF), further corroborated experimentally. Improvements observed in the power generated prove to be a boon for weakly coupled low profile piezoelectric materials. Thus, in spite of the weak piezoelectric coupling observed in PVDF, its energy harvesting capability can be improved significantly using it in a multistep piezoelectric beam configuration.

Making risk minimization tolerant to label noise

In many applications, the training data, from which one needs to learn a classifier, is corrupted with label noise. Many standard algorithms such as SVM perform poorly in the presence of label noise. In this paper we investigate the robustness of risk minimization to label noise. We prove a sufficient condition on a loss function for the risk minimization under that loss to be tolerant to uniform label noise. We show that the 0-1 loss, sigmoid loss, ramp loss and probit loss satisfy this condition though none of the standard convex loss functions satisfy it. We also prove that, by choosing a sufficiently large value of a parameter in the loss function, the sigmoid loss, ramp loss and probit loss can be made tolerant to nonuniform label noise also if we can assume the classes to be separable under noise-free data distribution. Through extensive empirical studies, we show that risk minimization under the 0-1 loss, the sigmoid loss and the ramp loss has much better robustness to label noise when compared to the SVM algorithm. (C) 2015 Elsevier B.V. All rights reserved.

Proper holomorphic mappings of balanced domains in C-n

We extend a well-known result, about the unit ball, by H. Alexander to a class of balanced domains in . Specifically: we prove that any proper holomorphic self-map of a certain type of balanced, finite-type domain in , is an automorphism. The main novelty of our proof is the use of a recent result of Opshtein on the behaviour of the iterates of holomorphic self-maps of a certain class of domains. We use Opshtein's theorem, together with the tools made available by finiteness of type, to deduce that the aforementioned map is unbranched. The monodromy theorem then delivers the result.

Simultaneous perturbation methods for adaptive labor staffing in service systems

We consider the problem of optimizing the workforce of a service system. Adapting the staffing levels in such systems is non-trivial due to large variations in workload and the large number of system parameters do not allow for a brute force search. Further, because these parameters change on a weekly basis, the optimization should not take longer than a few hours. Our aim is to find the optimum staffing levels from a discrete high-dimensional parameter set, that minimizes the long run average of the single-stage cost function, while adhering to the constraints relating to queue stability and service-level agreement (SLA) compliance. The single-stage cost function balances the conflicting objectives of utilizing workers better and attaining the target SLAs. We formulate this problem as a constrained parameterized Markov cost process parameterized by the (discrete) staffing levels. We propose novel simultaneous perturbation stochastic approximation (SPSA)-based algorithms for solving the above problem. The algorithms include both first-order as well as second-order methods and incorporate SPSA-based gradient/Hessian estimates for primal descent, while performing dual ascent for the Lagrange multipliers. Both algorithms are online and update the staffing levels in an incremental fashion. Further, they involve a certain generalized smooth projection operator, which is essential to project the continuous-valued worker parameter tuned by our algorithms onto the discrete set. The smoothness is necessary to ensure that the underlying transition dynamics of the constrained Markov cost process is itself smooth (as a function of the continuous-valued parameter): a critical requirement to prove the convergence of both algorithms. We validate our algorithms via performance simulations based on data from five real-life service systems. For the sake of comparison, we also implement a scatter search based algorithm using state-of-the-art optimization tool-kit OptQuest. From the experiments, we observe that both our algorithms converge empirically and consistently outperform OptQuest in most of the settings considered. This finding coupled with the computational advantage of our algorithms make them amenable for adaptive labor staffing in real-life service systems.