Checking tests for read-once functions over arbitrary bases

DOI10.1007/978-3-642-30642-6_6MaRDI QIDQ2907486zbMATH OpenOpenAlexFDO

Authors Dmitry Chistikov

Publication date 10 September 2012

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1203.0631

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Computational learning theory (68Q32) Boolean functions (06E30)

Abstract: A 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 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 every read-once function f over B has a checking test containing O(n^l) vectors, where n is the number of relevant variables of f and l is the largest arity of functions in B. For some functions, this bound cannot be improved by more than a constant factor. The employed technique involves reconstructing f from its l-variable projections and provides a stronger form of Kuznetsov's classic theorem on read-once representations.

Recommendations

• Testing read-once functions over the elementary basis
• Testing Monotone Read-Once Functions
• On the relationship between diagnostic and checking tests of the read-once functions
• Read-once functions with hard-to-test projections
• Testing of read-once functions in extended elementary bases

Cited in

(13)

• The length of a read-many certificate in the basis of all functions of l variables
• Read-once functions with hard-to-test projections
• Testing read-once functions over the elementary basis
• Read-once functions of the algebra of logic in pre-elementary bases
• On read-once functions over \(\mathbb{Z}_3\)
• Testing of read-once functions in extended elementary bases
• Testing read-once functions in a median-augmented element basis
• On the relationship between diagnostic and checking tests of the read-once functions
• Testing Monotone Read-Once Functions
• On read-once multifunctions in some base
• Learning read-once functions individually
• Using relevance queries for identification of read-once functions
• Learning read once functions using subcube parity queries

This page was built for publication: Checking tests for read-once functions over arbitrary bases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2907486)