Redistribution Mechanisms for Assignment of Heterogeneous Objects

There are p heterogeneous objects to be assigned to n competing agents (n > p) each with unit demand. It is required to design a Groves mechanism for this assignment problem satisfying weak budget balance, individual rationality, and minimizing the budget imbalance. This calls for designing an appropriate rebate function. When the objects are identical, this problem has been solved which we refer as WCO mechanism. We measure the performance of such mechanisms by the redistribution index. We first prove an impossibility theorem which rules out linear rebate functions with non-zero redistribution index in heterogeneous object assignment. Motivated by this theorem,we explore two approaches to get around this impossibility. In the first approach, we show that linear rebate functions with non-zero redistribution index are possible when the valuations for the objects have a certain type of relationship and we design a mechanism with linear rebate function that is worst case optimal. In the second approach, we show that rebate functions with non-zero efficiency are possible if linearity is relaxed. We extend the rebate functions of the WCO mechanism to heterogeneous objects assignment and conjecture them to be worst case optimal.

The Borkar-Meyn theorem for asynchronous stochastic approximations

In this paper, we give a generalization of a result by Borkar and Meyn (2000) 1], on the stability and convergence of synchronous-update stochastic approximation algorithms, to the case of asynchronous stochastic approximations with delays. We then describe an interesting application of the result to asynchronous distributed temporal difference (TD) learning with function approximation and delays. (C) 2011 Elsevier B.V. All rights reserved.

Variants of Miyachi�s Theorem for Nilpotent lie Groups

We formulate and prove two versions of Miyachi�s theorem for connected, simply connected nilpotent Lie groups. This allows us to prove the sharpness of the constant 1/4 in the theorems of Hardy and of Cowling and Price for any nilpotent Lie group. These theorems are proved using a variant of Miyachi�s theorem for the group Fourier transform.

Qualitative theorem proving in linear constraints

We know, from the classical work of Tarski on real closed fields, that elimination is, in principle, a fundamental engine for mechanized deduction. But, in practice, the high complexity of elimination algorithms has limited their use in the realization of mechanical theorem proving. We advocate qualitative theorem proving, where elimination is attractive since most processes of reasoning take place through the elimination of middle terms, and because the computational complexity of the proof is not an issue. Indeed what we need is the existence of the proof and not its mechanization. In this paper, we treat the linear case and illustrate the power of this paradigm by giving extremely simple proofs of two central theorems in the complexity and geometry of linear programming.

Variants Of Miyachi’S Theorem For Nilpotent Lie Groups

We formulate and prove two versions of Miyachi’s theorem for connected, simply connected nilpotent Lie groups. This allows us to prove the sharpness of the constant 1/4 in the theorems of Hardy and of Cowling and Price for any nilpotent Lie group. These theorems are proved using a variant of Miyachi’s theorem for the group Fourier transform.

The single ring theorem

We study the empirical measure LA of the eigenvalues of nonnormal square matrices of the form A(n) = U(n)T(n)V(n), with U(n), V(n) independent Haar distributed on the unitary group and T(n) diagonal. We show that when the empirical measure of the eigenyalues of T(n) converges, and T(n) satisfies some technical conditions, L(An) converges towards a rotationally invariant measure mu on the complex plane whose support is a single ring. In particular, we provide a complete proof of the Feinberg-Zee single ring theorem [6]. We also consider the case where U(n), V(n) are independently Haar distributed on the orthogonal group.

An analogue of the Wiener Tauberian Theorem for the Heisenberg Motion group

We show that the Wiener Tauberian property holds for the Heisenberg Motion group TnB

Emitter near an arbitrary body: Purcell effect, optical theorem and the Wheeler-Feynman absorber

The altered spontaneous emission of an emitter near an arbitrary body can be elucidated using an energy balance of the electromagnetic field. From a classical point of view it is trivial to show that the field scattered back from any body should alter the emission of the source. But it is not at all apparent that the total radiative and non-radiative decay in an arbitrary body can add to the vacuum decay rate of the emitter (i.e.) an increase of emission that is just as much as the body absorbs and radiates in all directions. This gives us an opportunity to revisit two other elegant classical ideas of the past, the optical theorem and the Wheeler-Feynman absorber theory of radiation. It also provides us alternative perspectives of Purcell effect and generalizes many of its manifestations, both enhancement and inhibition of emission. When the optical density of states of a body or a material is difficult to resolve (in a complex geometry or a highly inhomogeneous volume) such a generalization offers new directions to solutions. (c) 2012 Elsevier Ltd. All rights reserved.

The projective plane, J-holomorphic curves and Desargues' theorem

By a theorem of Gromov, for an almost complex structure J on CP2 tamed by the standard symplectic structure, the J-holomorphic curves representing the positive generator of homology form a projective plane. We show that this satisfies the Theorem of Desargues if and only if J is isomorphic to the standard complex structure. This answers a question of Ghys. (C) 2013 Published by Elsevier Masson SAS on behalf of Academie des sciences.

