Dmitry V. Chistikov
Testing Read-Once Functions over Arbitrary Bases.
Tue, 03/06/2012 - 15:01 — SomNambulAuthors: Dmitry V. Chistikov
Subjects: Discrete Mathematics
AbstractA Boolean function is called read-once over a basis B if it can be expressed
by a formula over B where no variable appears more than once. A checking test
for a read-once function f over B depending essentially on all its variables is
a set of input vectors distinguishing f from all other read-once functions of
the same variables. We show that all read-once functions f over B have checking
tests containing O(n^l) vectors, where n is the number of essential variables
of f and l is the largest arity of functions in B.- Read more
- 5 comments
- login or register to post comments
Learning Read-Once Functions Using Subcube Identity Queries.
Thu, 07/08/2010 - 15:01 — SomNambulAuthors: Andrey A. Voronenko, Dmitry V. Chistikov
Subjects: Computational Complexity
AbstractWe 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.
User login
