Testing Unsatisfiability of Constraint Satisfaction Problems via Tensor Products
원문 초록
We study the design of stochastic local search methods to prove unsatisfiability of a constraint satisfaction problem (CSP). For a binary CSP, such methods have been designed using the microstructure of the CSP. Here, we develop a method to decompose the microstructure into graph tensors. We show how to use the tensor decomposition to compute a proof of unsatisfiability efficiently and in parallel. We also offer substantial empirical evidence that our approach improves the praxis. For instance, one decomposition yields proofs of unsatisfiability in half the time without sacrificing the quality. Another decomposition is twenty times faster and effective three-tenths of the times compared to the prior method. Our method is applicable to arbitrary CSPs using the well known dual and hidden variable transformations from an arbitrary CSP to a binary CSP.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
MultiHU-TD: Multifeature Hyperspectral Unmixing Based on Tensor Decomposition
Revisit CP Tensor Decomposition: Statistical Optimality and Fast Convergence
D-Tracker: Modeling Interest Diffusion in Social Activity Tensor Data Streams
Multiscale Tensor Summation Factorization as a New Neural Network Layer (MTS Layer) for Multidimensional Data Processing
Knowledge Graph Completion with Mixed Geometry Tensor Factorization
Coeff-Tuning: A Graph Filter Subspace View for Tuning Attention-Based Large Models
토론
이 논문과 연결된 포럼 글이 아직 없습니다.