Public Key Encryption from High-Corruption Constraint Satisfaction Problems

Amit Sahai; Isaac M Hair

arxiv: 2604.10479 · v1 · submitted 2026-04-12 · 💻 cs.CR

Public Key Encryption from High-Corruption Constraint Satisfaction Problems

Isaac M Hair , Amit Sahai This is my paper

Pith reviewed 2026-05-10 16:31 UTC · model grok-4.3

classification 💻 cs.CR

keywords public-key encryptionconstraint satisfaction problemsLARP-CSPkXORtrapdoor plantingerror-correcting codeshigh corruption rateexpander graphs

0 comments

The pith

A public-key encryption scheme achieves plausible quasi-exponential security from the conjectured hardness of two high-corruption constraint satisfaction problems.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The authors build a public-key encryption scheme whose security rests on the assumed intractability of two constraint satisfaction problems in which nearly all constraints have been replaced by random values. A reader would care because the resulting security level is set far above quasi-polynomial time, a threshold that many other post-quantum candidates do not claim. The construction plants secret trapdoors by using the label extended factor graph of the CSP while keeping the instance outwardly random. As supporting work, the authors also produce the first uniform error-correcting code whose low-density generator matrix is expanding yet permits efficient decoding after a 1-o(1) fraction of symbols are corrupted.

Core claim

We give a public key encryption scheme with plausible quasi-exponential security based on the conjectured intractability of two constraint satisfaction problems, both instantiated with a corruption rate of 1-o(1). The first is a large-alphabet random predicate CSP on strongly expanding factor graphs where most predicate outputs are replaced by random bits. The second is the standard kXOR problem on random factor graphs where most parity checks are replaced by random bits. Security follows from a new trapdoor-planting technique that operates on the label extended factor graph; the paper supplies lower bounds that rule out many natural attacks on these instances and, along the way, constructs,

What carries the argument

The label extended factor graph of a CSP, which is used to embed secret trapdoors into an instance that otherwise looks like a high-corruption random problem.

If this is right

The encryption scheme resists all attacks that run in quasi-exponential time provided the two CSP conjectures hold.
Lower bounds exclude attacks that rely on finding non-random structure inside the factor graphs of LARP-CSP instances.
The new error-correcting code permits efficient decoding after 1-o(1) corruptions while its generator matrix remains both low-density and expanding.
The same high-corruption instances can be used for encryption without sacrificing the claimed security level.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The trapdoor-planting method on label extended graphs may extend to other primitives that require embedding secrets inside average-case hard instances.
High-corruption CSPs could serve as a source of hardness for additional average-case cryptographic tasks beyond encryption.
Further lower bounds against additional families of attacks would give more evidence that the hardness conjectures are robust.

Load-bearing premise

The two high-corruption constraint satisfaction problems remain hard for any efficient algorithm even when almost every constraint has been replaced by a random value.

What would settle it

An efficient algorithm that recovers the secret key from the public key or solves the underlying LARP-CSP or kXOR instances with 1-o(1) corruption would break the scheme.

read the original abstract

We give a public key encryption scheme with plausible quasi-exponential security based on the conjectured intractability of two constraint satisfaction problems (CSPs), both of which are instantiated with a corruption rate of $1 - o(1)$. First, we conjecture the hardness of a new large alphabet random predicate CSP (LARP-CSP) defined over an arbitrary but strongly expanding factor graph, where the vast majority of predicate outputs are replaced with random outputs. Second, we conjecture the hardness of the standard $k$XOR problem defined over a random factor graph, again where the vast majority of parity computations are replaced with random bits. In support of our hardness conjecture for LARP-CSPs, we give a variety of lower bounds, ruling out many natural attacks including all known attacks that exploit non-random factor graphs. Our public key encryption scheme is the first to leverage high corruption CSPs while simultaneously achieving a plausible security level far above quasi-polynomial. At the heart of our work is a new method for planting cryptographic trapdoors based on the label extended factor graph for a CSP. Along the way to achieving our result, we give the first uniform construction of an error-correcting code that has an expanding, low density generator matrix while simultaneously allowing for efficient decoding from a $1 - o(1)$ fraction of corruptions.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper builds a PKE from two high-corruption CSP conjectures using a new label-extended trapdoor planting method and a uniform expanding LDGM code, but security is conditional and the reduction details need checking.

read the letter

The main point is a public-key encryption construction whose security reduces to the conjectured hardness of LARP-CSP and kXOR at corruption rate 1-o(1), with the goal of quasi-exponential security. They plant trapdoors via label-extended factor graphs and give lower bounds ruling out many natural attacks plus all known ones that rely on non-random graphs. Along the way they produce the first uniform expanding low-density generator matrix code that still decodes efficiently from 1-o(1) errors. That code construction looks independently useful for high-noise settings. The planting technique is the clearest technical novelty and seems cleanly motivated by the need to hide structure while preserving the CSP instance. The lower bounds provide some concrete support for the assumptions rather than just asserting them. The soft spots sit in the security argument. The reduction must show that the planted instances remain as hard as the random ones even after most outputs are replaced randomly, and that the code decoder does not create a distinguishing advantage or leak the trapdoor. The abstract does not spell out reduction tightness or how the random-output replacement interacts with the planted labels, so it is possible that subexponential attacks survive. If the planting introduces any detectable bias in the high-corruption regime, the quasi-exponential claim would not hold. This is aimed at researchers who work on average-case assumptions for cryptography and who want alternatives that target higher security levels than quasi-polynomial. A reader comfortable with CSPs and expanding graphs will get the most out of the new techniques. The paper deserves serious peer review because the construction and the code are specific enough to evaluate and the conjectures are stated plainly rather than hidden. I would send it to referees.

Referee Report

3 major / 2 minor

Summary. The manuscript constructs a public-key encryption scheme whose security is reduced to the conjectured intractability of two high-corruption (1-o(1)) CSPs: LARP-CSP on strongly expanding factor graphs with most predicate outputs replaced by random values, and kXOR on random graphs with most parities replaced by random bits. The construction relies on a new trapdoor-planting technique that uses the label-extended factor graph of the CSP instance; supporting results include lower bounds ruling out many natural attacks on LARP-CSP (including all known attacks that exploit non-random factor graphs) and the first uniform error-correcting code possessing both an expanding low-density generator matrix and an efficient decoder that tolerates a 1-o(1) fraction of corruptions.

Significance. If the two hardness conjectures are valid and the security reduction is tight, the result would supply the first PKE achieving plausible quasi-exponential security from high-corruption CSP assumptions, a regime that has not previously yielded schemes with security above quasi-polynomial. The accompanying uniform LDGM code construction is of independent interest for coding theory and may find applications outside cryptography.

major comments (3)

