Instance complexity of Boolean functions.

Alison Hsiang-Hsuan Liu Nikhil S. Mande

Published in: CoRR (2023)

Keyphrases

boolean functions
uniform distribution
polynomial size
threshold functions
functional properties
relevant variables
prime implicants
dnf formulae
linear threshold
bi decomposition
membership queries
multi valued
read once formulas
functional dependencies
binary decision diagrams
bounded treewidth