M.Sc Student | Costa Areej |
---|---|

Subject | Exact Learning of Juntas from Membership Queries |

Department | Department of Computer Science |

Supervisor | Professor Nader Bshouty |

Full Thesis text |

This work addresses the problem of
learning Boolean functions in the presence of irrelevant attributes. The
learning model is the model of exact learning from membership queries. A
function *f* is said to be a Boolean function on *n* variables if *f
: {*0,1*}*^{n}* → {*0,1*}*. A membership query *a*
is a Boolean assignment of length *n*.

In this model we have a teacher and a
learner. The teacher holds a hidden target function *f* from a specific
known class of Boolean functions *C*. The learning process is done by
asking the teacher membership queries. The teacher answers each membership
query *a* by *f(a)*. The learner’s goal is to learn the exact target
function *f*, using a minimum number of queries and a small time
complexity.

For an assignment *a**∈**{*0,1*}*^{n}* *,* i**∈**{*1*,...,n} *and* ξ**∈**{*0,1*}* we denote by *a| _{xi←ξ}*
the assignment

We use new techniques (such as Yao’s minimax principle) to find new bounds, narrow some of the gaps between the lower and upper bounds and find new non-adaptive and adaptive algorithms with small query and time complexities, both for the deterministic case and the randomized case. Some of the bounds are tight in the sense that finding better ones either gives a breakthrough result in some long-standing combinatorial open problem or needs a new technique that is beyond the existing ones. We introduce in the following our main results.

For deterministic non-adaptive
learning, we give a new *n ^{O(d)}*

For deterministic adaptive learning,
we give a new result for *poly(d ^{d},n)* time algorithms with
improved query complexity. We also introduce a new lower bound for randomized
adaptive learning. Furthermore, we describe three new randomized adaptive
algorithms. The first one runs in