[Security reduction and trapdoor planting] The security reduction (centered on the label-extended factor graph planting method) must be shown to remain tight after the random-output replacement step that defines both LARP-CSP and kXOR; it is unclear whether the planted trapdoors preserve the exact distribution required by the conjectures or introduce a distinguishable structure that a subexponential algorithm could exploit even when the base CSP is hard.
[Lower bounds for LARP-CSP] The lower bounds claimed for LARP-CSP are stated to rule out attacks that exploit non-random factor graphs, yet the cryptographic instances are produced by a deliberate planting procedure that necessarily introduces non-random structure; the manuscript must verify that these bounds continue to apply to the planted instances or supply a separate argument that no new attack is enabled by the planting.
[Error-correcting code construction] The uniform ECC construction is asserted to be the first with both an expanding LDGM and efficient decoding from 1-o(1) corruptions; the decoder must be shown not to interact with the planted trapdoors in a way that leaks information about the secret key, and a precise comparison to prior non-uniform or low-corruption LDGM constructions is required to substantiate the novelty claim.

minor comments (2)

[Abstract] The abstract refers to 'a variety of lower bounds' without quantitative statements on the attack classes ruled out or the concrete security loss; expanding this description would improve readability.
[Notation and definitions] Notation for the corruption rate (1-o(1)) and the precise parameters of the expanding factor graphs should be defined once at the beginning of the technical sections and used consistently thereafter.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for their careful and constructive review of our manuscript. We address each major comment below with additional arguments and clarifications that we will incorporate into a revised version.

read point-by-point responses

Referee: [Security reduction and trapdoor planting] The security reduction (centered on the label-extended factor graph planting method) must be shown to remain tight after the random-output replacement step that defines both LARP-CSP and kXOR; it is unclear whether the planted trapdoors preserve the exact distribution required by the conjectures or introduce a distinguishable structure that a subexponential algorithm could exploit even when the base CSP is hard.

Authors: The trapdoor planting occurs on the label-extended factor graph prior to the random replacement of predicate outputs. The replacement step substitutes outputs with uniformly random values chosen independently of the planted labels and structure. As a result, the final distribution is identical to that of a standard LARP-CSP (or kXOR) instance under the conjecture. No distinguishable structure is introduced that would allow a subexponential attack beyond the base hardness assumption. We will add a formal lemma proving this distributional equivalence and tightness of the reduction in the revised manuscript. revision: yes
Referee: [Lower bounds for LARP-CSP] The lower bounds claimed for LARP-CSP are stated to rule out attacks that exploit non-random factor graphs, yet the cryptographic instances are produced by a deliberate planting procedure that necessarily introduces non-random structure; the manuscript must verify that these bounds continue to apply to the planted instances or supply a separate argument that no new attack is enabled by the planting.

Authors: The lower bounds hold for every strongly expanding factor graph. Our planting procedure is constructed to preserve strong expansion while localizing the non-random trapdoor structure to a negligible fraction of positions. This localized structure does not create global non-randomness or violate the expansion properties used in the bounds, so the ruled-out attacks remain inapplicable. We will add a dedicated subsection in the revised version that explicitly verifies the planted instances satisfy the hypotheses of the lower-bound theorems. revision: yes
Referee: [Error-correcting code construction] The uniform ECC construction is asserted to be the first with both an expanding LDGM and efficient decoding from 1-o(1) corruptions; the decoder must be shown not to interact with the planted trapdoors in a way that leaks information about the secret key, and a precise comparison to prior non-uniform or low-corruption LDGM constructions is required to substantiate the novelty claim.

Authors: The LDGM decoder receives only the corrupted codeword and has no access to the secret key or the planted trapdoors, which remain hidden in the private key. Consequently, decoding cannot leak secret-key information. To support the novelty claim we will expand the related-work discussion with a precise side-by-side comparison, emphasizing that earlier LDGM constructions are either non-uniform, tolerate only a constant fraction of errors, or lack an expanding generator matrix. revision: yes

Circularity Check

0 steps flagged

No circularity: security reduced to external conjectured CSP hardness with independent lower bounds

full rationale

The paper presents a PKE construction whose security is reduced to the conjectured intractability of LARP-CSP and kXOR at corruption rate 1-o(1). It supplies lower bounds that rule out many natural attacks on these CSPs, but these bounds are offered as supporting evidence for the conjecture rather than as a derivation that loops back to the scheme itself. No equations or steps in the provided abstract or description reduce by construction to fitted parameters, self-definitional quantities, or load-bearing self-citations. The trapdoor-planting technique via label-extended factor graphs is a new algorithmic method whose correctness is claimed to follow from the CSP assumptions, without the assumptions being defined in terms of the scheme.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 2 invented entities

The central claims rest on two domain-assumption hardness conjectures for the CSPs; the trapdoor method and error-correcting code are new elements introduced without external independent evidence.

axioms (2)

domain assumption LARP-CSP over strongly expanding factor graph with vast majority of predicate outputs replaced by random outputs is intractable.
Primary conjectured hardness assumption underlying the PKE security.
domain assumption kXOR over random factor graph with vast majority of parity computations replaced by random bits is intractable.
Secondary conjectured hardness assumption supporting the construction.

invented entities (2)

Label-extended factor graph trapdoor planting method no independent evidence
purpose: Embed cryptographic trapdoors into CSP instances to enable decryption.
New technique introduced for the PKE construction.
Uniform error-correcting code with expanding low-density generator matrix decodable from 1-o(1) corruptions no independent evidence
purpose: Support the cryptographic construction with efficient decoding under high corruption.
Claimed first uniform construction of such a code.

pith-pipeline@v0.9.0 · 5531 in / 1689 out tokens · 59719 ms · 2026-05-10T16:31:31.385832+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

62 extracted references · 62 canonical work pages

[1]

Ifζ(i)̸=⊥, thenG ′ i =H ζ(i)

work page
[2]

Then delete all columns ofG ′ which arenotindexed by some symbols i of the secretsas produced in KeyGen, and let the width ofG ′ ben ′′

Otherwise,G ′ i =0 |Σ|. Then delete all columns ofG ′ which arenotindexed by some symbols i of the secretsas produced in KeyGen, and let the width ofG ′ ben ′′. Notice that by definition ofζ, we have thatG ′ is simply a copy of Gwhere:

work page
[3]

Some rows are replaced with0. 19

work page
[4]

The columns are permuted

work page
[5]

This happens whenever there exist two indicesi, j∈[n]such thati̸=jbuts i =s j

Some of the columns might be “merged” by taking their coordinate-wise locical-OR. This happens whenever there exist two indicesi, j∈[n]such thati̸=jbuts i =s j. By Claim 4.4, we know that with probability1−o(1), none of the columns are merged. In this case the linear codeC ′ ={G ′x:x∈F n′′ 2 }is the same asC={Gx:x∈F n 2 }, but where a fixed set of coordin...

work page
[6]

?” if and only ifζ(i) =⊥, so the probability thatw i =“?

By Claim 4.2, we know thatζ(i) =⊥independently with probabilityαfor alli. By the construction ofw, we know thatw i =“?” if and only ifζ(i) =⊥, so the probability thatw i =“?” is exactlyα, independently for each coordinate

work page
[7]

