The Polynomial Compatibility Conjecture for Low-Influence Degree-d Distributions
Statement: AI-written, not yet formalized. Proof: open – no attempt yet.
A purely combinatorial question about polynomials, which several quantum black-box separations are waiting on. Take two distributions over low-degree, unit-norm functions on \(\mathcal{Y}^N\) whose coordinates all have small influence on average. Must there be one function in the support of each, and one point, where both are non-zero? The two distributions come from the two branches of a purified quantum party, and a point where both are non-zero is what “these two outcomes are simultaneously realizable” means — two openings of a commitment, or two consistent executions. It is known for exponentially small influences and false for large ones; the conjecture is that it survives all the way down to inverse-polynomial, which is the regime the separations need.
View PDF · LaTeX source · Formal statement — not yet formalized
Let \(\mathcal{Y}\) be a finite abelian group. For \(f : \mathcal{Y}^N \to \mathbb{C}\), expand \(f\) in the character basis; \(\deg(f)\) is the largest number of non-trivial coordinates in a character with a non-zero coefficient, \(\lVert f \rVert_2\) is taken under the uniform distribution on \(\mathcal{Y}^N\), and \(\mathrm{Inf}_i(f)\) is the total squared weight on characters non-trivial at coordinate \(i\).
Conjecture. There exist a finite abelian group \(\mathcal{Y}\), constants \(c_1 \in (0,1]\) and \(c_2 > 0\), and a function \(\delta : \mathbb{N} \to (0,1]\) with \(\delta(d) \ge c_1 d^{-c_2}\) for all \(d \ge 1\) — equivalently \(\delta(d) \ge 1/p(d)\) for some polynomial \(p\) — such that for every \(d, N \in \mathbb{N}\) the following holds. Let \(\mathbf{F}\) and \(\mathbf{G}\) be any two distributions over functions \(\mathcal{Y}^N \to \mathbb{C}\) with
- \(\lVert f \rVert_2 = 1\) and \(\lVert g \rVert_2 = 1\) for every \(f \in \mathrm{supp}(\mathbf{F})\), \(g \in \mathrm{supp}(\mathbf{G})\);
- \(\deg(f) \le d\) and \(\deg(g) \le d\) throughout both supports;
- \(\mathbb{E}_{f \gets \mathbf{F}}[\mathrm{Inf}_i(f)] \le \delta(d)\) and \(\mathbb{E}_{g \gets \mathbf{G}}[\mathrm{Inf}_i(g)] \le \delta(d)\) for every \(i \in [N]\).
Then there exist \(f \in \mathrm{supp}(\mathbf{F})\), \(g \in \mathrm{supp}(\mathbf{G})\) and \(x \in \mathcal{Y}^N\) with \(f(x) \cdot g(x) \ne 0\).
Why the constant in \(\delta\) is load-bearing. Writing the bound as \(\delta(d) \ge d^{-c}\) instead would force \(\delta(1) = 1\), and the statement is then false: over \(\mathcal{Y} = \mathbb{Z}_2\) with \(N = 1\), the degree-one unit-norm functions \(f = (1+x)/\sqrt{2}\) and \(g = (1-x)/\sqrt{2}\) have \(\mathrm{Inf}_1 = 1/2\) and vanish at opposite points, so point masses on them refute it. The papers’ own \(1/\mathrm{poly}(d)\) — admitting, say, \(\delta(d) = 1/(100d)\) — is untouched by this, and is what is transcribed above.
Sources
- Austrin, Chung, Chung, Fu, Lin, and Mahmoody. On the Impossibility of Key Agreements from Quantum Random Oracles. Cryptology ePrint Archive, Report 2022/218; CRYPTO 2022, pp. 165–194. Where the conjecture is introduced; Theorem 4.4 (exponentially small influences), Theorem 5.6 (equivalence with the quantum-state formulation), Appendix B (the refuted regime).
- Chung, Lin, and Mahmoody. Black-Box Separations for Non-Interactive Commitments in a Quantum World. Cryptology ePrint Archive, Report 2023/570; EUROCRYPT 2023. Conjecture 2.8, the restatement transcribed above, and the separation built on it.
- Zhandry. How to record quantum queries, and applications to quantum indifferentiability. CRYPTO 2019, pp. 239–268. The compressed-oracle technique the whole reduction to polynomials rests on.
- Mahmoody and Pass. The curious case of non-interactive commitments — on the power of black-box vs. non-black-box use of primitives. CRYPTO 2012, pp. 701–718. The classical separation being lifted.
- Donoho and Stark. Uncertainty principles and signal recovery. SIAM Journal on Applied Mathematics 49(3):906–931, 1989. Used downstream in place of Schwartz–Zippel.
View PDF — no proof written yet · LaTeX source — no proof written yet · Formal proof — not yet formalized
Open in the regime that matters, and pinned from both sides.
Proved for exponentially small influences. Theorem 4.4 of the paper that introduced the conjecture establishes it whenever \(\delta < \lvert\mathcal{Y}\rvert^{-d}/d\). That paper also shows (its Theorem 5.6) that the polynomial formulation is equivalent to a quantum-state formulation, so nothing is lost by working combinatorially.
False for \(\delta \ge 1/(2d)\). Its Appendix B rules that regime out, and shows the degree and influence hypotheses are needed on both distributions rather than one.
What is left, and what it buys. Everything between \(\lvert\mathcal{Y}\rvert^{-d}/d\) and \(1/(2d)\). Any \(\delta\) that is \(1/\mathrm{poly}(d, \log\lvert\mathcal{Y}\rvert)\) already suffices for a polynomial-query attack, which is why the inverse-polynomial regime is the target. The later paper assumes the conjecture throughout — its Theorem 1.1, Section 4, Lemma 4.4 and Construction 4.5 are all conditional on it — to rule out quantum black-box constructions of non-interactive commitments from post-quantum one-way functions.
The asymmetry of the two directions. \(\mathcal{Y}\) is existentially quantified, so a proof for one finite abelian group — \(\mathbb{Z}_2\), say — settles the conjecture, while a refutation has to rule out every finite abelian group.
The conjecture is what remains after Zhandry’s compressed-oracle technique is applied to a black-box separation argument. Classically one records the oracle positions a party asked and fixes a partial oracle consistent with that record; a superposition query cannot be recorded, so the argument is re-run in the purified view with the oracle register in the Fourier basis. A \(d\)-query algorithm is then sparse in that basis, each branch of the purified party becomes a distribution over degree-\(d\), unit-norm, low-influence functions, and “both branches are simultaneously realizable” becomes exactly the non-vanishing condition above.
The source papers note a kinship with the Aaronson–Ambainis line on the need for structure in quantum speedups, and the downstream construction replaces Schwartz–Zippel with the Donoho–Stark support-size uncertainty principle to boost a single compatible oracle into a large set of them.
This page is the merge of two harvested drafts. polynomial-compatibility was taken from ePrint 2022/218 and polynomial-compatibility-2 from ePrint 2023/570; they state the same conjecture, since the second paper explicitly uses “the Polynomial Compatibility Conjecture of [ACC+22]”. The LaTeX published here is the second, both because its parameterization is the correct one (see the note under Statement) and because it takes the codomain to be \(\mathbb{C}\) rather than \(\mathbb{R}\), which is what the quantum application needs. The first draft stays in latex/conjectures/ and is not separately promoted.
Checked against the literature, 2026-08-19. Searched forward citations and progress on the related Aaronson–Ambainis conjecture; “Cryptomania v.s. Minicrypt in a Quantum World” (arXiv 2504.05710, 2025) states it removes the conjecture used in Austrin et al. and Chung–Lin–Mahmoody, i.e. it bypasses this conjecture with a different separation rather than resolving it, and Bhattacharya’s “Aaronson–Ambainis Conjecture Is True For Random Restrictions” (ITCS 2025, arXiv 2402.13952) proves a weaker restricted-domain version of the related-but-distinct Aaronson–Ambainis conjecture, neither of which resolves the Polynomial Compatibility Conjecture itself. Still open in the inverse-polynomial regime.
An attack was attempted, 27–28 August 2026, and did not move the conjecture. A multi-agent proof campaign ran against a ladder of special cases; its artifacts are in campaign/. One rung was proved and verified: over \(\mathbb{Z}_2\), two cross-disjoint families of normalized cylinder-pattern indicators with windows of at most \(d\) coordinates cannot both keep every coordinate’s average influence below \(1/(3d)\) — and the constant is tight, since the \(d \times d\) grid construction sits at exactly \(1/(2d)\). The proof replaces the union bound with an isoperimetric argument and cites nothing externally; it passed five independent blind referee passes across two model families, an adjudication that upheld no defect, and a final context-free check.
The next rung — the same statement for all degree-\(\le d\) subsets of the cube — remains open, and this is where the conjecture’s content begins. It is settled at \(d = 2\) with the optimal constant \(1/4\) (proved for every \(N\), so widening the class from the first rung does not move the frontier), and at \(d = 3\) the value \(1/6\) survived exhaustive search over the complete window-6 and window-7 pattern classes. Four technique classes were closed with explicit certificates: payments charged against relevance-counted windows, routes needing a single coordinate influential for both sides, the junta-substitution route, and a repaired payment hypothesis refuted at degree 120. The remaining difficulty is pinned to a specific density band, with explicit witnesses inside it.
No progress was made on the inverse-polynomial regime itself, and the proved threshold for the conjecture is unchanged. As with everything on this site, none of this has been read by a human referee.