Certificates of Non-Membership for Classes of Read-Once Functions

DOI10.3233/FI-2014-1032MaRDI QIDQ2934873zbMATH OpenOpenAlexFDO

Authors A. A. Voronenko, Dmitry Chistikov, V. S. Fedorova

Publication date 22 December 2014

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/fi-2014-1032

zbMATH Keywords

read-once functioncertificate of non-membership

Mathematics Subject Classification ID

Computational learning theory (68Q32) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Network protocols (68M12)

Recommendations

• Read-Once Functions Revisited and the Readability Number of a Boolean Function
• The length of a read-many certificate in the basis of all functions of l variables
• Testing read-once functions over the elementary basis
• Functions that are read-once on a subset of their inputs
• Sensitivity, Block Sensitivity, and Certificate Complexity of Unate Functions and Read-Once Functions
• scientific article; zbMATH DE number 176867
• scientific article; zbMATH DE number 7310075
• Read-once functions with hard-to-test projections
• Certification of nontermination proofs
• Non-malleable functions and their applications

Cited in

(4)

• The length of a read-many certificate in the basis of all functions of l variables
• On the Shannon function for read-many certificate length in a family of bases
• On the length of a read-many certificate in certain extended elementary bases
• Polynomial certificates for propositional classes.

This page was built for publication: Certificates of Non-Membership for Classes of Read-Once Functions

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