Combining this with the erasure probability, we have that the probability a coordinate isnoterased butiscorrupted will be exactly(1−α)β, independently for each coordinate

By definition ofEnc, we know that every non-erased coordinate ofwwill be set to a random value inF 2 independently with probabilityβ. Combining this with the erasure probability, we have that the probability a coordinate isnoterased butiscorrupted will be exactly(1−α)β, independently for each coordinate

work page
[8]

?”} m sampled as follows: ri = ® “?

Otherwise, the coordinate will be left un-erased and un-corrupted. Claim 4.8.Consider a PKE scheme identical to the one in Section 4.1, but where we remove Step 5 and Step 6 in algorithmKeyGen. Sample(pk,sk)←KeyGen(1 λ)andct←Enc(1 λ,pk,1), and then run Dec(1λ,sk,ct). Over the random coins ofKeyGenandEnc, the distribution over vectorswin algorithm Decis id...

work page
[9]

In the case that we encrypted a bitb= 0, the distribution on vectorswis withino(1)statistical distance of the distribution on vectorsc ′ for which Pr Distinguish(1n,G,c ′) = 0 ≥1−o(1)

work page
[10]

Takingλsufficiently large completes the proof of correctness

In the case that we encrypted a bitb= 1, the distribution on vectorswis withino(1)statistical distance of the distribution on vectorsrfor which Pr[Distinguish(1n,G,r) = 1]≥1−o(1) 20 So for the true PKE scheme, Pr î (pk,sk)←KeyGen(1 λ);Dec(1 λ,sk,Enc(1 λ,pk, b)) =b ó ≥1−o(1). Takingλsufficiently large completes the proof of correctness. 4.3 Security We use...

work page
[11]

If the output is(⊥,⊥)then returnA(⊥,⊥)

RunH 0,$(1λ). If the output is(⊥,⊥)then returnA(⊥,⊥)

work page
[12]

Bhas advantage at least0.3>1/4, which is a contradiction

Otherwise, returnA(H,b). Bhas advantage at least0.3>1/4, which is a contradiction. 22 Claim 4.12.Assume that Conjecture 3.1 (LARP-CSP) holds with corruption rateα. Then for all sufficiently largeλ, for allλ O(1)-size non-uniform algorithmsA, Pr î A(H1,$(1λ)) = 1 ó −Pr î A(H1(1λ)) = 1 ó <0.3 Proof.Identical to the proof of Claim 4.10. Composing Claims 4.10...

work page
[13]

The code{Gx:x∈F n 2 }is a subcode of the Reed-Muller code RM((⌈logn⌉) cm,(⌈logn⌉) 2)

work page
[14]

Proof.We propose the following algorithm

With1−o(1)probability over the coins ofK ck,cm,Gis(1−o(1), n 1−o(1))-expanding. Proof.We propose the following algorithm. (Recall that all logarithms are taken base 2.) G←K ck,cm(1n):

work page
[15]

Setk := (⌈logn⌉) ck,m := 2(⌈logn⌉) cm ,w :=⌊log(n/k)⌋

work page
[16]

, g(1,w), g(2,1),

Samplekwrandom degree-⌈logn⌉polynomials g(1,1), . . . , g(1,w), g(2,1), . . . , g(k,w) :F logm 2 →F 2. 23

work page
[17]

(a) Each row is indexed by a pointp∈F logm 2 (b) Each column is indexed by a pointq∈F w 2

For alli∈[k], we construct a matrixM (i) ∈F m×2w 2 as follows. (a) Each row is indexed by a pointp∈F logm 2 (b) Each column is indexed by a pointq∈F w 2 . (c) SetM (i) p,q = 1if and only ifg (i,j)(p) =q j for allj∈[w], or equivalently setM (i) p,q = 1if and only if the concatenation of the evaluationsg (i,1)(p)∥. . .∥g (i,w)(p)equalsq

work page
[18]

∥M (k) ó , and then append zero columns until the width is exactlyn

SetG= î M(1)∥. . .∥M (k) ó , and then append zero columns until the width is exactlyn

work page
[19]

By construction, the algorithm runs in2 O((logn) cm) time, andGis a matrix overF 2 of widthnand heightm

OutputG. By construction, the algorithm runs in2 O((logn) cm) time, andGis a matrix overF 2 of widthnand heightm. To show that every row has exactlyknonzero entries, it suffices to show that each matrixM (i) has exactly one nonzero entry per row. This follows because, for every pointp∈F logm 2 , there is exactly one pointq∈F w 2 such thatg (i,j)(p) =q j f...

work page
[20]

Show that arandommatrix with the same parameters will be a(1−o(1), n 1−o(1))-expander

work page
[21]

∥M (k) ó isstatistically random

Show that,on a local level,the matrix î M(1)∥. . .∥M (k) ó isstatistically random

work page
[22]

?”} m ofc: c′ i =    “?

Compose these results via a union bound to show that î M(1)∥. . .∥M (k) ó , and henceG, is a(1− o(1), n1−o(1))-expander. Claim 5.1.LetR (1), . . . ,R(k) ∈F t×2w 2 be sampled at random, conditioned on each matrix having exactly 1 nonzero entry per row, and letR := î R(1)∥. . .∥R (k) ó . Then assumingnis sufficiently large and1≤t≤ 2w/(⌈logn⌉) 2, with probab...

work page
[23]

Thenc ′ disagrees withcon less thanz ∗ coordinates with probability1−o(1)

Letcbe a random codeword from RM(d, d 1/3), and letc ′ be the vectorcsubjected to corruptions of rateγ. Thenc ′ disagrees withcon less thanz ∗ coordinates with probability1−o(1). Consequently D(c′)disagrees withc ′ on less than thanz ∗ coordinates with probability1−o(1)

work page
[24]

With probability1−o(1), for allc∈RM(d, d 1/3),rdisagrees withc on more thanz ∗ coordinates

Letr∈F m 2 be a random vector. With probability1−o(1), for allc∈RM(d, d 1/3),rdisagrees withc on more thanz ∗ coordinates. SinceDoutputs a vector in RM(d, d 1/3), we have that with probability 1−o(1),D(r)disagrees withron more than thanz ∗ coordinates. So the distinguisher just invokesD, counts the number of coordinates on which the input vector and outpu...

work page
[26]

don’t care

Planted distributionP:(H,F,b), where we samples∈Σ n at random and set bi =f i(sNH(i,1), . . . ,sNH(i,k)). For a given pair(H,F), letQ H,F denote the distribution on vectorsbas sampled in (1), andP H,F denote the distribution on vectorsbas sampled in (2). 28 6.1 Low Complexity Embedding Attacks As discussed in Section 1.1 of the introduction, there are kno...

work page
[27]

The challenger fixes parametersm, n, kand alphabetsΣ,Γ. She also fixes the description of (a) A null distributionD H,F over vectorsb∈Γ m, (b) A planted distributionD ′ H,F over vectorsb∈Γ m, and (c) A distributionZover sets of functionsF={f i : Σk →Γ} i∈[m]. BothD H,F andD ′ H,F depend on a(1−o(1), n 1−o(1))-expanding(m, n, k)-matrixHto be fixed later by ...

