Let $r$ and $d$ be positive integers and let $G$ be a finite graph.  Two players, Alice and Bob, play a game on $G$ by coloring the uncolored vertices with colors from a set $X$ of cardinality $r$.  At the end of each play, the subgraph induced by any color class must have maximum degree at most $d$.  We say that Alice wins the game if all vertices are eventually colored.  Otherwise, Bob wins.  The least $r$ such that Alice has a winning strategy is called the $d$-relaxed game chromatic number of $G$, denoted $d$-$\chi_g(G)$.  It is known that there exist graphs such that 0-$\chi_g(G)=3$, but 1-$\chi_g(G)>3$.  It is conjectured that for all $r$ and $d$, there exists a graph $G$ such that $d$-$\chi_g(G)=r$ and $(d+1)$-$\chi_g(G)>r$.  We will prove this conjecture for the special case where $d=0$.

Topological methods have been used (Bjorner, Lovasz, Welker and Yao)
for estimating the size and depth of decision trees where a linear test is performed at each node. The methods have been applied for instance to the questions of deciding, by a linear decision tree, whether given $n$ real numbers some $k$ of them are equal or some $k$ of them are unequal.  It turns out that the Betti numbers of the complement of  the $k$-equal arrangements are the essential ingredient in a lower bound
for these complexity problems. We show that the $A-$theory  is closely related to these spaces, thus shedding a new light on this topological approach to linear decision trees.

A tournament on a set V of n vertices is a directed graph on V in which for every pair of distinct vertices u, v in V, either (u,v) or (v,u) is a directed edge, but not both. Stearns, McCarvey, Erdos, Moser, and Alon studied the voting problem (realizing tournaments by orderings). Recently, Dr. Kierstead studied the Dice Dimension of Tournaments. We will discuss the relations between these two. Some new result in Dice Dimension will be presented, and some open problems which related to Dice Dimension and Monochromatic Paths in Edge-Colored Tournaments will be mentioned.

In the distributed model of computations, as introduced by Linial, a global function of a graph (for example a proper vertex coloring) must be computed, by every vertex in parallel, based on information available locally. In fact, to design an efficient algorithm a vertex v can obtain information about vertices that are in the sphere of poly-logarithmic radius with center in v. In addition, if no randomness is allowed, symmetry-breaking concerns must be addressed. In this talk, we will overview the known results and present algorithms for vertex- and edge-coloring problems.

Consider an arbitrary distributed network in which large numbers of objects are continuously being created, replicated, and destroyed.  A basic problem arising in such an environment is that of organizing a {\em data tracking scheme}\/ for locating object copies.  In this paper, we present a new tracking scheme for locating nearby copies of replicated objects in arbitrary distributed environments.

Our tracking scheme supports efficient accesses to data objects while keeping the local memory overhead low.  In particular, our tracking scheme achieves an expected $\polylog(n)$-approximation in the cost of any access operation, for an arbitrary network.  The memory overhead incurred by our scheme is $O(\polylog(n))$ times the maximum number of objects stored at any node, with high probability.  We also show that our tracking scheme adapts well to dynamic changes in the network.