Depth-Independent Lower bounds on the Communication Complexity of Read-Once Boolean Formulas
Rahul JainHartmut KlauckShengyu ZhangPublished in: CoRR (2009)
Keyphrases
- boolean formula
- lower bound
- max sat
- equivalence queries
- upper bound
- sat solvers
- read once formulas
- worst case
- membership queries
- branch and bound algorithm
- np complete
- unsatisfiable cores
- practical problems
- np hard
- linear constraints
- computational complexity
- binary decision diagrams
- efficient learning
- branch and bound
- conjunctive normal form
- boolean variables
- randomly generated
- sat problem
- objective function
- constraint satisfaction
- tabu search
- optimal solution