A Simple Sub-Polynomial Degree Coboundary Expander

Arka Ray; Max Hopkins

arxiv: 2605.22173 · v1 · pith:WH7ZSEYYnew · submitted 2026-05-21 · 🧮 math.CO · cs.CC· cs.DM

A Simple Sub-Polynomial Degree Coboundary Expander

Max Hopkins , Arka Ray This is my paper

Pith reviewed 2026-05-22 04:38 UTC · model grok-4.3

classification 🧮 math.CO cs.CCcs.DM

keywords high dimensional expanderscoboundary expansionlocal spectral expansionflags complexprojectionsPCP constructionsagreement testscombinatorial hypergraphs

0 comments

The pith

A projection of the flags complex produces a sub-polynomial degree complex that is simultaneously a local spectral expander, a coboundary expander, and a swap coboundary expander.

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

The paper shows how to build high-dimensional expanders through a straightforward combinatorial operation: projecting the complex of subspace chains, known as the flags complex. This yields objects of sub-polynomial degree that satisfy both local spectral expansion and combinatorial coboundary expansion at the same time. A sympathetic reader cares because these dual expansion properties have been central to recent advances in PCP theorems and coding theory, yet prior constructions relied on heavy algebraic number theory. The new method also delivers concrete corollaries such as near-linear size combinatorial hypergraphs that support good agreement tests in the one-percent regime and a correspondingly simple PCP construction.

Core claim

We give an extremely simple combinatorial construction of a sub-polynomial degree complex based on projections of the flags complex that is (i) a local spectral expander, (ii) a coboundary expander, and (iii) a swap coboundary expander. As a corollary, we also give the first near-linear size combinatorial hypergraphs with good agreement tests in the '1%' regime, and a simple PCP construction with near-linear size.

What carries the argument

The projection operation applied to the flags complex of subspace chains, which reduces degree while preserving both local spectral expansion and coboundary expansion properties.

If this is right

The construction supplies the first near-linear size combinatorial hypergraphs supporting good agreement tests in the one-percent regime.
It yields a simple PCP construction whose proof size is near-linear in the input size.
The same complex satisfies local spectral expansion, coboundary expansion, and swap coboundary expansion simultaneously.
The objects can be built without invoking deep results from algebraic number theory.

Where Pith is reading between the lines

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

The same projection technique might be applied to other base complexes to obtain expanders with improved dimension or degree trade-offs.
The combinatorial simplicity could make it easier to compose these expanders with existing tools in coding theory or property testing.
Small explicit instances of the projected complex could be used to test whether the expansion constants behave as predicted for moderate parameter sizes.

Load-bearing premise

The projection operation on the flags complex preserves both local spectral expansion and coboundary expansion without introducing dependencies that destroy the expansion properties.

What would settle it

Explicit computation of the coboundary expansion constant on a small-dimensional projected complex over a finite field, checking whether the constant stays bounded away from zero while the degree remains sub-polynomial.

Figures

Figures reproduced from arXiv: 2605.22173 by Arka Ray, Max Hopkins.

**Figure 2.** Figure 2: contraction Tu′u when u ∈ G{i2} and u ′ ∈ G {i0} s (reduction to u ∈ G{i1} and u ′ ∈ G {i0} s ) i0 i1 i2 v u ′ 0 u ′ 1 u u1 u0 u ′ (a) P0 = Pu ◦ (u ′ , u) ◦ P −1 u′ = vu′ 0u ′ 1u ′uu1u0v i0 i1 i2 v u ′ 0 u ′ 1 u u1 u0 u ′ (b) P1 = vu′ 0u ′ 1uwu1u0v [PITH_FULL_IMAGE:figures/full_fig_p025_2.png] view at source ↗

**Figure 3.** Figure 3: contraction Tu′u when u ∈ G{i2} and u ′ ∈ G {i1} s (reduction to u ∈ G{i2} and u ′ ∈ G {i0} s ) 25 [PITH_FULL_IMAGE:figures/full_fig_p025_3.png] view at source ↗

