Planted Constraint Satisfaction

Average-case hardness of recovering a planted solution to a random constraint-satisfaction instance, such as planted k-XOR.

Status	Statement	Tags
	Planted k-OV Hardness Conjecture 10 of the source, and a newly proposed average-case assumption rather than a question the literature already asked. Its worst-case counterpart – that k-OV requires n^(k-o(1)) time – is a central conjecture of fine-grained complexity. The planting preserves the marginal distribution of any subset of fewer than k vectors, and the source gives a search-to-decision reduction. 5 open	Average Case Hardness Fine Grained Cryptography Orthogonal Vectors Planted Constraint Satisfactionassumption
	SBP Collision Resistance Posed as a displayed Open Question and called a central open challenge. The source gives an efficient online collision finder for small kappa and an overlap-gap-based online lower bound for a different, randomized activation – introduced precisely because the SBP’s own collision space resists a first-moment analysis. For very large kappa collisions become trivial. The middle window is reached by neither technique. 4 open	Average Case Hardness Collision Resistant Hashing Overlap Gap Property Planted Constraint Satisfactionseparation
	PKE from constant-noise planted k-XOR Open: whether public-key encryption can be based on the hardness of planted k-XOR with a linear number of equations and a constant noise rate, as a single assumption. The survey poses it as one of two closing open questions and does not return to it; every combinatorial scheme it surveys needs sub-constant noise.	Average Case Hardness Planted Constraint Satisfactionseparationbarrier (ai)