Learning Read-Once Functions Using Subcube Identity Queries

Details Learning Read-Once Functions Using Subcube Identity Queries Learning Read-Once Functions Using Subcube Identity Queries

2010-07-07

arxiv.org/abs/1007.1073v1

Computer Science

Computational Complexity

Submitted to SODA11

Scientific paper

We consider the problem of exact identification for read-once functions over arbitrary Boolean bases. We introduce a new type of queries (subcube identity ones), discuss its connection to previously known ones, and study the complexity of the problem in question. Besides these new queries, learning algorithms are allowed to use classic membership ones. We present a technique of modeling an equivalence query with a polynomial number of membership and subcube identity ones, thus establishing (under certain conditions) a polynomial upper bound on the complexity of the problem. We show that in some circumstances, though, equivalence queries cannot be modeled with a polynomial number of subcube identity and membership ones. We construct an example of an infinite Boolean basis with an exponential lower bound on the number of membership and subcube identity queries required for exact identification. We prove that for any finite subset of this basis, the problem remains polynomial.

Affiliated with

Also associated with

No associations

Rating

Learning Read-Once Functions Using Subcube Identity Queries does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Learning Read-Once Functions Using Subcube Identity Queries, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Learning Read-Once Functions Using Subcube Identity Queries will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-345092