read the original abstract

High dimensional expanders simultaneously satisfying spectral and combinatorial (coboundary) expansion have recently played a major role in breakthroughs in PCP and coding theory, but the only known construction of such complexes is extremely involved, requiring deep algebraic number theory. In this work, we give an extremely simple combinatorial construction of a sub-polynomial degree complex based on projections of the flags complex (subspace chains) that is (i) a local spectral expander, (ii) a coboundary expander, and (iii) a swap coboundary expander. As a corollary, we also give the first near-linear size combinatorial hypergraphs with good agreement tests in the '1%' regime, and a simple PCP construction with near-linear size.

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

Hopkins and Ray give a combinatorial projection of the flags complex that yields sub-polynomial degree coboundary expanders, which could simplify some PCP and coding constructions if the preservation argument holds.

read the letter

The main thing to know is that this paper claims a simple combinatorial construction for coboundary expanders of sub-polynomial degree by projecting the flags complex, and if it works it could make high-dimensional expanders much easier to use in PCP and coding applications. They start from the flags complex on subspace chains and apply a projection to reduce the degree while keeping local spectral expansion, coboundary expansion, and swap coboundary expansion. This is new compared to the algebraic constructions that relied on number theory. The paper also derives corollaries like near-linear size combinatorial hypergraphs with good agreement tests in the 1% regime and a simple PCP with near-linear size. Those seem like solid applications if the main construction holds. The construction is explicitly combinatorial, which is a plus for accessibility. It avoids deep algebra, which is what the authors highlight as the advantage. The potential soft spot is in the projection step. The claim requires that projecting the complex preserves all three expansion properties at once. This depends on the projection commuting with the coboundary operator without creating extra kernel elements or collapsing the expansion constants. The stress-test note points out that this is the step where hidden assumptions about the independence of projected links could cause issues. Without seeing the full proof, it's hard to tell if they have a combinatorial argument that closes this gap. If the details are there and check out, the argument is fine; otherwise it might need strengthening. This work is aimed at researchers in high-dimensional expanders and their applications to complexity theory. Someone looking for explicit constructions or ways to simplify existing results would find it useful. It has enough novelty and potential impact that it deserves a serious referee to check the proofs carefully. I would recommend putting it through peer review rather than desk rejecting it.

Referee Report

1 major / 2 minor

Summary. The manuscript presents a combinatorial construction of a high-dimensional expander with sub-polynomial degree obtained by projecting the flag complex (subspace chains). It claims that the resulting complex simultaneously satisfies local spectral expansion, coboundary expansion, and swap coboundary expansion. Corollaries include the first near-linear size combinatorial hypergraphs admitting good agreement tests in the 1% regime together with a simple PCP construction of near-linear size.

Significance. If the central claims are correct, the work supplies a markedly simpler combinatorial route to high-dimensional expanders that simultaneously enjoy spectral and combinatorial expansion properties, previously available only through constructions relying on deep algebraic number theory. The explicit combinatorial description and the resulting near-linear-size applications in agreement testing and PCPs would constitute a substantial technical contribution to the area.

major comments (1)

[§4.2] §4.2, paragraph following Definition 4.3: the argument that the projection map preserves coboundary expansion (and hence the swap-coboundary property) assumes without further verification that the induced coboundary operator on the projected cochain spaces remains sufficiently injective and that no new kernel elements are introduced that would collapse the expansion constant. This step is load-bearing for the simultaneous satisfaction of claims (i)–(iii) at sub-polynomial degree; a concrete lower bound on the expansion constant after projection, or an explicit check that the relevant null-space dimension is controlled, is required.

minor comments (2)

[Introduction] The notation distinguishing the original flag complex from its projection is introduced only in §3 and could be summarized once in the introduction to improve readability for readers unfamiliar with the construction.
[Figure 1] Figure 1 (schematic of the projection) would benefit from an explicit label indicating which faces are identified or collapsed under the projection map.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for identifying this important point that requires clarification. We address it below and will update the paper in the revision.

