Bounding the scaling window of random constraint satisfaction problems

The model $$k$$ k -CSP is a random CSP model with moderately growing arity $$k$$ k of constraints. By incorporating certain linear structure, $$k$$ k -CSP is revised to a random linear CSP, named $$k$$ k -hyper- $${\mathbb F}$$ F -linear CSP. It had been shown theoretically that the two models exhibit exact satisfiability phase transitions when the constraint density $$r$$ r is varied accordingly. In this paper, we use finite-size scaling analysis to characterize the threshold behaviors of the two models with finite problem size $$n$$ n . A series of experimental studies are carried out to illustrate the scaling window of the model $$k$$ k -CSP.