One of Claude Shannon’s best remembered “toys” was his maze-solving machine, created by partitions on a rectangular grid. A mechanical mouse was started at one point in the maze with the task of finding cheese at another point. Relays under the board guided successive moves, each of which were taken in the first open counterclockwise direction from the previous move. In belated honor of Shannon’s centenary and of amnesia in the mouse at age 70, we compare this deterministic search strategy with ...

The initial vision of cellular communications was to deliver ubiquitous voice communications to anyone anywhere. In a simplified view, 1G delivered voice services for business customers, and only 2G for consumers. Next, this also initiated the appetite for cellular data, for which 3G was designed. However, Blackberry delivered business smartphones, and 4G made smartphones a consumer device. The promise of 5G is to start the Tactile Internet, to control real and virtual objects in real-time via c...

Using networks as a means of computing can reduce the communication flow over networks. We propose to distribute the computation load in stationary networks and formulate a flow-based delay minimization problem that jointly captures the costs of communications and computation. We exploit the distributed compression scheme of Slepian-Wolf that is applicable under any protocol information. We introduce the notion of entropic surjectivity as a measure of function’s sparsity and to understand the li...

Reed-Muller (RM) codes are among the oldest, simplest and perhaps most ubiquitous family of codes. They are used in many areas of coding theory in both electrical engineering and computer science. Yet, many of their important properties are still under investigation. This paper covers some of the recent developments regarding the weight enumerator and the capacity-achieving properties of RM codes, as well as some of the algorithmic developments. In particular, the paper discusses the recent conn...

This paper develops fundamental limits of deep neural network learning by characterizing what is possible if no constraints are imposed on the learning algorithm and on the amount of training data. Concretely, we consider Kolmogorov-optimal approximation through deep neural networks with the guiding theme being a relation between the complexity of the function (class) to be approximated and the complexity of the approximating network in terms of connectivity and memory requirements for storing t...