New Learning and Testing Problems for Read-Once Functions
Voronenko, Andrey A. · arXiv (Cornell University) · 2009
In the paper, we consider several types of queries for classical and new problems of learning and testing read-once functions. In several cases, the border between polynomial and exponential complexities is obtained.