work page
[28]

After viewing the descriptions ofD H,F,D ′ H,F, andZ, the adversary spends unbounded time to choose a(1−o(1), n 1−o(1))-expanding(m, n, k)-matrixHalong with a tuple(F, d,L,Ψ), where (a)Fis any finite field, (b)dis an embedding dimension parameter, (c)L ⊆ {F∪ ⊥} md is any subset of vectors, and (d)Ψ :F md → {F∪ ⊥} md is any transformation

work page
[30]

testing structure

Based onH,F, the description ofD H,F, and the description ofD ′ H,F, the adversary spends un- bounded time to fix a tuple(Φ, π, h), where (a)Φ ={ϕ i : Γ→F d}i∈[m] is any set of (not necessarily injective) functions. (b)π:F md →F md is any affine transformation. (c)h:{0, . . . , md} → {0,1}is an acceptance predicate. The adversary wins the game if and only...

work page
[31]

She also fixes (a) The null distributionD H,F as the uniform distribution over vectorsb∈ {0,1} m

The challenger fixes parameters(m, n, k) = (n logO(1) n, n,log O(1) n)and alphabets(Σ,Γ) = ({0,1}, {0,1}). She also fixes (a) The null distributionD H,F as the uniform distribution over vectorsb∈ {0,1} m. (b) The planted distributionD ′ H,F as the distribution over vectorsb∈ {0,1} m sampled by picking s∈ {0,1} n at random and then setting bi =f i(sNH(i,1)...

work page
[32]

She also fixes a tuple(F, d,L,Ψ), where (a)F :=F 2, (b)d := 1, (c)L ⊆ {F 2 ∪ ⊥} md is the set of all truth tables for sufficiently small AC0[+]circuits (the symbol ⊥is not used)

The adversary constructs a(1−o(1), n 1−o(1))-expanding(m, n, k)-matrixHthat is described by a sufficiently small AC0[+]circuit. She also fixes a tuple(F, d,L,Ψ), where (a)F :=F 2, (b)d := 1, (c)L ⊆ {F 2 ∪ ⊥} md is the set of all truth tables for sufficiently small AC0[+]circuits (the symbol ⊥is not used). (d)Ψ :F md 2 → {F2 ∪ ⊥} md is the identity transfo...

work page
[33]

The challenger samples a set of functionsFfrom the distributionZ

work page
[34]

(b)πis the identity transformation

The adversary spends unbounded time to fix a tuple(Φ, π, h), where (a) Everyϕ i ∈Φjust casts from{0,1}to the fieldF 2 by mapping zero to zero and one to one. (b)πis the identity transformation. (c)his the function which outputs 1 iff its input is zero. Now because most functions were set to the identity, if we abuse notation and assume thatbis already ove...

work page
[36]

,sNH(i,k))

Planted distributionP:(H,F,b), where we samples∈Σ n at random and set bi =f i(sNH(i,1), . . . ,sNH(i,k)). For a given pair(H,F), letQ H,F denote the distribution on vectorsbas sampled in (1), andP H,F denote the distribution on vectorsbas sampled in (2). Now we give a formal statement of the lower bound. Theorem 6.2.Fix any(1−o(1), n 1−o(1))-expanding(m, ...

work page
[37]

Finite fieldFof order2≤ |F| ≤2 |Σ|o(k) ,

work page
[38]

Embedding dimension parameter1≤d≤m O(1),

work page
[39]

SubsetL ⊆ {F∪ ⊥} md, and 32

work page
[40]

After this, sample the set of functionsFas in Problem 1

TransformationΨ :F md → {F∪ ⊥} md. After this, sample the set of functionsFas in Problem 1. Then with probability1−exp ¶ −|Σ|Ω(k) © , the following holds. For all

work page
[41]

, ϕm : Γ→F d,

Functionsϕ 1, . . . , ϕm : Γ→F d,

work page
[42]

Affine transformationsπ:F md →F md, and

work page
[43]

, md} → {0,1}, we have Pr b∼PH,F h h dist’ Ψπϕ(b1)∥

Acceptance predicatesh:{0, . . . , md} → {0,1}, we have Pr b∼PH,F h h dist’ Ψπϕ(b1)∥. . .∥ϕ(b m) ,L = 1 i −Pr b∼QH,F h h dist’ Ψπϕ(b1)∥. . .∥ϕ(b m) ,L = 1 i ≤ |Σ| −Ω(k), whereQ H,F andP H,F are the null and planted distributions for Problem 1, respectively. In the proof Theorem 6.2, we need a way to formalize the dependencies between random variables. Def...

work page
[44]

Show that if(F, d,L,Ψ)and(Φ, π, h)are fixed before sampling the random functions inF, there is a sharp tail bound showing that the test almost surely has negligible advantage

work page
[45]

Pr b∼PH,F [T(b) = 1]−Pr b∼QH,F [T(b) = 1] ≥ |Σ| −k/10 # is at most2 −|Σ|(4/5−o(1))k . We only prove the upper bound for Pr F ∼U

Union bound over all choices of(Φ, π, h), showing that with high probability there does not exist a good test even if an adversary is allowed to fix(Φ, π, h)after examiningF. 33 Claim 6.5.Fix an(m, n, k)-graphHand any choice of(F, d,L,Ψ)and(Φ, π, h). Then samplemrandom functionsf i : Σk →Γ, and letFbe the set of allf i. With probability at least1−2 −|Σ|(4...

work page
[47]

,sNH(i,k))

Planted distributionP:(H,F,b), where we samples∈Σ n at random and set bi =f i(sNH(i,1), . . . ,sNH(i,k)). To analyze this problem in terms of low degree polynomials, we need to find the right input formulation. Indeed if we only examine the pair(H,b)thenbis statistically random, because eachf i is a random function. We will instead represent the problem u...

work page
[48]

, jk)∈ X, for all(σ j1,

Null distributionQ: For all(j 1, . . . , jk)∈ X, for all(σ j1, . . . , σjk)∈Σ k, add the edge((j1, σj1), . . . , (jk, σjk))independently with probability1/|Γ|

work page
[49]

irrelevant,

Planted distributionP: Perform the same procedure as in distributionQ. Then samples∈Σ k at random, and for all(j 1, . . . , jk)∈ Xadd the edge((j 1,s j1), . . . ,(jk,s jk))if it doesn’t already exist. 36 The task is to determine, given(H, K), which distributionKwas sampled from. Remark 6.6.The pair(H, K)contains significantly less information than the tup...

work page
[50]

Null distributionQ:(H,F,b), whereb∈Γ m is sampled uniformly at random

work page
[51]

,sNH(i,k))

Planted distributionP:(H,F,b), where we samples∈Σ n at random and set bi =f i(sNH(i,1), . . . ,sNH(i,k)). For the lower bound in this section,we assume that|Σ|is a power of two. Formalizing the Proof System.Polynomial calculus refutations work as follows [CEI96]. We first ini- tialize a system of polynomialsg 1(X) = 0, . . . gm(X) = 0in a set of variables...

