On Tseitin Formulas, Read-Once Branching Programs and Treewidth.
Ludmila GlinskihDmitry ItsyksonPublished in: Theory Comput. Syst. (2021)
Keyphrases
- semidefinite
- read once formulas
- tree decompositions
- boolean functions
- upper bound
- semidefinite programming
- propositional formulas
- constraint satisfaction problems
- search space
- bounded treewidth
- sufficient conditions
- boolean formula
- membership queries
- uniform distribution
- max sat
- convex relaxation
- machine learning
- higher dimensional
- semi supervised
- special case
- reduced error pruning