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

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

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

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)

Cited In (3)

• 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

   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 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Read-once functions with hard-to-test projections 👍 👎
• Certification of Nontermination Proofs 👍 👎
• Non-malleable functions and their applications 👍 👎

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)