Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #3 to TR14-029 | 13th October 2014 17:29

On Learning and Testing Dynamic Environments

RSS-Feed




Revision #3
Authors: Oded Goldreich, Dana Ron
Accepted on: 13th October 2014 17:30
Downloads: 826
Keywords: 


Abstract:

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 the requirement that only a small portion
of the environment is inspected in each time slot
(i.e., the time period between two consecutive applications
of the evolution rule).

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.



Changes to previous version:

correcting a few typos etc


Revision #2 to TR14-029 | 30th March 2014 18:21

On Learning and Testing Dynamic Environments





Revision #2
Authors: Oded Goldreich, Dana Ron
Accepted on: 30th March 2014 18:21
Downloads: 722
Keywords: 


Abstract:

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 the requirement that only a small portion
of the environment is inspected in each time slot
(i.e., the time period between two consecutive applications
of the evolution rule).

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.



Changes to previous version:

We added a new section (i.e., Sec 1.3) of proof overviews,
corrected the proof of Thm 2.2 and added details to the proof of Thm 7.3.


Revision #1 to TR14-029 | 15th March 2014 11:29

On Learning and Testing Dynamic Environments





Revision #1
Authors: Oded Goldreich, Dana Ron
Accepted on: 15th March 2014 11:29
Downloads: 618
Keywords: 


Abstract:

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 the requirement that only a small portion
of the environment is inspected in each time slot
(i.e., the time period between two consecutive applications
of the evolution rule).

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.



Changes to previous version:

This version contains an additional section (current Section 7)
that studies the testing of evironments of moving objects when
the number of objects s relatively very small (i.e., the ``sparse case'').


Paper:

TR14-029 | 4th March 2014 17:35

On Learning and Testing Dynamic Environments





TR14-029
Authors: Oded Goldreich, Dana Ron
Publication: 4th March 2014 17:36
Downloads: 1205
Keywords: 


Abstract:

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 the requirement that only a small portion
of the environment is inspected in each time slot
(i.e., the time period between two consecutive applications
of the evolution rule).

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.



ISSN 1433-8092 | Imprint