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

DOI10.3233/FI-2014-1032zbMATH Open1318.68099OpenAlexW1496971265MaRDI QIDQ2934873FDOQ2934873

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

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

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)

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)