On Learning and Testing Dynamic Environments

Webpage for a paper by Oded Goldreich and Dana Ron


We initiate a study of learning and testing dynamic environments, focusing on environment that evolve according to a fixed local rule. The (proper) learning task consists of obtaining the initial configuration of the environment, whereas for non-proper learning it suffices to predict its future values. The testing task consists of checking whether the environment has indeed evolved from some initial configuration according to the known evolution rule. We focus on the temporal aspect of these computational problems, which is reflected in two requirements: (1) It is not possible to "go back to the past" and make a query concerning the environment at time t after making a query at time t' > t; (2) Only a small portion of the environment is inspected in each time slot.

We present some general observations, an extensive study of two special cases, two separation results, and a host of open problems. The two special cases that we study refer to linear rules of evolution and to rules of evolution that represent simple movement of objects. Specifically, we show that evolution according to any linear rule can be tested within a total number of queries that is sublinear in the size of the environment, and that evolution according to a simple one-dimensional movement can be tested within a total number of queries that is independent of the size of the environment.

Material available on-line

Back to either Oded Goldreich's homepage or general list of papers.