work page
[52]

Settingg(X) =g ′(X) +g ′′(X)for any polynomialsg ′(X), g ′′(X)already in the system

work page
[53]

Settingg(X) =X i ·g ′(X)for any variableX i and any polynomialg ′(X)already in the system. The goal of a refutation is to derive the statement1 = 0via these operations; such a derivation is only possible if the original system was unsatisfiable, because the derivation rules cannot derive an unsatisfiable system from a satisfiable one. As in the lower boun...

work page
[54]

, ϕn : Σ→F log2 |Σ| 2 for each variableX j

The adversary non-deterministically finds the best (bijective) embeddingsϕ 1, . . . , ϕn : Σ→F log2 |Σ| 2 for each variableX j. LetX ′ be a matrix ofnlog 2 |Σ|variables overF 2 such thatX ′ j,1, . . . ,X′ j,log2 |Σ| representsX j. 18A smarter algorithm could conceivably exploit nontrivial cancellations that occur without needing to fully distribute the po...

work page
[55]

,X′ NH(i,1),log2 |Σ|,X ′ NH(i,2),1,

The adversary initializes a polynomial system overX ′ by appending, for eachi∈[m], the constraint f ′ i(X′) = 0, wheref ′ i is the unique polynomial overF 2 such that (a)f ′ i is supported on the variable setX′ NH(i,1),1, . . . ,X′ NH(i,1),log2 |Σ|,X ′ NH(i,2),1, . . . ,X′ NH(i,k),log2 |Σ|. (b) For all(σ 1, . . . , σk)∈Σ k such thatf i(σ1, . . . , σk) =b ...

work page
[56]

converted

The adversary (non-deterministically) appends a new polynomialg(X ′) = 0to the system, by either (a) Settingg(X ′) =g ′(X′) +g ′′(X′)for any polynomialsg ′(X′), g′′(X′)already in the system. (b) Settingg(X ′) =X ′ j,ℓ ·g ′(X′)for any variableX ′ j,ℓ and any polynomialg ′(X′)already in the system. The goal of the adversary is derive the equation1 = 0, and ...

work page
[57]

Every polynomial depends on at mostk ′ variables

work page
[58]

For all subsetsGof at least 1 polynomial and at mosttpolynomials,Gdepends on at least(1−o(1))tk ′ distinct variables

work page
[59]

Then any polynomial calculus refutation of the systemg 1(X) = 0,

Every polynomial has rational degreeΩ(k ′). Then any polynomial calculus refutation of the systemg 1(X) = 0, . . . , gm(X) = 0has at least one mono- mial of degreeΩ(tk ′). 43 Remark 6.16.The conditions we impose on the polynomial system in this lemma are equivalent to those in Theorem 3.8 from [AR01], but phrased slightly differently. As stated by Alekhno...

work page
[60]

