Diameter versus Certificate Complexity of Boolean Functions.

Siddhesh Chaubal Anna Gál

Published in: Electron. Colloquium Comput. Complex. (2022)

Keyphrases

boolean functions
uniform distribution
polynomial size
threshold functions
functional properties
prime implicants
membership queries
relevant variables
dnf formulae
computational complexity
bounded treewidth
binary decision diagrams
pseudo boolean functions
machine learning