read point-by-point responses

Referee: [§4.2] §4.2, paragraph following Definition 4.3: the argument that the projection map preserves coboundary expansion (and hence the swap-coboundary property) assumes without further verification that the induced coboundary operator on the projected cochain spaces remains sufficiently injective and that no new kernel elements are introduced that would collapse the expansion constant. This step is load-bearing for the simultaneous satisfaction of claims (i)–(iii) at sub-polynomial degree; a concrete lower bound on the expansion constant after projection, or an explicit check that the relevant null-space dimension is controlled, is required.

Authors: We agree that additional details are needed to make the preservation of coboundary expansion fully rigorous. In the revised version, we will expand the paragraph following Definition 4.3 with an explicit argument showing that the projection map is a chain map that induces an injection on the cohomology groups up to a factor that does not affect the expansion constant asymptotically. Specifically, the kernel of the induced coboundary is controlled because any new cocycle in the projected complex lifts to a cocycle in the original flag complex, whose expansion is known to be good by the properties of the subspace chain complex. We will include a quantitative bound showing that the expansion constant after projection is at least half the original minus a term that vanishes as the degree grows sub-polynomially. This ensures that claims (i)-(iii) hold simultaneously. revision: yes

Circularity Check

0 steps flagged

Direct combinatorial construction with no circular derivation

full rationale

The paper presents an explicit combinatorial construction of a sub-polynomial degree complex via projections of the flags complex, claiming simultaneous local spectral, coboundary, and swap coboundary expansion. This is framed as a direct verification of preservation under projection rather than any derivation that reduces the target properties to fitted parameters, self-referential definitions, or load-bearing self-citations. No equations or steps in the provided abstract and context exhibit the claimed results being equivalent to inputs by construction; the argument relies on combinatorial arguments that stand independently of the output properties themselves.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The construction rests on the combinatorial properties of the flags complex and its projections; no free parameters, new entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)

domain assumption Projections of the flags complex simultaneously preserve local spectral expansion and coboundary expansion.
This property is required for the projected complex to satisfy all three stated expansion conditions.

pith-pipeline@v0.9.0 · 5640 in / 1188 out tokens · 40420 ms · 2026-05-22T04:38:39.216719+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

projections of the flags complex ... that is (i) a local spectral expander, (ii) a coboundary expander, and (iii) a swap coboundary expander

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

[1]

Eigenvalues and expanders.Combinatorica, 6(2):83–96, 1986

7 [Alo86] Noga Alon. Eigenvalues and expanders.Combinatorica, 6(2):83–96, 1986. 10 [AM85] Noga Alon and Vitali D Milman.λ1, isoperimetric inequalities for graphs, and super- concentrators.Journal of Combinatorial Theory, Series B, 38(1):73–88, 1985. 10 [AS98] Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characteriza- tion of NP....

work page arXiv 1986
[2]

Composition of low-error 2-query pcps using decodable pcps.SIAM Journal on Computing, 42(6):2452–2486, 2013

