In 1977, J.A. Davis et al showed that any finite subset of natural numbers can be permuted such that it does not contain any 3-term A.P. as a sub-sequence. However, this is not true for the set of all natural numbers.
Alice and Bob want to hold a conversation over a noisy channel on which adversarially chosen bits may be flipped. How can they communicate robustly despite such an attack?
Peer reviewing is not just an important part of research, but also one of the main characteristics of scientific temper. However, over millions of years, we have evolved into selfish beings, and we attempt to maximize our benefits.
We consider the unbounded error communication complexity of XOR functions, i.e. those of the form f of XOR, where f is an arbitrary boolean function on n bits.
We introduce a new information-theoretic complexity measure IC∞ for 2-party functions which is a lower-bound on communication complexity, and has the two leading lower-bounds on communication complexity as its natural relaxations: (external) infor
The max-coloring problem is to compute a legal coloring of the vertices of a graph $G=(V,E)$ with vertex weights $w$ such that $sum^k_{i=1} max_{v \in C_i} w(v_i)$ is minimized, where $C_1, \ldots ,C_k$ are the various color classes.
How should a group of friends decide which movie to watch together or which restaurant to go for dinner? How should a municipal corporation decide which set of public projects to undertake?
As is well known, Monte Carlo methods are ubiquitous in many applied domains. One of the main uses of these methods is to study the long-time behavior of stochastic systems of interest.