Graduate Students

The complexity theory of switching networks has been explored during the past year by Nicholas Pippenger. 1 He investigated a large variety of problems concerned with connecting networks, and found the order of growth with network size of the num-ber of contacts needed. He also investigated the complexity of the routing algorithms required to set up the connection pattern. One of his results is the first proof that a particular type of connecting network(a partial concentrator) that can rearrange existing calls has a number of switches that grows more slowly with the number of inputs than is the case for a similar network that must maintain old calls while placing new ones. Another result is an improvement on the coefficient of the number of contacts needed for an E-blocking connecting network found by M. J. Marcus.2 This was obtained by an explicit construction. If selections from a fixed set of code words are packed adjacent (in space or time) to one another, a receiver or an algorithm accessing memory can unpack them neatly only if no code word in the set is the beginning of another. If the set satisfies this con-dition, its lengths must satisfy the Kraft inequality; conversely, any set of integer