2026-07-23T20:14:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27068 2026-07-23T11:36:19Z ddc:004 open_access

A Simple Sub-Polynomial Degree Coboundary Expander Hopkins, Max Ray, Arka high dimensional expansders agreement testing probabilistically checkable proofs 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Max Hopkins and Arka Ray 2026 Is Part Of LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2026.26 urn:nbn:de:0030-drops-270685 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.26 eng https://creativecommons.org/licenses/by/4.0/legalcode