A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs.
Tommaso d'OrsiLuca TrevisanPublished in: CCC (2023)
Keyphrases
- zeta function
- constraint satisfaction problems
- boolean functions
- real valued
- conjunctive normal form
- constraint propagation
- decision diagrams
- constraint satisfaction
- arc consistency
- search space
- boolean formula
- non binary
- solving constraint satisfaction problems
- singular value decomposition
- tree decomposition
- pairwise comparison
- distributed constraint satisfaction
- lower bound
- binary csps
- coefficient matrix
- correlation matrix
- random instances
- symmetry breaking
- sat problem
- randomly generated
- constraint programming
- special case