, σk)∈Σ k such thatf i(σ1,

For all(σ 1, . . . , σk)∈Σ k such thatf i(σ1, . . . , σk) =b i, we have f ′ i(ϕNH(i,1)(σ1), . . . , ϕNH(i,k)(σk)) = 0

work page
[61]

Proof.First we give a sharp tail bound on the probability that, for a single choice of indexi, valueb i, embeddingsϕ 1,

For all other inputs,f ′ i equals1. Proof.First we give a sharp tail bound on the probability that, for a single choice of indexi, valueb i, embeddingsϕ 1, . . . , ϕk, and low degree polynomialsp, q, a random functionf i will satisfypf i =q. Then we union bound over all choices ofi,b i, ϕ1, . . . , ϕk, p, qto complete the proof. Claim 6.19.Fix an indexi∈[...

work page arXiv 2010
[62]

The quasi- polynomial low-degree conjecture is false.arXiv preprint arXiv:2505.17360, 2025

5 [BBK+21] Afonso S Bandeira, Jess Banks, Dmitriy Kunisky, Christopher Moore, and Alex Wein. Spectral planting and the hardness of refuting cuts, colorability, and communities in random graphs. In Conference on Learning Theory, pages 410–473. PMLR, 2021. 5 [BCG+12] Aditya Bhaskara, Moses Charikar, Venkatesan Guruswami, Aravindan Vijayaraghavan, and Yuan Z...

work page arXiv 2021
[63]

Cornell University,

5 [Hop18] Samuel Hopkins.Statistical inference and the sum of squares method. Cornell University,

work page
[64]

One-way secret-key agreement and applications to circuit polarization and immunization of public-key encryption

3, 37, 38 [HR05] Thomas Holenstein and Renato Renner. One-way secret-key agreement and applications to circuit polarization and immunization of public-key encryption. InAnnual International Cryp- tology Conference, pages 478–493. Springer, 2005. 8, 12, 13 [IPS99] Russell Impagliazzo, Pavel Pudl ´ak, and Jiri Sgall. Lower bounds for the polynomial calculus...

work page 2005
[65]

Schloss Dagstuhl, 2017

5, 37, 38 [KZ17] Andrei Krokhin and Stanislav Zivny.The constraint satisfaction problem: Complexity and approximability. Schloss Dagstuhl, 2017. 1 [LG24] Yuetian Luo and Chao Gao. Computational lower bounds for graphon estimation via low- degree polynomials.The Annals of Statistics, 52(5):2318–2348, 2024. 5 [Lyu05] Vadim Lyubashevsky. The parity problem i...

work page arXiv 2017
[66]

Finding correlations in subquadratic time, with applications to learning pari- ties and juntas

2 [Val12] Gregory Valiant. Finding correlations in subquadratic time, with applications to learning pari- ties and juntas. In2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 11–20. IEEE, 2012. 6 [WEAM19] Alexander Wein, Ahmed El Alaoui, and Cristopher Moore. The kikuchi hierarchy and tensor pca.Journal of the ACM, 2019. 1, 7 51 [W...

work page 2012

[1] [1]

Ifζ(i)̸=⊥, thenG ′ i =H ζ(i)

work page

[2] [2]

Then delete all columns ofG ′ which arenotindexed by some symbols i of the secretsas produced in KeyGen, and let the width ofG ′ ben ′′

Otherwise,G ′ i =0 |Σ|. Then delete all columns ofG ′ which arenotindexed by some symbols i of the secretsas produced in KeyGen, and let the width ofG ′ ben ′′. Notice that by definition ofζ, we have thatG ′ is simply a copy of Gwhere:

work page

[3] [3]

Some rows are replaced with0. 19

work page

[4] [4]

The columns are permuted

work page

[5] [5]

This happens whenever there exist two indicesi, j∈[n]such thati̸=jbuts i =s j

Some of the columns might be “merged” by taking their coordinate-wise locical-OR. This happens whenever there exist two indicesi, j∈[n]such thati̸=jbuts i =s j. By Claim 4.4, we know that with probability1−o(1), none of the columns are merged. In this case the linear codeC ′ ={G ′x:x∈F n′′ 2 }is the same asC={Gx:x∈F n 2 }, but where a fixed set of coordin...

work page

[6] [6]

?” if and only ifζ(i) =⊥, so the probability thatw i =“?

By Claim 4.2, we know thatζ(i) =⊥independently with probabilityαfor alli. By the construction ofw, we know thatw i =“?” if and only ifζ(i) =⊥, so the probability thatw i =“?” is exactlyα, independently for each coordinate

work page

[7] [7]

Combining this with the erasure probability, we have that the probability a coordinate isnoterased butiscorrupted will be exactly(1−α)β, independently for each coordinate

By definition ofEnc, we know that every non-erased coordinate ofwwill be set to a random value inF 2 independently with probabilityβ. Combining this with the erasure probability, we have that the probability a coordinate isnoterased butiscorrupted will be exactly(1−α)β, independently for each coordinate

work page

[8] [8]

?”} m sampled as follows: ri = ® “?

Otherwise, the coordinate will be left un-erased and un-corrupted. Claim 4.8.Consider a PKE scheme identical to the one in Section 4.1, but where we remove Step 5 and Step 6 in algorithmKeyGen. Sample(pk,sk)←KeyGen(1 λ)andct←Enc(1 λ,pk,1), and then run Dec(1λ,sk,ct). Over the random coins ofKeyGenandEnc, the distribution over vectorswin algorithm Decis id...

work page

[9] [9]

In the case that we encrypted a bitb= 0, the distribution on vectorswis withino(1)statistical distance of the distribution on vectorsc ′ for which Pr Distinguish(1n,G,c ′) = 0 ≥1−o(1)

work page

[10] [10]

Takingλsufficiently large completes the proof of correctness

In the case that we encrypted a bitb= 1, the distribution on vectorswis withino(1)statistical distance of the distribution on vectorsrfor which Pr[Distinguish(1n,G,r) = 1]≥1−o(1) 20 So for the true PKE scheme, Pr î (pk,sk)←KeyGen(1 λ);Dec(1 λ,sk,Enc(1 λ,pk, b)) =b ó ≥1−o(1). Takingλsufficiently large completes the proof of correctness. 4.3 Security We use...

work page

[11] [11]

If the output is(⊥,⊥)then returnA(⊥,⊥)

RunH 0,$(1λ). If the output is(⊥,⊥)then returnA(⊥,⊥)

work page

[12] [12]

Bhas advantage at least0.3>1/4, which is a contradiction

Otherwise, returnA(H,b). Bhas advantage at least0.3>1/4, which is a contradiction. 22 Claim 4.12.Assume that Conjecture 3.1 (LARP-CSP) holds with corruption rateα. Then for all sufficiently largeλ, for allλ O(1)-size non-uniform algorithmsA, Pr î A(H1,$(1λ)) = 1 ó −Pr î A(H1(1λ)) = 1 ó <0.3 Proof.Identical to the proof of Claim 4.10. Composing Claims 4.10...

work page

[13] [13]

The code{Gx:x∈F n 2 }is a subcode of the Reed-Muller code RM((⌈logn⌉) cm,(⌈logn⌉) 2)

work page

[14] [14]

Proof.We propose the following algorithm

With1−o(1)probability over the coins ofK ck,cm,Gis(1−o(1), n 1−o(1))-expanding. Proof.We propose the following algorithm. (Recall that all logarithms are taken base 2.) G←K ck,cm(1n):

work page

[15] [15]

Setk := (⌈logn⌉) ck,m := 2(⌈logn⌉) cm ,w :=⌊log(n/k)⌋

work page

[16] [16]

, g(1,w), g(2,1),

Samplekwrandom degree-⌈logn⌉polynomials g(1,1), . . . , g(1,w), g(2,1), . . . , g(k,w) :F logm 2 →F 2. 23

work page

[17] [17]

(a) Each row is indexed by a pointp∈F logm 2 (b) Each column is indexed by a pointq∈F w 2

For alli∈[k], we construct a matrixM (i) ∈F m×2w 2 as follows. (a) Each row is indexed by a pointp∈F logm 2 (b) Each column is indexed by a pointq∈F w 2 . (c) SetM (i) p,q = 1if and only ifg (i,j)(p) =q j for allj∈[w], or equivalently setM (i) p,q = 1if and only if the concatenation of the evaluationsg (i,1)(p)∥. . .∥g (i,w)(p)equalsq

work page

[18] [18]

∥M (k) ó , and then append zero columns until the width is exactlyn

SetG= î M(1)∥. . .∥M (k) ó , and then append zero columns until the width is exactlyn

work page

[19] [19]

By construction, the algorithm runs in2 O((logn) cm) time, andGis a matrix overF 2 of widthnand heightm

OutputG. By construction, the algorithm runs in2 O((logn) cm) time, andGis a matrix overF 2 of widthnand heightm. To show that every row has exactlyknonzero entries, it suffices to show that each matrixM (i) has exactly one nonzero entry per row. This follows because, for every pointp∈F logm 2 , there is exactly one pointq∈F w 2 such thatg (i,j)(p) =q j f...

work page

[20] [20]

Show that arandommatrix with the same parameters will be a(1−o(1), n 1−o(1))-expander

work page

[21] [21]

∥M (k) ó isstatistically random

Show that,on a local level,the matrix î M(1)∥. . .∥M (k) ó isstatistically random

work page

[22] [22]

?”} m ofc: c′ i =    “?

Compose these results via a union bound to show that î M(1)∥. . .∥M (k) ó , and henceG, is a(1− o(1), n1−o(1))-expander. Claim 5.1.LetR (1), . . . ,R(k) ∈F t×2w 2 be sampled at random, conditioned on each matrix having exactly 1 nonzero entry per row, and letR := î R(1)∥. . .∥R (k) ó . Then assumingnis sufficiently large and1≤t≤ 2w/(⌈logn⌉) 2, with probab...

work page

[23] [23]

Thenc ′ disagrees withcon less thanz ∗ coordinates with probability1−o(1)

Letcbe a random codeword from RM(d, d 1/3), and letc ′ be the vectorcsubjected to corruptions of rateγ. Thenc ′ disagrees withcon less thanz ∗ coordinates with probability1−o(1). Consequently D(c′)disagrees withc ′ on less than thanz ∗ coordinates with probability1−o(1)

work page

[24] [24]

With probability1−o(1), for allc∈RM(d, d 1/3),rdisagrees withc on more thanz ∗ coordinates

Letr∈F m 2 be a random vector. With probability1−o(1), for allc∈RM(d, d 1/3),rdisagrees withc on more thanz ∗ coordinates. SinceDoutputs a vector in RM(d, d 1/3), we have that with probability 1−o(1),D(r)disagrees withron more than thanz ∗ coordinates. So the distinguisher just invokesD, counts the number of coordinates on which the input vector and outpu...

work page

[25] [26]

don’t care

Planted distributionP:(H,F,b), where we samples∈Σ n at random and set bi =f i(sNH(i,1), . . . ,sNH(i,k)). For a given pair(H,F), letQ H,F denote the distribution on vectorsbas sampled in (1), andP H,F denote the distribution on vectorsbas sampled in (2). 28 6.1 Low Complexity Embedding Attacks As discussed in Section 1.1 of the introduction, there are kno...

work page

[26] [27]

The challenger fixes parametersm, n, kand alphabetsΣ,Γ. She also fixes the description of (a) A null distributionD H,F over vectorsb∈Γ m, (b) A planted distributionD ′ H,F over vectorsb∈Γ m, and (c) A distributionZover sets of functionsF={f i : Σk →Γ} i∈[m]. BothD H,F andD ′ H,F depend on a(1−o(1), n 1−o(1))-expanding(m, n, k)-matrixHto be fixed later by ...

work page

[27] [28]

After viewing the descriptions ofD H,F,D ′ H,F, andZ, the adversary spends unbounded time to choose a(1−o(1), n 1−o(1))-expanding(m, n, k)-matrixHalong with a tuple(F, d,L,Ψ), where (a)Fis any finite field, (b)dis an embedding dimension parameter, (c)L ⊆ {F∪ ⊥} md is any subset of vectors, and (d)Ψ :F md → {F∪ ⊥} md is any transformation

work page

[28] [30]

testing structure

Based onH,F, the description ofD H,F, and the description ofD ′ H,F, the adversary spends un- bounded time to fix a tuple(Φ, π, h), where (a)Φ ={ϕ i : Γ→F d}i∈[m] is any set of (not necessarily injective) functions. (b)π:F md →F md is any affine transformation. (c)h:{0, . . . , md} → {0,1}is an acceptance predicate. The adversary wins the game if and only...

work page

[29] [31]

She also fixes (a) The null distributionD H,F as the uniform distribution over vectorsb∈ {0,1} m

The challenger fixes parameters(m, n, k) = (n logO(1) n, n,log O(1) n)and alphabets(Σ,Γ) = ({0,1}, {0,1}). She also fixes (a) The null distributionD H,F as the uniform distribution over vectorsb∈ {0,1} m. (b) The planted distributionD ′ H,F as the distribution over vectorsb∈ {0,1} m sampled by picking s∈ {0,1} n at random and then setting bi =f i(sNH(i,1)...

work page

[30] [32]

She also fixes a tuple(F, d,L,Ψ), where (a)F :=F 2, (b)d := 1, (c)L ⊆ {F 2 ∪ ⊥} md is the set of all truth tables for sufficiently small AC0[+]circuits (the symbol ⊥is not used)

The adversary constructs a(1−o(1), n 1−o(1))-expanding(m, n, k)-matrixHthat is described by a sufficiently small AC0[+]circuit. She also fixes a tuple(F, d,L,Ψ), where (a)F :=F 2, (b)d := 1, (c)L ⊆ {F 2 ∪ ⊥} md is the set of all truth tables for sufficiently small AC0[+]circuits (the symbol ⊥is not used). (d)Ψ :F md 2 → {F2 ∪ ⊥} md is the identity transfo...

work page

[31] [33]

The challenger samples a set of functionsFfrom the distributionZ

work page

[32] [34]

(b)πis the identity transformation

The adversary spends unbounded time to fix a tuple(Φ, π, h), where (a) Everyϕ i ∈Φjust casts from{0,1}to the fieldF 2 by mapping zero to zero and one to one. (b)πis the identity transformation. (c)his the function which outputs 1 iff its input is zero. Now because most functions were set to the identity, if we abuse notation and assume thatbis already ove...

work page

[33] [36]

,sNH(i,k))

Planted distributionP:(H,F,b), where we samples∈Σ n at random and set bi =f i(sNH(i,1), . . . ,sNH(i,k)). For a given pair(H,F), letQ H,F denote the distribution on vectorsbas sampled in (1), andP H,F denote the distribution on vectorsbas sampled in (2). Now we give a formal statement of the lower bound. Theorem 6.2.Fix any(1−o(1), n 1−o(1))-expanding(m, ...

work page

[34] [37]

Finite fieldFof order2≤ |F| ≤2 |Σ|o(k) ,

work page

[35] [38]

Embedding dimension parameter1≤d≤m O(1),

work page

[36] [39]

SubsetL ⊆ {F∪ ⊥} md, and 32

work page

[37] [40]

After this, sample the set of functionsFas in Problem 1

TransformationΨ :F md → {F∪ ⊥} md. After this, sample the set of functionsFas in Problem 1. Then with probability1−exp ¶ −|Σ|Ω(k) © , the following holds. For all

work page

[38] [41]

, ϕm : Γ→F d,

Functionsϕ 1, . . . , ϕm : Γ→F d,

work page

[39] [42]

Affine transformationsπ:F md →F md, and

work page

[40] [43]

, md} → {0,1}, we have Pr b∼PH,F h h dist’ Ψπϕ(b1)∥

Acceptance predicatesh:{0, . . . , md} → {0,1}, we have Pr b∼PH,F h h dist’ Ψπϕ(b1)∥. . .∥ϕ(b m) ,L = 1 i −Pr b∼QH,F h h dist’ Ψπϕ(b1)∥. . .∥ϕ(b m) ,L = 1 i ≤ |Σ| −Ω(k), whereQ H,F andP H,F are the null and planted distributions for Problem 1, respectively. In the proof Theorem 6.2, we need a way to formalize the dependencies between random variables. Def...

work page

[41] [44]

Show that if(F, d,L,Ψ)and(Φ, π, h)are fixed before sampling the random functions inF, there is a sharp tail bound showing that the test almost surely has negligible advantage

work page

[42] [45]

Pr b∼PH,F [T(b) = 1]−Pr b∼QH,F [T(b) = 1] ≥ |Σ| −k/10 # is at most2 −|Σ|(4/5−o(1))k . We only prove the upper bound for Pr F ∼U

Union bound over all choices of(Φ, π, h), showing that with high probability there does not exist a good test even if an adversary is allowed to fix(Φ, π, h)after examiningF. 33 Claim 6.5.Fix an(m, n, k)-graphHand any choice of(F, d,L,Ψ)and(Φ, π, h). Then samplemrandom functionsf i : Σk →Γ, and letFbe the set of allf i. With probability at least1−2 −|Σ|(4...

work page

[43] [47]

,sNH(i,k))

Planted distributionP:(H,F,b), where we samples∈Σ n at random and set bi =f i(sNH(i,1), . . . ,sNH(i,k)). To analyze this problem in terms of low degree polynomials, we need to find the right input formulation. Indeed if we only examine the pair(H,b)thenbis statistically random, because eachf i is a random function. We will instead represent the problem u...

work page

[44] [48]

, jk)∈ X, for all(σ j1,

Null distributionQ: For all(j 1, . . . , jk)∈ X, for all(σ j1, . . . , σjk)∈Σ k, add the edge((j1, σj1), . . . , (jk, σjk))independently with probability1/|Γ|

work page

[45] [49]

irrelevant,

Planted distributionP: Perform the same procedure as in distributionQ. Then samples∈Σ k at random, and for all(j 1, . . . , jk)∈ Xadd the edge((j 1,s j1), . . . ,(jk,s jk))if it doesn’t already exist. 36 The task is to determine, given(H, K), which distributionKwas sampled from. Remark 6.6.The pair(H, K)contains significantly less information than the tup...

work page

[46] [50]

Null distributionQ:(H,F,b), whereb∈Γ m is sampled uniformly at random

work page

[47] [51]

,sNH(i,k))

