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.

Two player game variant of the Erdos-Szekeres problem

The classical Erdos-Szekeres theorem states that a convex k-gon exists in every sufficiently large point set. This problem has been well studied and finding tight asymptotic bounds is considered a challenging open problem. Several variants of the Erdos-Szekeres problem have been posed and studied in the last two decades. The well studied variants include the empty convex k-gon problem, convex k-gon with specified number of interior points and the chromatic variant. In this paper, we introduce the following two player game variant of the Erdos-Szekeres problem: Consider a two player game where each player playing in alternate turns, place points in the plane. The objective of the game is to avoid the formation of the convex k-gon among the placed points. The game ends when a convex k-gon is formed and the player who placed the last point loses the game. In our paper we show a winning strategy for the player who plays second in the convex 5-gon game and the empty convex 5-gon game by considering convex layer configurations at each step. We prove that the game always ends in the 9th step by showing that the game reaches a specific set of configurations.

Differential Games of Mixed Type with Control and Stopping Times

We study a zero sum differential game of mixed type where each player uses both control and stopping times. Under certain conditions we show that the value function for this problem exists and is the unique viscosity solution of the corresponding variational inequalities. We also show the existence of saddle point equilibrium for a special case of differential game.

Cooperation of Notch and Ras/MAPK signaling pathways in human breast carcinogenesis

Background: Recent studies have implicated aberrant Notch signaling in breast cancers. Yet, relatively little is known about the pattern of expression of various components of the Notch pathway, or its mechanism of action. To better understand the role of the Notch pathway in breast cancer, we have undertaken a detailed expression analysis of various Notch receptors, their ligands, and downstream targets at different stages of breast cancer progression. Results: We report here that there is a general increase in the expression levels of Notch 1, 2, 4, Jagged1, Jagged2, and Delta-like 4 proteins in breast cancers, with simultaneous upregulation of multiple Notch receptors and ligands in a given cancer tissue. While Notch3 and Delta-like1 were undetectable in normal tissues, moderate to high expression was detected in several cancers. We detected the presence of active, cleaved Notch1, along with downstream targets of the Notch pathway, Hes1/Hes5, in similar to 75% of breast cancers, clearly indicating that in a large proportion of breast cancers Notch signaling is aberrantly activated. Furthermore, we detected cleaved Notch1 and Hes1/5 in early precursors of breast cancers - hyperplasia and ductal carcinoma in situ suggesting that aberrant Notch activation may be an early event in breast cancer progression. Mechanistically, while constitutively active Notch1 alone failed to transform immortalized breast cells, it synergized with the Ras/MAPK pathway to mediate transformation. This cooperation is reflected in vivo, as a subset of cleaved Notch positive tumors additionally expressed phopsho-Erk1/2 in the nuclei. Such cases exhibited high node positivity, suggesting that Notch-Ras cooperation may lead to poor prognosis. Conclusions: High level expression of Notch receptors and ligands, and its increased activation in several breast cancers and early precursors, places Notch signaling as a key player in breast cancer pathogenesis. Its cooperation with the Ras/MAPK pathway in transformation offers combined inhibition of the two pathways as a new modality for breast cancer treatment.

Experimental implementation of a three qubit quantum game with corrupt source using nuclear magnetic resonance quantum information processor

In a three player quantum `Dilemma' game each player takes independent decisions to maximize his/her individual gain. The optimal strategy in the quantum version of this game has a higher payoff compared to its classical counterpart. However, this advantage is lost if the initial qubits provided to the players are from a noisy source. We have experimentally implemented the three player quantum version of the `Dilemma' game as described by Johnson, [N.F. Johnson, Phys. Rev. A 63 (2001) 020302(R)] using nuclear magnetic resonance quantum information processor and have experimentally verified that the payoff of the quantum game for various levels of corruption matches the theoretical payoff. (c) 2007 Elsevier Inc. All rights reserved.

Comparative Nucleotide and Amino Acid Sequence Analysis of the Sequence-Specific RNA-Binding Rotavirus Nonstructural Protein NSP3

NSP3, an acidic nonstructural protein, encoded by gene 7 has been implicated as the key player in the assembly of the 11 viral plus-strand RNAs into the early replication intermediates during rotavirus morphogenesis. To date, the sequence or NSP3 from only three animal rotaviruses (SA11, SA114F, and bovine UK) has been determined and that from a human strain has not been reported. To determine the genetic diversity among gene 7 alleles from group A rotaviruses, the nucleotide sequence of the NSP3 gene from 13 strains belonging to nine different G serotypes, from both humans and animals, has been determined. Based on the amino acid sequence identity as well as phylogenetic analysis, NSP3 from group A rotaviruses falls into three evolutionarily related groups, i.e., the SA11 group, the Wa group, and the S2 group. The SA 11/SA114F gene appears to have a distant ancestral origin from that of the others and codes for a polypeptide of 315 amino acids (aa) in length. NSP3 from all other group A rotaviruses is only 313 aa in length because of a 2-amino-acid deletion near the carboxy-terminus, While the SA114F gene has the longest 3' untranslated region (UTR) of 132 nucleotides, that from other strains suffered deletions of varying lengths at two positions downstream of the translational termination codon. In spite of the divergence of the nucleotide (nt) sequence in the protein coding region, a stretch of about 80 nt in the 3' UTR is highly conserved in the NSP3 gene from all the strains. This conserved sequence in the 3' UTR might play an important role in the regulation of expression of the NSP3 gene. (C) 1995 Academic Press, Inc.