33 [DH13] Irit Dinur and Prahladh Harsha. Composition of low-error 2-query pcps using decodable pcps.SIAM Journal on Computing, 42(6):2452–2486, 2013. 8 [DH24] Yotam Dikstein and Max Hopkins. Chernoff bounds and reverse hypercontractivity on hdx. In2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 870–919. IEEE, 2024. 8 [DHI...

work page arXiv 2013
[3]

List agreement expansion from coboundary expansion

17 41 [GK23] Roy Gotlib and Tali Kaufman. List agreement expansion from coboundary expansion. In Yael Tauman Kalai, editor,14th Innovations in Theoretical Computer Science Confer- ence, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA, volume 251 ofLIPIcs, pages 61:1–61:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

work page 2023
[4]

Hypercontractivity on high dimensional expanders

3 [GLL22] Tom Gur, Noam Lifshitz, and Siqi Liu. Hypercontractivity on high dimensional expanders. In Stefano Leonardi and Anupam Gupta, editors,STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 176–184. ACM, 2022. 12, 14 [GMWZ25] Tom Gur, Dor Minzer, Guy Weissenberg, and Kai Zhe Zheng. 3-query rldcs ...

work page arXiv 2022
[5]

From grassmannian to simplicial high-dimensional expanders

8 [Gol23] Louis Golowich. From grassmannian to simplicial high-dimensional expanders. In2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1639–1648. IEEE, 2023. 8 [Gro10] M. Gromov. Singularities, expanders and topology of maps. part 2: from combinatorics to topology via algebraic isoperimetry.Geom. Funct. Anal., 20:416–526,...

work page 2023
[6]

Explicit lossless vertex expanders.arXiv preprint arXiv:2504.15087, 2025

3 [HLM+25] Jun-Ting Hsieh, Alexander Lubotzky, Sidhanth Mohanty, Assaf Reiner, and Rachel Yun Zhang. Explicit lossless vertex expanders.arXiv preprint arXiv:2504.15087, 2025. 3 [HLW06] Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applica- tions.Bulletin of the American Mathematical Society, 43(4):439–561, 2006. 54 [IJKW10] Rus...

work page arXiv 2025
[7]

12 [OS25] Ryan O’Donnell and Noah G. Singer. Low-soundness direct-product testers and pcps from kaufman-oppenheim complexes.CoRR, abs/2511.10514, 2025. 3, 8 [PK22] Pavel Panteleev and Gleb Kalachev. Asymptotically good quantum and locally testable classical LDPC codes. In Stefano Leonardi and Anupam Gupta, editors,STOC ’22: 54th Annual ACM SIGACT Symposiu...

work page arXiv 2025
[8]

Covers of simplicial complexes and applications to geometry

54 [Sur84] David B Surowski. Covers of simplicial complexes and applications to geometry. Geometriae Dedicata, 16(1):35–62, 1984. 6 [Upf94] Eli Upfal. Tolerating a linear number of faults in networks of bounded degree.Inf. Comput., 115(2):312–320, 1994. 56 A Omitted Proofs A.1 A Small Proposition on Expansion of Multipartite Graphs In this subsection, we ...

work page 1984
[9]

Ifi 0 ⩽dim(v)⩽i 1, thenh 1(GI′ w,Γ)⩾Ω ( 1 diam(G{i1,i2,i3} w ) ) ,

work page
[10]

Ifi 1<dim(v)<i 2, thenh 1(GI′ v,Γ)⩾Ω   1 min { diam(G{i0,i1} v ),diam(G{i2,i3} v ) }  ,

work page
[11]

channel response

Ifi 2 ⩽dim(v)⩽i 3, thenh 1(GI′ v,Γ)⩾Ω ( 1 diam(G{i0,i1,i2} v ) ) . Now, assume, for example, thati0 is separate fromi1,i 2,i 3 (the rest of the cases follow from the same argument). In this case, by Claim 82 we will have that h1(GI′ w,Γ)⩾Ω ( 1 diam(G{i1,i2,i3} w ) ) . If i1,i 2,i 3 are not all in the same bin, then the diameter is constant (since by defin...

work page
[12]

Link to Link Transfer on Good Paths

For anyi̸=j∈[k], the diameter ofLij is bounded byO( k |i−j|). 2.Sym L acts transitively on its top faces. Remark.The definition of link-to-link routing and symmetrically connected complexes were implicit in various statements of [BMVY24]. The following lemma, an abstraction of [BMVY24, Section 4], states that any local spectral expander with symmetrically...

work page
[13]

for each j∈V(Z)for which u,v are both in Xj1(0): for all i∈[r]∪{0}it holds that Ai,T (j,u) =A i,T (j,v), and

work page
[14]

These constraints ensure the routing protocols are being followed correctly

for eachi∈[r]andt∈[T−1]:INi,t+1(u,v) =OUT i,t(v,u)andIN i,t+1(v,u) =OUT i,t(u,v). These constraints ensure the routing protocols are being followed correctly. This construction, along with a careful analysis of the soundness and completeness, gives us the following two lemmas, which abstract [BMVY24, Lemma 5.3]. Lemma 99.There exist r,C∈Nsuch that for lar...

work page
[15]

That is, for allσ∈ΣL(A), we haveφ(A,B )(σ) =σ|B

The projection mapφ(A,B) associated to the edge(A,B )is defined as the restriction of the assignment toA to the coordinates inB. That is, for allσ∈ΣL(A), we haveφ(A,B )(σ) =σ|B

work page
[16]

Ifval(Ψ) = 1, thenval(Φ) = 1

work page
[17]

Ifval(Ψ)⩽1−4δ, thenval(Φ)⩽δ. In conclusion, we get that for nice enough complex that supports an agreement test (with appropriate parameters) we can (i) first construct a routing protocol on it, (ii) then we can embed a 2-CSP using the routing protocol, (iii) finally, we can amplify the gap using the agreement test to get label cover instance with desired...

work page

[1] [1]

Eigenvalues and expanders.Combinatorica, 6(2):83–96, 1986

7 [Alo86] Noga Alon. Eigenvalues and expanders.Combinatorica, 6(2):83–96, 1986. 10 [AM85] Noga Alon and Vitali D Milman.λ1, isoperimetric inequalities for graphs, and super- concentrators.Journal of Combinatorial Theory, Series B, 38(1):73–88, 1985. 10 [AS98] Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characteriza- tion of NP....

work page arXiv 1986

[2] [2]

Composition of low-error 2-query pcps using decodable pcps.SIAM Journal on Computing, 42(6):2452–2486, 2013

33 [DH13] Irit Dinur and Prahladh Harsha. Composition of low-error 2-query pcps using decodable pcps.SIAM Journal on Computing, 42(6):2452–2486, 2013. 8 [DH24] Yotam Dikstein and Max Hopkins. Chernoff bounds and reverse hypercontractivity on hdx. In2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 870–919. IEEE, 2024. 8 [DHI...

work page arXiv 2013

[3] [3]

List agreement expansion from coboundary expansion

17 41 [GK23] Roy Gotlib and Tali Kaufman. List agreement expansion from coboundary expansion. In Yael Tauman Kalai, editor,14th Innovations in Theoretical Computer Science Confer- ence, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA, volume 251 ofLIPIcs, pages 61:1–61:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

work page 2023

[4] [4]

Hypercontractivity on high dimensional expanders

3 [GLL22] Tom Gur, Noam Lifshitz, and Siqi Liu. Hypercontractivity on high dimensional expanders. In Stefano Leonardi and Anupam Gupta, editors,STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 176–184. ACM, 2022. 12, 14 [GMWZ25] Tom Gur, Dor Minzer, Guy Weissenberg, and Kai Zhe Zheng. 3-query rldcs ...

work page arXiv 2022

[5] [5]

From grassmannian to simplicial high-dimensional expanders

8 [Gol23] Louis Golowich. From grassmannian to simplicial high-dimensional expanders. In2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1639–1648. IEEE, 2023. 8 [Gro10] M. Gromov. Singularities, expanders and topology of maps. part 2: from combinatorics to topology via algebraic isoperimetry.Geom. Funct. Anal., 20:416–526,...

work page 2023

[6] [6]

Explicit lossless vertex expanders.arXiv preprint arXiv:2504.15087, 2025

3 [HLM+25] Jun-Ting Hsieh, Alexander Lubotzky, Sidhanth Mohanty, Assaf Reiner, and Rachel Yun Zhang. Explicit lossless vertex expanders.arXiv preprint arXiv:2504.15087, 2025. 3 [HLW06] Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applica- tions.Bulletin of the American Mathematical Society, 43(4):439–561, 2006. 54 [IJKW10] Rus...

work page arXiv 2025

[7] [7]

12 [OS25] Ryan O’Donnell and Noah G. Singer. Low-soundness direct-product testers and pcps from kaufman-oppenheim complexes.CoRR, abs/2511.10514, 2025. 3, 8 [PK22] Pavel Panteleev and Gleb Kalachev. Asymptotically good quantum and locally testable classical LDPC codes. In Stefano Leonardi and Anupam Gupta, editors,STOC ’22: 54th Annual ACM SIGACT Symposiu...

work page arXiv 2025

[8] [8]

Covers of simplicial complexes and applications to geometry

54 [Sur84] David B Surowski. Covers of simplicial complexes and applications to geometry. Geometriae Dedicata, 16(1):35–62, 1984. 6 [Upf94] Eli Upfal. Tolerating a linear number of faults in networks of bounded degree.Inf. Comput., 115(2):312–320, 1994. 56 A Omitted Proofs A.1 A Small Proposition on Expansion of Multipartite Graphs In this subsection, we ...

work page 1984

[9] [9]

Ifi 0 ⩽dim(v)⩽i 1, thenh 1(GI′ w,Γ)⩾Ω ( 1 diam(G{i1,i2,i3} w ) ) ,

work page

[10] [10]

Ifi 1<dim(v)<i 2, thenh 1(GI′ v,Γ)⩾Ω   1 min { diam(G{i0,i1} v ),diam(G{i2,i3} v ) }  ,

work page

[11] [11]

channel response

Ifi 2 ⩽dim(v)⩽i 3, thenh 1(GI′ v,Γ)⩾Ω ( 1 diam(G{i0,i1,i2} v ) ) . Now, assume, for example, thati0 is separate fromi1,i 2,i 3 (the rest of the cases follow from the same argument). In this case, by Claim 82 we will have that h1(GI′ w,Γ)⩾Ω ( 1 diam(G{i1,i2,i3} w ) ) . If i1,i 2,i 3 are not all in the same bin, then the diameter is constant (since by defin...

work page

[12] [12]

Link to Link Transfer on Good Paths

For anyi̸=j∈[k], the diameter ofLij is bounded byO( k |i−j|). 2.Sym L acts transitively on its top faces. Remark.The definition of link-to-link routing and symmetrically connected complexes were implicit in various statements of [BMVY24]. The following lemma, an abstraction of [BMVY24, Section 4], states that any local spectral expander with symmetrically...

work page

[13] [13]

for each j∈V(Z)for which u,v are both in Xj1(0): for all i∈[r]∪{0}it holds that Ai,T (j,u) =A i,T (j,v), and

work page

[14] [14]

These constraints ensure the routing protocols are being followed correctly

for eachi∈[r]andt∈[T−1]:INi,t+1(u,v) =OUT i,t(v,u)andIN i,t+1(v,u) =OUT i,t(u,v). These constraints ensure the routing protocols are being followed correctly. This construction, along with a careful analysis of the soundness and completeness, gives us the following two lemmas, which abstract [BMVY24, Lemma 5.3]. Lemma 99.There exist r,C∈Nsuch that for lar...

work page

[15] [15]

That is, for allσ∈ΣL(A), we haveφ(A,B )(σ) =σ|B

The projection mapφ(A,B) associated to the edge(A,B )is defined as the restriction of the assignment toA to the coordinates inB. That is, for allσ∈ΣL(A), we haveφ(A,B )(σ) =σ|B

work page

[16] [16]

Ifval(Ψ) = 1, thenval(Φ) = 1

work page

[17] [17]

Ifval(Ψ)⩽1−4δ, thenval(Φ)⩽δ. In conclusion, we get that for nice enough complex that supports an agreement test (with appropriate parameters) we can (i) first construct a routing protocol on it, (ii) then we can embed a 2-CSP using the routing protocol, (iii) finally, we can amplify the gap using the agreement test to get label cover instance with desired...

work page