New Learning and Testing Problems for Read-Once Functions

Abstract

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.