J. B. S. Haldane, Ernst Mayr and the Beanbag Genetics Dispute

Starting from the early decades of the twentieth century, evolutionary biology began to acquire mathematical overtones. This took place via the development of a set of models in which the Darwinian picture of evolution was shown to be consistent with the laws of heredity discovered by Mendel. The models, which came to be elaborated over the years, define a field of study known as population genetics. Population genetics is generally looked upon as an essential component of modern evolutionary theory. This article deals with a famous dispute between J. B. S. Haldane, one of the founders of population genetics, and Ernst Mayr, a major contributor to the way we understand evolution. The philosophical undercurrents of the dispute remain relevant today. Mayr and Haldane agreed that genetics provided a broad explanatory framework for explaining how evolution took place but differed over the relevance of the mathematical models that sought to underpin that framework. The dispute began with a fundamental issue raised by Mayr in 1959: in terms of understanding evolution, did population genetics contribute anything beyond the obvious? Haldane's response came just before his death in 1964. It contained a spirited defense, not just of population genetics, but also of the motivations that lie behind mathematical modelling in biology. While the difference of opinion persisted and was not glossed over, the two continued to maintain cordial personal relations.

A Nash Bargaining Approach to Retention Enhancing Bid Optimization in Sponsored Search Auctions with Discrete Bids

Bid optimization is now becoming quite popular in sponsored search auctions on the Web. Given a keyword and the maximum willingness to pay of each advertiser interested in the keyword, the bid optimizer generates a profile of bids for the advertisers with the objective of maximizing customer retention without compromising the revenue of the search engine. In this paper, we present a bid optimization algorithm that is based on a Nash bargaining model where the first player is the search engine and the second player is a virtual agent representing all the bidders. We make the realistic assumption that each bidder specifies a maximum willingness to pay values and a discrete, finite set of bid values. We show that the Nash bargaining solution for this problem always lies on a certain edge of the convex hull such that one end point of the edge is the vector of maximum willingness to pay of all the bidders. We show that the other endpoint of this edge can be computed as a solution of a linear programming problem. We also show how the solution can be transformed to a bid profile of the advertisers.

RAD51 as a potential biomarker and therapeutic target for pancreatic cancer

Chemotherapy is a very important therapeutic strategy for cancer treatment. The failure of conventional and molecularly targeted chemotherapeutic regimes for the treatment of pancreatic cancer highlights a desperate need for novel therapeutic interventions. Chemotherapy often fails to eliminate all tumor cells because of intrinsic or acquired drug resistance, which is the most common cause of tumor recurrence. Overexpression of RAD51 protein, a key player in DNA repair/recombination has been observed in many cancer cells and its hyperexpression is implicated in drug resistance. Recent studies suggest that RAD51 overexpression contributes to the development, progression and drug resistance of pancreatic cancer cells. Here we provide a brief overview of the available pieces of evidence in support of the role of RAD51 in pancreatic tumorigenesis and drug resistance, and hypothesize that RAD51 could serve as a potential biomarker for diagnosis of pancreatic cancer. We discuss the possible involvement of RAD51 in the drug resistance associated with epithelial to mesenchymal transition and with cancer stem cells. Finally, we speculate that targeting RAD51 in pancreatic cancer cells may be a novel approach for the treatment of pancreatic cancer. (C) 2011 Elsevier B.V. All rights reserved.

Experimental implementation of quantumUlam’s problem in a nuclear magnetic resonance quantum information processor

The Ulam’s problem is a two person game in which one of the player tries to search, in minimum queries, a number thought by the other player. Classically the problem scales polynomially with the size of the number. The quantum version of the Ulam’s problem has a query complexity that is independent of the dimension of the search space. The experimental implementation of the quantum Ulam’s problem in a Nuclear Magnetic Resonance Information Processor with 3 quantum bits is reported here.

Silencing of toxic gene expression by Fis

