Checking tests for read-once functions over arbitrary bases

DOI10.1007/978-3-642-30642-6_6zbMATH Open1360.06006arXiv1203.0631OpenAlexW2962843752MaRDI QIDQ2907486FDOQ2907486

Authors: Dmitry Chistikov 

Publication date: 10 September 2012

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

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.

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

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

Mathematics Subject Classification ID

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

Cited In (8)

• 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
• On the relationship between diagnostic and checking tests of the read-once functions
• Testing Monotone Read-Once Functions
• 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)