Month: August 2017

The minimal hidden computer needed to implement a visible computation

We consider the problem of constructing a physical system that evolves according to some specified conditional distribution. We restrict attention to physical systems that can be modeled as a time-inhomogeneous continuous-time Markov chain (CTMC) over a finite state space, which includes many of the systems considered in stochastic thermodynamics. Examples range from constructing a logical gate to be used in a digital circuit to constructing an entire digital computer. It is known that many conditional distributions over a space Xcannot be implemented by any CTMC, even approximately. This raises the question of how they can arise in the real world. Here we focus on the case where the conditional distribution is a (single-valued) function f. Any f over a set of “visible” states X can be implemented — if the system has access to some additional “hidden” states not in X. Motivated by engineering considerations, we consider a natural decomposition of any such CTMC into a sequence of “hidden” timesteps, demarcated by changes in the set of allowed transitions between states. We demonstrate a tradeoff between the number of hidden states and the number of hidden timesteps needed to implement any given f using a CTMC, analogous to space / time tradeoffs in theoretical computer science.


The minimal hidden computer needed to implement a visible computation
David H. Wolpert, Artemy Kolchinsky, Jeremy A. Owen


Re-Imagining Streetlight Infrastructure as a Digital Urban Platform

Urban infrastructures have traditionally been mono-functional: water, sewage, and electricity are notable examples. Embedded with digital technologies, urban infrastructures have the potential to communicate with one another and become multi-functional platforms that integrate data gathering and actuation cycles. In this paper, we focus on public lighting infrastructures. Despite the technological development of lights, including LED technology, streetlights have been primarily treated as a mono-functional infrastructure. Based on case studies, we discuss the potential of reimagining streetlight infrastructure, and advance some initial proposals that focus on sensing and actuation cycles, which could transform this pervasive infrastructure into a digital urban platform.


Re-Imagining Streetlight Infrastructure as a Digital Urban Platform
Ricardo Álvarez, Fábio Duarte, Alaa AlRadwan, Michelle Sit & Carlo Ratti
Journal of Urban Technology
Volume 24, 2017 – Issue 2

Pages 51-64 | Published online: 10 Apr 2017



The coevolution of networks and health

Historically, health has played an important role in network research, and vice versa (Valente, 2010). This intersection has contributed to how we understand human health as well as the development of network concepts, theory, and methods. Throughout, dynamics have featured prominently. Even when limited to static methods, the emphasis in each of these fields on providing causal explanations has led researchers to draw upon theories that are dynamic, often explicitly. Here, we elaborate a variety of ways to conceptualize the relationship between health and network dynamics, show how these possibilities are reflected in the existing literature, highlight how the articles within this special issue expand that understanding, and finally, identify paths for future research to push this intersection forward.


The coevolution of networks and health

Network Science, Volume 5 / Issue 3, August 2017, pp 249 – 256
doi: 10.1017/nws.2017.24


Trajectory stability in the traveling salesman problem

Two generalizations of the traveling salesman problem in which sites change their position in time are presented. The way the rank of different trajectory lengths changes in time is studied using the rank diversity. We analyze the statistical properties of rank distributions and rank dynamics and give evidence that the shortest and longest trajectories are more predictable and robust to change, that is, more stable.


Trajectory stability in the traveling salesman problem
Sergio Sánchez, Germinal Cocho, Jorge Flores, Carlos Gershenson, Gerardo Iñiguez, Carlos Pineda