On Tseitin Formulas, Read-Once Branching Programs and Treewidth.
Ludmila GlinskihDmitry ItsyksonPublished in: CSR (2019)
Keyphrases
- read once formulas
- semidefinite
- boolean functions
- tree decompositions
- constraint satisfaction problems
- membership queries
- uniform distribution
- semidefinite programming
- propositional formulas
- upper bound
- bounded treewidth
- search space
- convex sets
- convex relaxation
- max sat
- machine learning
- sufficient conditions
- simulated annealing
- decision trees