We introduce a "derandomized" analogue of graph squaring. This
operation increases the connectivity of the graph (as measured by the
second eigenvalue) almost as well as squaring the graph does, yet only
increases the degree of the graph by a constant factor, instead of
squaring the degree.

One application of ... more >>>

We study counting various types of con gurations in certain classes of graph
automata viewed as discrete dynamical systems. The graph automata models
of our interest are Sequential and Synchronous Dynamical Systems (SDSs and
SyDSs, respectively). These models have been proposed as a mathematical foun-
dation for a theory of ... more >>>

We address the fundamental question of whether the Nash equilibria of
a game can be computed in polynomial time. We describe certain
efficient reductions between this problem for
normal form games with a fixed number of players
and graphical games with fixed degree. Our main result is that ... more >>>