Department of

# Mathematics

Seminar Calendar
for events the day of Monday, March 6, 2006.

.
events for the
events containing

Questions regarding events or the calendar should be directed to Tori Corkery.
    February 2006            March 2006             April 2006
Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa
1  2  3  4             1  2  3  4                      1
5  6  7  8  9 10 11    5  6  7  8  9 10 11    2  3  4  5  6  7  8
12 13 14 15 16 17 18   12 13 14 15 16 17 18    9 10 11 12 13 14 15
19 20 21 22 23 24 25   19 20 21 22 23 24 25   16 17 18 19 20 21 22
26 27 28               26 27 28 29 30 31      23 24 25 26 27 28 29
30


Monday, March 6, 2006

2:00 pm in 143 Altgeld Hall,Monday, March 6, 2006

#### The geometry of projections

###### Gosia Konwerska (UIUC)

3:00 pm in 347 Altgeld Hall,Monday, March 6, 2006

#### The construction of traces

###### Thomas Cooney (UIUC)

3:00 pm in 3405 Siebel Center,Monday, March 6, 2006

#### On the Computational Complexity of Counting in Certain Classes of Sparse Graph Automata

###### P. Tosic (UIUC Computer Science)

Abstract: We study computational complexity of counting the fixed point configurations (FPs), garden of Eden configurations (GEs), and predecessor configurations in certain types of graph automata. We prove that both exact and approximate counting of fixed points in Sequential and Synchronous Dynamical Systems (SDSs and SyDSs, respectively) are computationally intractable problems. This intractability is shown to hold even when each node is required to update according to (i) a monotone Boolean function, (ii) a symmetric Boolean function, or even (iii) a simple threshold function that is both monotone and symmetric. We also show that the problems of counting exactly the garden of Eden configurations (GEs), all transient configurations, and all predecessors of an arbitrary configuration, are also computationally intractable. Moreover, the hardness of the exact enumeration of FPs and other types of configurations holds even in some severely restricted cases, i.e., when the nodes of an SDS or SyDS use at most two different Boolean functions from an appropriately restricted class of the node update rules, and, additionally, when the underlying graphs are constrained so that each node has only c = O(1) neighbors for small values of c.