Universality of the Stochastic Airy Operator

We introduce a new method for studying universality of random matrices. Let T-n be the Jacobi matrix associated to the Dyson beta ensemble with uniformly convex polynomial potential. We show that after scaling, Tn converges to the stochastic Airy operator. In particular, the top edge of the Dyson beta ensemble and the corresponding eigenvectors are universal. As a byproduct, these ideas lead to conjectured operator limits for the entire family of soft edge distributions. (C) 2015 Wiley Periodicals, Inc.

QoS Constrained Optimal Sink and Relay Placement in Planned Wireless Sensor Networks

We are given a set of sensors at given locations, a set of potential locations for placing base stations (BSs, or sinks), and another set of potential locations for placing wireless relay nodes. There is a cost for placing a BS and a cost for placing a relay. The problem we consider is to select a set of BS locations, a set of relay locations, and an association of sensor nodes with the selected BS locations, so that the number of hops in the path from each sensor to its BS is bounded by h(max), and among all such feasible networks, the cost of the selected network is the minimum. The hop count bound suffices to ensure a certain probability of the data being delivered to the BS within a given maximum delay under a light traffic model. We observe that the problem is NP-Hard, and is hard to even approximate within a constant factor. For this problem, we propose a polynomial time approximation algorithm (SmartSelect) based on a relay placement algorithm proposed in our earlier work, along with a modification of the greedy algorithm for weighted set cover. We have analyzed the worst case approximation guarantee for this algorithm. We have also proposed a polynomial time heuristic to improve upon the solution provided by SmartSelect. Our numerical results demonstrate that the algorithms provide good quality solutions using very little computation time in various randomly generated network scenarios.

Anomalous transport at weak coupling

We evaluate the contribution of chiral fermions in d = 2, 4, 6, chiral bosons, a chiral gravitino like theory in d = 2 and chiral gravitinos in d = 6 to all the leading parity odd transport coefficients at one loop. This is done by using finite temperature field theory to evaluate the relevant Kubo formulae. For chiral fermions and chiral bosons the relation between the parity odd transport coefficient and the microscopic anomalies including gravitational anomalies agree with that found by using the general methods of hydrodynamics and the argument involving the consistency of the Euclidean vacuum. For the gravitino like theory in d = 2 and chiral gravitinos in d = 6, we show that relation between the pure gravitational anomaly and parity odd transport breaks down. From the perturbative calculation we clearly identify the terms that contribute to the anomaly polynomial, but not to the transport coefficient for gravitinos. We also develop a simple method for evaluating the angular integrals in the one loop diagrams involved in the Kubo formulae. Finally we show that charge diffusion mode of an ideal 2 dimensional Weyl gas in the presence of a finite chemical potential acquires a speed, which is equal to half the speed of light.

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].

Kernelization complexity of possible winner and coalitional manipulation problems in voting

In the POSSIBLE WINNER problem in computational social choice theory, we are given a set of partial preferences and the question is whether a distinguished candidate could be made winner by extending the partial preferences to linear preferences. Previous work has provided, for many common voting rules, fixed parameter tractable algorithms for the POSSIBLE WINNER problem, with number of candidates as the parameter. However, the corresponding kernelization question is still open and in fact, has been mentioned as a key research challenge 10]. In this paper, we settle this open question for many common voting rules. We show that the POSSIBLE WINNER problem for maximin, Copeland, Bucklin, ranked pairs, and a class of scoring rules that includes the Borda voting rule does not admit a polynomial kernel with the number of candidates as the parameter. We show however that the COALITIONAL MANIPULATION problem which is an important special case of the POSSIBLE WINNER problem does admit a polynomial kernel for maximin, Copeland, ranked pairs, and a class of scoring rules that includes the Borda voting rule, when the number of manipulators is polynomial in the number of candidates. A significant conclusion of our work is that the POSSIBLE WINNER problem is harder than the COALITIONAL MANIPULATION problem since the COALITIONAL MANIPULATION problem admits a polynomial kernel whereas the POSSIBLE WINNER problem does not admit a polynomial kernel. (C) 2015 Elsevier B.V. All rights reserved.

Tracking the migration of the Indian continent using the carbonate clumped isotope technique on Phanerozoic soil carbonates

Approximately 140 million years ago, the Indian plate separated from Gondwana and migrated by almost 90 degrees latitude to its current location, forming the Himalayan-Tibetan system. Large discrepancies exist in the rate of migration of Indian plate during Phanerozoic. Here we describe a new approach to paleo-latitudinal reconstruction based on simultaneous determination of carbonate formation temperature and delta O-18 of soil carbonates, constrained by the abundances of C-13-O-18 bonds in palaeosol carbonates. Assuming that the palaeosol carbonates have a strong relationship with the composition of the meteoric water, delta O-18 carbonate of palaeosol can constrain paleo-latitudinal position. Weighted mean annual rainfall delta O-18 water values measured at several stations across the southern latitudes are used to derive a polynomial equation: delta(18)Ow = -0.006 x (LAT)(2) - 0.294 x (LAT) - 5.29 which is used for latitudinal reconstruction. We use this approach to show the northward migration of the Indian plate from 46.8 +/- 5.8 degrees S during the Permian (269 M. y.) to 30 +/- 11 degrees S during the Triassic (248 M. y.), 14.7 +/- 8.7 degrees S during the early Cretaceous (135 M. y.), and 28 +/- 8.8 degrees S during the late Cretaceous ( 68 M. y.). Soil carbonate delta O-18 provides an alternative method for tracing the latitudinal position of Indian plate in the past and the estimates are consistent with the paleo-magnetic records which document the position of Indian plate prior to 135 +/- 3 M. y.

Nonrotating Beams Isospectral to Tapered Rotating Beams

In this paper, we seek to find nonrotating beams that are isospectral to a given tapered rotating beam. Isospectral structures have identical natural frequencies. We assume the mass and stiffness distributions of the tapered rotating beam to be polynomial functions of span. Such polynomial variations of mass and stiffness are typical of helicopter and wind turbine blades. We use the Barcilon-Gottlieb transformation to convert the fourth-order governing equations of the rotating and the nonrotating beams, from the (x, Y) frame of reference to a hypothetical (z, U) frame of reference. If the coefficients of both the equations in the (z, U) frame match with each other, then the nonrotating beam is isospectral to the given rotating beam. The conditions on matching the coefficients lead to a pair of coupled differential equations. Wesolve these coupled differential equations numerically using the fourth-order Runge-Kutta scheme. We also verify that the frequencies (given in the literature) of standard tapered rotating beams are the frequencies (obtained using the finite-element analysis) of the isospectral nonrotating beams. Finally, we present an example of beams having a rectangular cross-section to show the application of our analysis. Since experimental determination of rotating beam frequencies is a difficult task, experiments can be easily conducted on these isospectral nonrotating beams to calculate the frequencies of the rotating beam.