Let $G=(V,E)$ be a connected undirected graph with $k$ vertices. Suppose
that on each vertex of the graph there is a player having an $n$-bit
string. Each player is allowed to communicate with its neighbors according
to an agreed communication protocol, and the players must decide,
deterministically, if their inputs ... more >>>

We present new explicit constructions of *deterministic* randomness extractors, dispersers and related objects. We say that a
distribution $X$ on binary strings of length $n$ is a
$\delta$-source if $X$ assigns probability at most $2^{-\delta n}$
to any string of length $n$. For every $\delta>0$ we construct the
following poly($n$)-time ... more >>>

Consider a graph obtained by taking edge disjoint union of $k$ complete bipartite graphs.
Alon, Saks and Seymour conjectured that such graph has chromatic number at most $k+1$.
This well known conjecture remained open for almost twenty years.
In this paper, we construct a counterexample to this
conjecture and discuss ... more >>>