Planted distributionP:(H,F,b), where we samples∈Σ n at random and set bi =f i(sNH(i,1), . . . ,sNH(i,k)). For the lower bound in this section,we assume that|Σ|is a power of two. Formalizing the Proof System.Polynomial calculus refutations work as follows [CEI96]. We first ini- tialize a system of polynomialsg 1(X) = 0, . . . gm(X) = 0in a set of variables...

work page

[48] [52]

Settingg(X) =g ′(X) +g ′′(X)for any polynomialsg ′(X), g ′′(X)already in the system

work page

[49] [53]

Settingg(X) =X i ·g ′(X)for any variableX i and any polynomialg ′(X)already in the system. The goal of a refutation is to derive the statement1 = 0via these operations; such a derivation is only possible if the original system was unsatisfiable, because the derivation rules cannot derive an unsatisfiable system from a satisfiable one. As in the lower boun...

work page

[50] [54]

, ϕn : Σ→F log2 |Σ| 2 for each variableX j

The adversary non-deterministically finds the best (bijective) embeddingsϕ 1, . . . , ϕn : Σ→F log2 |Σ| 2 for each variableX j. LetX ′ be a matrix ofnlog 2 |Σ|variables overF 2 such thatX ′ j,1, . . . ,X′ j,log2 |Σ| representsX j. 18A smarter algorithm could conceivably exploit nontrivial cancellations that occur without needing to fully distribute the po...

