Diameter Versus Certificate Complexity of Boolean Functions.

Siddhesh Chaubal Anna Gál

Published in: MFCS (2021)

Keyphrases

boolean functions
uniform distribution
polynomial size
relevant variables
threshold functions
membership queries
prime implicants
dnf formulae
bounded treewidth
linear threshold
read once formulas
disjunctive normal form
linear functions
multi valued
bi decomposition
desirable properties
model checking