FR1.R7.3

A Random CSP with Connections to Discrepancy Theory and Randomized Trials

Eren Kizildag, University of Illinois Urbana-Champaign, United States

Session:
Information Theory and Computer Science

Track:
21: Other topics

Location:
VIP

Presentation Time:
Fri, 12 Jul, 10:25 - 10:45

Session Chair:
Prakash Narayan, University of Maryland
Abstract
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.
Resources