Learning Parity With Noise

Hardness of decoding a noisy random linear code, and the variants – sparse, regular-noise, variable-density, expand-accumulate – that correlated-pseudorandomness constructions are built on.

Status	Statement	Tags
	Subexponential-query PCF from sparse LPN Open in both directions, and the source paper poses it as a question rather than conjecturing an answer; the affirmative direction is this page’s reading. The one follow-up construction from sparse LPN inherits the same superpolynomial ceiling and says so. 6 open	Learning Parity With Noise Pseudorandom Correlation Functions Random Oracle Modelromassumption
	Standard-model weak PCF from sparse LPN Open, posed by the source as its second open question with an obstruction it names explicitly; the affirmative direction is this page’s reading. An independent follow-up construction reports the same random oracle as inherent to the same recursion. 6 open	Learning Parity With Noise Pseudorandom Correlation Functions Random Oracle Modelassumption
	Efficient Parity-Tolerance Simulation Feasibility is settled: every circuit can be compiled into a t-parity-tolerant one. What is open is the simulator’s running time, which in the source’s construction is exponential in t; the source gives partial evidence, under LPN, that inefficient simulation may be inherent for a related relaxed notion. 4 open	Leakage Resilient Circuits Learning Parity With Noisecharacterization
	EA-Code Distance over Rings Theorem 3.10 of the source proves the distance bound over F_2 only. Over a ring of size q its proof technique forces the rate to satisfy R much less than 1/ln q, which the source states it believes is an artefact of the argument, supported by small-parameter weight-distribution experiments over F_17 and Z_16. 5 open	Code Based Cryptography Dual Distance Learning Parity With Noise Pseudorandom Correlation Functionslower-boundadaptation (ai)
	No Self-Reduction for LSN Conjecture 5.20 of the source. It proves no random self-reduction exists from an arbitrary worst-case QNCP instance into LSN, naming exchange symmetry between code and error as the obstruction, and proves the tableau-randomizing barrier conditionally on the scrambling gap being polynomially related to eps. It is explicit that this is not an impossibility for random self-reductions in general. 4 open	Average Case Hardness Learning Parity With Noise Quantum Information Stabilizer Codesimpossibilityadaptation (ai)
	Binary dual-distance bound is the worst case Open, and asserted rather than asked – the source writes that it expects the inequality, gives an intuition covering one of the two competing effects, records that all prior work assumes it, and proves nothing. A probe at small parameters is consistent with it; the parameters the source’s own construction uses are out of computational reach, which is why the source does not check it either. 7 open	Average Case Hardness Dual Distance Learning Parity With Noiselower-boundadaptation (ai)
	MDSD Linear-Test Bias The source proves a non-tight reduction from standard decisional syndrome decoding and separately conjectures that the DOOM algorithm is the best attack; the linear-test bias is the one quantity it states it cannot bound. 5 open	Learning Parity With Noise Shuffle Model Syndrome Decodinglower-bound