Large deviation function and fluctuation theorem for classical particle transport

We analytically evaluate the large deviation function in a simple model of classical particle transfer between two reservoirs. We illustrate how the asymptotic long-time regime is reached starting from a special propagating initial condition. We show that the steady-state fluctuation theorem holds provided that the distribution of the particle number decays faster than an exponential, implying analyticity of the generating function and a discrete spectrum for its evolution operator.

Reduced Grobner bases and Macaulay-Buchberger Basis Theorem over Noetherian rings

In this paper, we extend the characterization of Zx]/(f), where f is an element of Zx] to be a free Z-module to multivariate polynomial rings over any commutative Noetherian ring, A. The characterization allows us to extend the Grobner basis method of computing a k-vector space basis of residue class polynomial rings over a field k (Macaulay-Buchberger Basis Theorem) to rings, i.e. Ax(1), ... , x(n)]/a, where a subset of Ax(1), ... , x(n)] is an ideal. We give some insights into the characterization for two special cases, when A = Z and A = ktheta(1), ... , theta(m)]. As an application of this characterization, we show that the concept of Border bases can be extended to rings when the corresponding residue class ring is a finitely generated, free A-module. (C) 2014 Elsevier B.V. All rights reserved.

An integral fluctuation theorem for systems with unidirectional transitions

The fluctuations of a Markovian jump process with one or more unidirectional transitions, where R-ij > 0 but R-ji = 0, are studied. We find that such systems satisfy an integral fluctuation theorem. The fluctuating quantity satisfying the theorem is a sum of the entropy produced in the bidirectional transitions and a dynamical contribution, which depends on the residence times in the states connected by the unidirectional transitions. The convergence of the integral fluctuation theorem is studied numerically and found to show the same qualitative features as systems exhibiting microreversibility.

A nodal domain theorem for integrable billiards in two dimensions

Eigenfunctions of integrable planar billiards are studied - in particular, the number of nodal domains, nu of the eigenfunctions with Dirichlet boundary conditions are considered. The billiards for which the time-independent Schrodinger equation (Helmholtz equation) is separable admit trivial expressions for the number of domains. Here, we discover that for all separable and nonseparable integrable billiards, nu satisfies certain difference equations. This has been possible because the eigenfunctions can be classified in families labelled by the same value of m mod kn, given a particular k, for a set of quantum numbers, m, n. Further, we observe that the patterns in a family are similar and the algebraic representation of the geometrical nodal patterns is found. Instances of this representation are explained in detail to understand the beauty of the patterns. This paper therefore presents a mathematical connection between integrable systems and difference equations. (C) 2014 Elsevier Inc. All rights reserved.

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.

Bounds on isoperimetric values of trees

Let G = (V, E) be a finite, simple and undirected graph. For S subset of V, let delta(S, G) = {(u, v) is an element of E : u is an element of S and v is an element of V - S} be the edge boundary of S. Given an integer i, 1 <= i <= vertical bar V vertical bar, let the edge isoperimetric value of G at i be defined as b(e)(i, G) = min(S subset of V:vertical bar S vertical bar=i)vertical bar delta(S, G)vertical bar. The edge isoperimetric peak of G is defined as b(e)(G) = max(1 <= j <=vertical bar V vertical bar)b(e)(j, G). Let b(v)(G) denote the vertex isoperimetric peak defined in a corresponding way. The problem of determining a lower bound for the vertex isoperimetric peak in complete t-ary trees was recently considered in [Y. Otachi, K. Yamazaki, A lower bound for the vertex boundary-width of complete k-ary trees, Discrete Mathematics, in press (doi: 10.1016/j.disc.2007.05.014)]. In this paper we provide bounds which improve those in the above cited paper. Our results can be generalized to arbitrary (rooted) trees. The depth d of a tree is the number of nodes on the longest path starting from the root and ending at a leaf. In this paper we show that for a complete binary tree of depth d (denoted as T-d(2)), c(1)d <= b(e) (T-d(2)) <= d and c(2)d <= b(v)(T-d(2)) <= d where c(1), c(2) are constants. For a complete t-ary tree of depth d (denoted as T-d(t)) and d >= c log t where c is a constant, we show that c(1)root td <= b(e)(T-d(t)) <= td and c(2)d/root t <= b(v) (T-d(t)) <= d where c(1), c(2) are constants. At the heart of our proof we have the following theorem which works for an arbitrary rooted tree and not just for a complete t-ary tree. Let T = (V, E, r) be a finite, connected and rooted tree - the root being the vertex r. Define a weight function w : V -> N where the weight w(u) of a vertex u is the number of its successors (including itself) and let the weight index eta(T) be defined as the number of distinct weights in the tree, i.e eta(T) vertical bar{w(u) : u is an element of V}vertical bar. For a positive integer k, let l(k) = vertical bar{i is an element of N : 1 <= i <= vertical bar V vertical bar, b(e)(i, G) <= k}vertical bar. We show that l(k) <= 2(2 eta+k k)