Bacteria and bacteriophages have evolved DNA modification as a strategy to protect their genomes. Mom protein of bacteriophage Mu modifies the phage DNA, rendering it refractile to numerous restriction enzymes and in turn enabling the phage to successfully invade a variety of hosts. A strong fortification, a combined activity of the phage and host factors, prevents untimely expression of mom and associated toxic effects. Here, we identify the bacterial chromatin architectural protein Fis as an additional player in this crowded regulatory cascade. Both in vivo and in vitro studies described here indicate that Fis acts as a transcriptional repressor of mom promoter. Further, our data shows that Fis mediates its repressive effect by denying access to RNA polymerase at mom promoter. We propose that a combined repressive effect of Fis and previously characterized negative regulatory factors could be responsible to keep the gene silenced most of the time. We thus present a new facet of Fis function in Mu biology. In addition to bringing about overall downregulation of Mu genome, it also ensures silencing of the advantageous but potentially lethal mom gene.

Silencing of toxic gene expression by Fis

Bacteria and bacteriophages have evolved DNA modification as a strategy to protect their genomes. Mom protein of bacteriophage Mumodifies the phage DNA, rendering it refractile to numerous restriction enzymes and in turn enabling the phage to successfully invade a variety of hosts. A strong fortification, a combined activity of the phage and host factors, prevents untimely expression of mom and associated toxic effects. Here, we identify the bacterial chromatin architectural protein Fis as an additional player in this crowded regulatory cascade. Both in vivo and in vitro studies described here indicate that Fisacts as a transcriptional repressor of mom promoter. Further, our data shows that Fis mediates its repressive effect by denying access to RNA polymerase at mom promoter. We propose that a combined repressive effect of Fis and previously characterized negative regulatory factors could be responsible to keep the gene silenced most of the time. We thus present a new facet of Fis function in Mu biology. In addition to bringing about overall downregulation of Mu genome, it also ensures silencing of the advantageous but potentially lethal mom gene.

ATM- and ATR-mediated phosphorylation of XRCC3 regulates DNA double-strand break-induced checkpoint activation and repair

The RAD51 paralogs XRCC3 and RAD51C have been implicated in homologous recombination (HR) and DNA damage responses. However, the molecular mechanism(s) by which these paralogs regulate HR and DNA damage signaling remains obscure. Here, we show that an SQ motif serine 225 in XRCC3 is phosphorylated by ATR kinase in an ATM signaling pathway. We find that RAD51C but not XRCC2 is essential for XRCC3 phosphorylation, and this modification follows end resection and is specific to S and G(2) phases. XRCC3 phosphorylation is required for chromatin loading of RAD51 and HR-mediated repair of double-strand breaks (DSBs). Notably, in response to DSBs, XRCC3 participates in the intra-S-phase checkpoint following its phosphorylation and in the G(2)/M checkpoint independently of its phosphorylation. Strikingly, we find that XRCC3 distinctly regulates recovery of stalled and collapsed replication forks such that phosphorylation is required for the HR-mediated recovery of collapsed replication forks but is dispensable for the restart of stalled replication forks. Together, these findings suggest that XRCC3 is a new player in the ATM/ATR-induced DNA damage responses to control checkpoint and HR-mediated repair.

Bounds on the sum-rate capacity of the Gaussian MIMO X channel

We consider the MIMO X channel (XC), a system consisting of two transmit-receive pairs, where each transmitter communicates with both the receivers. Both the transmitters and receivers are equipped with multiple antennas. First, we derive an upper bound on the sum-rate capacity of the MIMO XC under individual power constraint at each transmitter. The sum-rate capacity of the two-user multiple access channel (MAC) that results when receiver cooperation is assumed forms an upper bound on the sum-rate capacity of the MIMO XC. We tighten this bound by considering noise correlation between the receivers and deriving the worst noise covariance matrix. It is shown that the worst noise covariance matrix is a saddle-point of a zero-sum, two-player convex-concave game, which is solved through a primal-dual interior point method that solves the maximization and the minimization parts of the problem simultaneously. Next, we propose an achievable scheme which employs dirty paper coding at the transmitters and successive decoding at the receivers. We show that the derived upper bound is close to the achievable region of the proposed scheme at low to medium SNRs.

Fair Scheduling in Cellular Systems in the Presence of Noncooperative Mobiles

We consider the problem of ``fair'' scheduling the resources to one of the many mobile stations by a centrally controlled base station (BS). The BS is the only entity taking decisions in this framework based on truthful information from the mobiles on their radio channel. We study the well-known family of parametric alpha-fair scheduling problems from a game-theoretic perspective in which some of the mobiles may be noncooperative. We first show that if the BS is unaware of the noncooperative behavior from the mobiles, the noncooperative mobiles become successful in snatching the resources from the other cooperative mobiles, resulting in unfair allocations. If the BS is aware of the noncooperative mobiles, a new game arises with BS as an additional player. It can then do better by neglecting the signals from the noncooperative mobiles. The BS, however, becomes successful in eliciting the truthful signals from the mobiles only when it uses additional information (signal statistics). This new policy along with the truthful signals from mobiles forms a Nash equilibrium (NE) that we call a Truth Revealing Equilibrium. Finally, we propose new iterative algorithms to implement fair scheduling policies that robustify the otherwise nonrobust (in presence of noncooperation) alpha-fair scheduling algorithms.