UNO Gets Easier for a Single Player

This work is a follow up to 2, FUN 2010], which initiated a detailed analysis of the popular game of UNO (R). We consider the solitaire version of the game, which was shown to be NP-complete. In 2], the authors also demonstrate a (O)(n)(c(2)) algorithm, where c is the number of colors across all the cards, which implies, in particular that the problem is polynomial time when the number of colors is a constant. In this work, we propose a kernelization algorithm, a consequence of which is that the problem is fixed-parameter tractable when the number of colors is treated as a parameter. This removes the exponential dependence on c and answers the question stated in 2] in the affirmative. We also introduce a natural and possibly more challenging version of UNO that we call ``All Or None UNO''. For this variant, we prove that even the single-player version is NP-complete, and we show a single-exponential FPT algorithm, along with a cubic kernel.

Co-Evolution of Content Spread and Popularity in Mobile Opportunistic Networks

We consider a setting in which a single item of content is disseminated in a population of mobile nodes by opportunistic copying when pairs of nodes come in radio contact. The nodes in the population may either be interested in receiving the content (referred to as destinations) or not yet interested in receiving the content (referred to as relays). We consider a model for the evolution of popularity, the process by which relays get converted into destinations. A key contribution of our work is to model and study the joint evolution of content popularity and its spread in the population. Copying the content to relay nodes is beneficial since they can help spread the content to destinations, and could themselves be converted into destinations. We derive a fluid limit for the joint evolution model and obtain optimal policies for copying to relay nodes in order to deliver content to a desired fraction of destinations, while limiting the fraction of relay nodes that get the content but never turn into destinations. We prove that a time-threshold policy is optimal for controlling the copying to relays, i.e., there is an optimal time-threshold up to which all opportunities for copying to relays are exploited, and after which relays are not copied to. We then utilize simulations and numerical evaluations to provide insights into the effects of various system parameters on the optimally controlled co-evolution model.

BELIEF PROPAGATION FOR OPTIMAL EDGE COVER IN THE RANDOM COMPLETE GRAPH

We apply the objective method of Aldous to the problem of finding the minimum-cost edge cover of the complete graph with random independent and identically distributed edge costs. The limit, as the number of vertices goes to infinity, of the expected minimum cost for this problem is known via a combinatorial approach of Hessler and Wastlund. We provide a proof of this result using the machinery of the objective method and local weak convergence, which was used to prove the (2) limit of the random assignment problem. A proof via the objective method is useful because it provides us with more information on the nature of the edge's incident on a typical root in the minimum-cost edge cover. We further show that a belief propagation algorithm converges asymptotically to the optimal solution. This can be applied in a computational linguistics problem of semantic projection. The belief propagation algorithm yields a near optimal solution with lesser complexity than the known best algorithms designed for optimality in worst-case settings.

A novel method for studying the buckling of nanotubes considering geometrical imperfections

Buckling of nanotubes has been studied using many methods such as molecular dynamics (MD), molecular mechanics, and continuum-based shell theories. In MD, motion of the individual atoms is tracked under applied temperature and pressure, ensuring a reliable estimate of the material response. The response thus simulated varies for individual nanotubes and is only as accurate as the force field used to model the atomic interactions. On the other hand, there exists a rich literature on the understanding of continuum mechanics-based shell theories. Based on the observations on the behavior of nanotubes, there have been a number of shell theory-based approaches to study the buckling of nanotubes. Although some of these methods yield a reasonable estimate of the buckling stress, investigation and comparison of buckled mode shapes obtained from continuum analysis and MD are sparse. Previous studies show that the direct application of shell theories to study nanotube buckling often leads to erroneous results. The present study reveals that a major source of this error can be attributed to the departure of the shape of the nanotube from a perfect cylindrical shell. Analogous to the shell buckling in the macro-scale, in this work, the nanotube is modeled as a thin-shell with initial imperfection. Then, a nonlinear buckling analysis is carried out using the Riks method. It is observed that this proposed approach yields significantly improved estimate of the buckling stress and mode shapes. It is also shown that the present method can account for the variation of buckling stress as a function of the temperature considered. Hence, this can prove to be a robust method for a continuum analysis of nanosystems taking in the effect of variation of temperature as well.

VIRTUAL VIEW SYNTHESIS BY NON-LOCAL MEANS FILTERING USING TEMPORAL DATA

A novel algorithm for Virtual View Synthesis based on Non-Local Means Filtering is presented in this paper. Apart from using the video frames from the nearby cameras and the corresponding per-pixel depth map, this algorithm also makes use of the previously synthesized frame. Simple and efficient, the algorithm can synthesize video at any given virtual viewpoint at a faster rate. In the process, the quality of the synthesized frame is not compromised. Experimental results prove the above mentioned claim. The subjective and objective quality of the synthesized frames are comparable to the existing algorithms.

On Hermite pseudo-multipliers

In this article we deal with a variation of a theorem of Mauceri concerning the L-P boundedness of operators M which are known to be bounded on L-2. We obtain sufficient conditions on the kernel of the operator M so that it satisfies weighted L-P estimates. As an application we prove L-P boundedness of Hermite pseudo-multipliers. (C) 2014 Elsevier Inc. All rights reserved.

PROPER HOLOMORPHIC MAPS BETWEEN BOUNDED SYMMETRIC DOMAINS REVISITED

We prove that a proper holomorphic map between two nonplanar bounded symmetric domains of the same dimension, one of them being irreducible, is a biholomorphism. Our methods allow us to give a single, all-encompassing argument that unifies the various special cases in which this result is known. We discuss an application of these methods to domains having noncompact automorphism groups that are not assumed to act transitively.

Achieving SK Capacity in the Source Model: When Must All Terminals Talk?

In this paper, we address the problem of characterizing the instances of the multiterminal source model of Csiszar and Narayan in which communication from all terminals is needed for establishing a secret key of maximum rate. We give an information-theoretic sufficient condition for identifying such instances. We believe that our sufficient condition is in fact an exact characterization, but we are only able to prove this in the case of the three-terminal source model.

On strong centerpoints

Let P be a set of n points in R-d and F be a family of geometric objects. We call a point x is an element of P a strong centerpoint of P w.r.t..F if x is contained in all F is an element of F that contains more than cn points of P, where c is a fixed constant. A strong centerpoint does not exist even when F is the family of halfspaces in the plane. We prove the existence of strong centerpoints with exact constants for convex polytopes defined by a fixed set of orientations. We also prove the existence of strong centerpoints for abstract set systems with bounded intersection. (C) 2014 Elsevier B.V. All rights reserved.

Discrete-Rate Adaptation and Selection in Energy Harvesting Wireless Systems

In a system with energy harvesting (EH) nodes, the design focus shifts from minimizing energy consumption by infrequently transmitting less information to making the best use of available energy to efficiently deliver data while adhering to the fundamental energy neutrality constraint. We address the problem of maximizing the throughput of a system consisting of rate-adaptive EH nodes that transmit to a destination. Unlike related literature, we focus on the practically important discrete-rate adaptation model. First, for a single EH node, we propose a discrete-rate adaptation rule and prove its optimality for a general class of stationary and ergodic EH and fading processes. We then study a general system with multiple EH nodes in which one is opportunistically selected to transmit. We first derive a novel and throughput-optimal joint selection and rate adaptation rule (TOJSRA) when the nodes are subject to a weaker average power constraint. We then propose a novel rule for a multi-EH node system that is based on TOJSRA, and we prove its optimality for stationary and ergodic EH and fading processes. We also model the various energy overheads of the EH nodes and characterize their effect on the adaptation policy and the system throughput.

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.