Letter to the editor concerning the paper by Z. A. Niyazova “Learning of arithmetic sum of monotone conjunctions”

A. V. Bistrigova

Lomonosov Moscow State University

Abstract: The complexity of learning functions with respect to the number of monotone conjunctions in their representation is studied in the paper “Learning of arithmetic sum of monotone conjunctions” by Z. A. Niyazova. In particular, lower and upper bounds on the number of queries one needs to learn the function, having no more than 2 conjunctions, are presented there. Here, we show that this result can be improved upon by one query.

Keywords: exact learning, sum of monotone conjunctions, membership queries.