Determining the Multiplicative Complexity of Boolean Functions using SAT.
Mathias SoekenPublished in: IACR Cryptol. ePrint Arch. (2020)
Keyphrases
- boolean functions
- uniform distribution
- polynomial size
- threshold functions
- randomly generated
- relevant variables
- membership queries
- boolean formula
- functional properties
- sat problem
- worst case
- truth table
- prime implicants
- multi valued
- linear threshold
- bounded treewidth
- read once formulas
- dnf formulae
- binary decision diagrams
- disjunctive normal form
- decision problems
- computational complexity