Bounding Threshold Dimension: Realizing Graphic Boolean Functions as the AND of Majority Gates.
Mathew C. FrancisAtrayee MajumderRogers MathewPublished in: WG (2022)
Keyphrases
- boolean functions
- threshold functions
- uniform distribution
- upper bound
- membership queries
- relevant variables
- linear threshold
- prime implicants
- dnf formulae
- functional properties
- read once formulas
- multi valued
- disjunctive normal form
- pseudo boolean functions
- truth table
- bi decomposition
- relational databases
- lower bound