work page

[51] [55]

,X′ NH(i,1),log2 |Σ|,X ′ NH(i,2),1,

The adversary initializes a polynomial system overX ′ by appending, for eachi∈[m], the constraint f ′ i(X′) = 0, wheref ′ i is the unique polynomial overF 2 such that (a)f ′ i is supported on the variable setX′ NH(i,1),1, . . . ,X′ NH(i,1),log2 |Σ|,X ′ NH(i,2),1, . . . ,X′ NH(i,k),log2 |Σ|. (b) For all(σ 1, . . . , σk)∈Σ k such thatf i(σ1, . . . , σk) =b ...

work page

[52] [56]

converted

The adversary (non-deterministically) appends a new polynomialg(X ′) = 0to the system, by either (a) Settingg(X ′) =g ′(X′) +g ′′(X′)for any polynomialsg ′(X′), g′′(X′)already in the system. (b) Settingg(X ′) =X ′ j,ℓ ·g ′(X′)for any variableX ′ j,ℓ and any polynomialg ′(X′)already in the system. The goal of the adversary is derive the equation1 = 0, and ...

work page

[53] [57]

Every polynomial depends on at mostk ′ variables

work page

[54] [58]

For all subsetsGof at least 1 polynomial and at mosttpolynomials,Gdepends on at least(1−o(1))tk ′ distinct variables

work page

[55] [59]

Then any polynomial calculus refutation of the systemg 1(X) = 0,

Every polynomial has rational degreeΩ(k ′). Then any polynomial calculus refutation of the systemg 1(X) = 0, . . . , gm(X) = 0has at least one mono- mial of degreeΩ(tk ′). 43 Remark 6.16.The conditions we impose on the polynomial system in this lemma are equivalent to those in Theorem 3.8 from [AR01], but phrased slightly differently. As stated by Alekhno...

work page

[56] [60]

, σk)∈Σ k such thatf i(σ1,

For all(σ 1, . . . , σk)∈Σ k such thatf i(σ1, . . . , σk) =b i, we have f ′ i(ϕNH(i,1)(σ1), . . . , ϕNH(i,k)(σk)) = 0

work page

[57] [61]

Proof.First we give a sharp tail bound on the probability that, for a single choice of indexi, valueb i, embeddingsϕ 1,

For all other inputs,f ′ i equals1. Proof.First we give a sharp tail bound on the probability that, for a single choice of indexi, valueb i, embeddingsϕ 1, . . . , ϕk, and low degree polynomialsp, q, a random functionf i will satisfypf i =q. Then we union bound over all choices ofi,b i, ϕ1, . . . , ϕk, p, qto complete the proof. Claim 6.19.Fix an indexi∈[...

work page arXiv 2010

[58] [62]

The quasi- polynomial low-degree conjecture is false.arXiv preprint arXiv:2505.17360, 2025

5 [BBK+21] Afonso S Bandeira, Jess Banks, Dmitriy Kunisky, Christopher Moore, and Alex Wein. Spectral planting and the hardness of refuting cuts, colorability, and communities in random graphs. In Conference on Learning Theory, pages 410–473. PMLR, 2021. 5 [BCG+12] Aditya Bhaskara, Moses Charikar, Venkatesan Guruswami, Aravindan Vijayaraghavan, and Yuan Z...

work page arXiv 2021

[59] [63]

Cornell University,

5 [Hop18] Samuel Hopkins.Statistical inference and the sum of squares method. Cornell University,

work page

[60] [64]

One-way secret-key agreement and applications to circuit polarization and immunization of public-key encryption

3, 37, 38 [HR05] Thomas Holenstein and Renato Renner. One-way secret-key agreement and applications to circuit polarization and immunization of public-key encryption. InAnnual International Cryp- tology Conference, pages 478–493. Springer, 2005. 8, 12, 13 [IPS99] Russell Impagliazzo, Pavel Pudl ´ak, and Jiri Sgall. Lower bounds for the polynomial calculus...

work page 2005

[61] [65]

Schloss Dagstuhl, 2017

5, 37, 38 [KZ17] Andrei Krokhin and Stanislav Zivny.The constraint satisfaction problem: Complexity and approximability. Schloss Dagstuhl, 2017. 1 [LG24] Yuetian Luo and Chao Gao. Computational lower bounds for graphon estimation via low- degree polynomials.The Annals of Statistics, 52(5):2318–2348, 2024. 5 [Lyu05] Vadim Lyubashevsky. The parity problem i...

work page arXiv 2017

[62] [66]

Finding correlations in subquadratic time, with applications to learning pari- ties and juntas

2 [Val12] Gregory Valiant. Finding correlations in subquadratic time, with applications to learning pari- ties and juntas. In2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 11–20. IEEE, 2012. 6 [WEAM19] Alexander Wein, Ahmed El Alaoui, and Cristopher Moore. The kikuchi hierarchy and tensor pca.Journal of the ACM, 2019. 1, 7 51 [W...

work page 2012