A Random CSP with Connections to Discrepancy Theory and Randomized Trials

We introduce a random constraint satisfaction problem (CSP) with non-uniform constraints that is closely related to the average-case discrepancy minimization problem in the non-proportional regime. Our proposal is particularly motivated by randomized controlled trials (RCTs) in statistics, involving different constraints. For the random CSP that we propose, we establish a sharp phase transition result regarding the existence of its solutions. We then precisely pinpoint the distance between the solution spaces corresponding to independent problem instances. In the context of RCTs, this quantifies the amount of reassignments needed if a similar RCT is to be repeated with an independent population and/or a potentially different set of constraints. We lastly study the solution space geometry, and show that, for certain values of constraints, the solutions are isolated singletons separated by linear Hamming distance.