{"id":"e18a836c-4acd-44ac-9cfd-fe85eee163fe","arxiv_id":"2504.15087","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For every epsilon and sufficiently large degree d, explicit d-regular graphs exist in which every small set S has at least (1-epsilon)d|S| distinct neighbors.","lead":"This paper gives the first explicit construction of constant-degree graphs in which every small set of vertices has almost all its edges going to distinct outside vertices. The construction uses Ramanujan cubical complexes and a small random-like gadget, and it also yields new quantum LDPC code families with linear-time decoding.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the core construction and proof are coherent.","rationale":"The reader's weakest_assumption pointed at the 2k-expanding property of the decorated Cayley cubical complex and the set-commutation of the LPS generators. I examined exactly that chain. Lemma 4.8 is the substantive step: it asserts A(p1)...A(pk)=A(p1...pk) with the odd-trace normalization. The proof is terse, but the odd-trace condition is precisely what prevents unit-migration collisions, and the type/XOR argument shows every factorization of an odd-trace product can be adjusted so all factors have odd trace. Thus the cubical generating set conditions hold. The eigenvalue bound in Lemma 4.9 has a typo (2k should be 2^k), but because k is fixed as a function of epsilon and D is then taken large, the extra constant is absorbed by O_k(1) throughout Lemmas 3.15 and 3.16. The small-set subcube density proof is sound: the expander mixing lemma application, the entropy/Shearer bound, and the extension counting via Lemma 3.3 all check out. The middle-to-right collision argument correctly uses skeleton expansion and the gadget spread condition; the only implicit step is choosing the final small-set constant eta small enough (e.g., eta = D^{-3}) so that the relevant subsets satisfy |U| <= D^{-1}|M|. This is not written explicitly, but it is consistent with the parameter windows and does not affect the asymptotic claim. The 'for every n' algorithmic phrasing is stronger than what is proved about primes in arithmetic progressions, but the central theorem only needs an explicit infinite family, so this is not load-bearing. I therefore find no reason to change the reader's ACCEPT verdict.","tokens_in":939,"tokens_out":940,"duration_ms":583268,"concrete_test":"Re-run the verification of Lemma 4.8 and the eigenvalue bound for a small explicit instance: take k=4, primes p1=5, p2=13, p3=17, p4=29, choose a prime q congruent to 1 mod 4*p1*p2*p3*p4 with q > 2*sqrt(p1*p2*p3*p4), and use a computer algebra system to compute the product set A(p1)...A(p4) modulo +/- in the quaternion image; check that its size equals prod(p_i+1) and that the nontrivial eigenvalues of the bipartite graph I_{0,1111} are at most 2^4 * sqrt(d). This directly tests the key black box on which Theorem 3.5 relies.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No significant objection identified. The main theorem rests on the structured base graph from Ramanujan Cayley cubical complexes (Theorem 3.5 and Lemma 4.8) and the gadget lemma of HLMOZ25. I checked the dependence chain and found no circularity or hidden assumption that would break the argument. The one clear typo is in Lemma 4.9, where the second-eigenvalue product should be 2^k times sqrt(d), not 2k times sqrt(d); since k is fixed before D is chosen, this only changes constants inside O_k(1) and does not affect the asymptotic claims. The algorithm's 'for every n' wording may be slightly stronger than what the prime-finding argument explicitly proves, but the existence of an explicit infinite family for each sufficiently large degree is unaffected. All small-set bounds, the entropy argument in Lemma 3.15, and the collision-graph analysis in Claim 2.13 are internally consistent.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper gives the first explicit construction of constant-degree lossless vertex expanders. For every epsilon > 0 and all sufficiently large d, it constructs a deterministic polynomial-time constructible infinite family of d-regular graphs in which every small set S has at least (1-epsilon)d|S| neighbors, hence at least (1-2epsilon)d|S| unique neighbors. The construction is the tripartite line product of a constant-sized random-like gadget graph with base graphs that are coded vertex-face incidence graphs of Ramanujan Cayley cubical complexes. A two-sided biregular version is proved for arbitrary constant imbalance, and the graphs carry a free group action of linear size, yielding new good quantum LDPC codes with linear-time decoding via the Lin-M. Hsieh framework. The paper develops self-contained proofs of the required cubical-complex expansion, the small-set subcube-density bound, and the collision analysis.","tokens_in":30680,"tokens_out":29564,"duration_ms":268177,"significance":"This is a major result: it resolves a long-standing open problem in explicit constructions and breaks the spectral barrier for vertex expansion in a strong and clean sense. The modular structure (constant-sized gadget plus expanding high-dimensional base) is likely to be influential, and the paper is careful with parameter dependencies. The base construction from LPS Ramanujan graphs is treated in detail, using only the Ramanujan property as a black box, and the application to quantum LDPC codes is explicit. The central claim is well supported by the high-level proof architecture, and the remaining issues appear fixable without changing the main ideas.","major_comments":[{"comment":"The proof of Lemma 2.8 does not, as written, support the claimed flexibility in DL and DR. The C-cubical incidence graph of X has middle degree P = product_i(p_i+1) (similarly P' for X'), and the text then says to pick an arbitrary DL-sized subcollection of signatures. If the subcollection is arbitrary, the intersections of the special sets Q_{a,b,i} with the kept signatures can be empty or of very different sizes, so Item (3) of Definition 2.5 (equal-size special sets partitioning [DL], uniformly over u in M_a) can fail. This uniform special-set structure is exactly what Claim 2.13 needs when it applies the spread condition of Lemma 2.9. The proof needs a balanced subcollection, for example a random subset of density DL/P whose existence follows by a Chernoff bound over the O_k(sqrt(D)) special-set families, or an analogous deterministic argument. As written, this is a gap in a load-bearing lemma.","section":"Section 3.1, Satisfying degree constraints"}],"minor_comments":[{"comment":"The proof of Lemma 4.9 gives the bound product_i(2 sqrt(p_i)) <= 2^k sqrt(d), so the displayed 2k sqrt(d) should be 2^k sqrt(d), and the phrase 2k-expanding in Definition 3.4 and Theorem 3.5 should be 2^k-expanding. Because k is fixed before D is chosen, the difference is absorbed in the O_k(1) constants and does not affect the asymptotic claims, but the stated constant is formally wrong.","section":"Section 4.2, Lemma 4.9; Definition 3.4; Theorem 3.5"},{"comment":"In the extension-counting argument, the text fixes an order of coordinates in S(U) and then says for each choice of (a_i in A_i)_{i not in S(U)} before forming a product over coordinates that appear to be in S(U); the notation should be corrected so the bijection between choices of outside-coordinate labels and extensions is clear.","section":"Section 3, proof of Lemma 3.3"},{"comment":"The definition of Delta(sigma) contains a typo: sigma_{j1}[i] != sigma_{j2}[k] should read sigma_{j1}[i] != sigma_{j2}[i].","section":"Section 3.2, Claim 3.14"},{"comment":"The algorithmic statement says the algorithm takes any positive integer n and outputs Z_n; as written this is stronger than the prime-construction argument, which directly gives infinitely many sizes. The authors should state the precise vertex-count guarantee, e.g. Theta(n) vertices for all sufficiently large n, and indicate how the prime-finding step supplies it.","section":"Theorem 2.2"},{"comment":"The degree bookkeeping in this remark should be clarified: Theorem 2.2 outputs a (k d_L, k d_R)-biregular graph, so the specialization d_L = d_R gives a kd-regular graph, and the perfect-matching reduction lowers this to d-regular; the phrase ed-bipartite graph is ambiguous.","section":"Remark 2.3"}],"recommendation":"major_revision","confidential_remarks":"The paper overlaps with recent works by some of the same authors, but the novel contribution is clearly stated and the overlap is not inappropriate. The main gap in Section 3.1 is fixable but should be addressed before publication; after that fix, the paper is very likely acceptable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague—\n\nThis is the real thing. Hsieh, Lubotzky, Mohanty, Reiner, and Zhang construct the first explicit constant-degree lossless vertex expanders, closing a gap listed as Open Problem 10.8 in the Hoory–Linial–Wigderson survey. They also get a two-sided biregular version for arbitrary constant imbalance and a free group action, which instantiates Lin and Hsieh's qLDPC framework. If the proof is right, and I believe it is, these are significant results.\n\nThe construction fits the tripartite line product from HMMP24, with base graphs built from coded incidence graphs of Ramanujan Cayley cubical complexes. The key technical novelty is the small-set subcube density bound: a small U in the middle layer has few k-faces meeting U in at least 2√k vertices. The proof uses expander mixing on the LPS Ramanujan graphs and a Shearer/entropy argument over the Hadamard code. This part is genuinely new and clean. The skeleton expansion of the incidence graphs—degree O(√D) and second eigenvalue O(D^{1/4})—is a real improvement over earlier unique-neighbor constructions.\n\nI checked the parameter choices in Section 2.2. They work: d_L and d_R are chosen large enough relative to D so τ, λ, and s satisfy all the inequalities; the split into high- and low-degree vertices is sound; Claim 2.13's collision bound uses the orientation lemma and the gadget spread condition correctly. The paper is honest about its black boxes: the Ramanujan theorem and the gadget existence lemma from HLMOZ25 are external, but none are circular or fitted to this construction.\n\nSoft spots are minor. Lemma 4.9 has a typo: the second-eigenvalue product should be 2^k√d, not 2k√d; this affects only constants inside O_k(1). The degree-constraint step in Section 3.1 (trimming faces by signature) is terse; it follows from Lemma 3.10, but a few more lines would help. The 'for every n' phrasing in Theorem 2.2 is slightly stronger than the prime-finding argument explicitly proves, but the existence of an explicit infinite family for each sufficiently large degree is solid.\n\nThis paper deserves a serious referee. I would send it to a top theory venue, and I expect it to be accepted with typographical fixes. You can cite it once it is in final form. Bring it to the next reading group for the subcube-density argument alone.","headline":"First explicit constant-degree lossless vertex expanders; the proof is coherent and the paper resolves a genuine open problem.","tokens_in":31242,"tokens_out":3160,"would_cite":true,"duration_ms":27561,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C48","05C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper constructs the first explicit constant-degree lossless vertex expanders: for any $\\varepsilon>0$ and large enough degree $d$, an infinite family of $d$-regular graphs in which every small set $S$ has at least…","keywords":["lossless vertex expanders","explicit construction","cubical complexes","Ramanujan graphs","small-set expansion","quantum LDPC codes","Hadamard code","tripartite line product"],"falsifier":"For an explicit choice of primes $p_1,\\ldots,p_k$ and $q$ as in Theorem 3.5, compute the second eigenvalue of the bipartite graph $I_{y,y\\oplus x}$ for each nonzero $x$; if any exceeds $2k\\sqrt{d_x(X)}$, the $2k$-expanding property fails. Alternatively, search over small subsets $U\\subseteq\\Gamma\\times\\mathcal{H}_k$ and count the $k$-faces meeting $U$ in at least $2\\sqrt{k}$ vertices; exceeding $O(D^{5/8})|U|$ would falsify Lemma 3.12.","tokens_in":30355,"feed_emoji":"🔗","tokens_out":13780,"duration_ms":113364,"temperature":0.7,"pith_summary":"The paper claims to resolve the long-standing search for explicit lossless vertex expanders: for every $\\varepsilon>0$ and every sufficiently large degree $d$, it gives a deterministic construction of an infinite family of $d$-regular graphs in which every small set $S$ has at least $(1-\\varepsilon)d|S|$ distinct neighbors. Random graphs were known to have this property, but no explicit family had been found. The construction is a tripartite line product of a constant-sized gadget graph with base graphs built from Ramanujan Cayley cubical complexes, and the proof of expansion rests on a new small-set subcube density bound for those complexes. The graphs also admit a free group action of linear size, which the paper uses to derive new families of good quantum LDPC codes with linear-time decoding.","feed_headline":"Explicit lossless vertex expanders now exist","feed_subtitle":"Constant-degree graphs where every small set keeps nearly all neighbors, enabling new quantum codes.","key_machinery":"The load-bearing object is the decorated Cayley cubical complex $X=\\operatorname{Cay}(\\Gamma;A_1,\\ldots,A_k)$, with vertex set $\\Gamma\\times\\mathbb{F}_2^k$ and $k$-faces that are hypercubes whose coordinate-step labels lie in prescribed generating sets $A_i$. The construction needs $X$ to be $2k$-expanding: for every pair of vertex types $y,y\\oplus x$, the bipartite graph between $\\Gamma\\times\\{y\\}$ and $\\Gamma\\times\\{y\\oplus x\\}$ has second eigenvalue at most $2k\\sqrt{d_x(X)}$, where $d_x(X)=\\prod_i |A_i|^{x_i}$. Theorem 3.5 obtains such complexes from the Ramanujan Cayley graphs of [LPS88]. The base graphs $G_L,G_R$ are coded incidence graphs between the $k$-faces and vertices restricted to the Hadamard code $\\mathcal{H}_k\\subseteq\\mathbb{F}_2^k$; this code structure makes the common neighborhoods of middle vertices uniformly about $\\sqrt{D}$ in size, giving skeleton expansion $O(D^{1/4})$. The proof of expansion is carried by the small-set subcube density bound in Lemma 3.12: any small $U\\subseteq\\Gamma\\times\\mathcal{H}_k$ has at most $O(D^{5/8})|U|$ $k$-faces meeting it in at least $2\\sqrt{k}$ vertices, proved with an entropy inequality. The final graph is the tripartite line product of these base graphs with a constant-sized gadget graph placed identically at every middle vertex.","core_discovery":"The paper's central claim is Theorem 1: for every $\\varepsilon>0$ there exists a sufficiently large integer $d_0$ such that for every integer $d\\ge d_0$, there is an explicit, deterministic polynomial-time constructible infinite family of $d$-regular graphs that are $(1-\\varepsilon)$-vertex expanders. This means every small set $S$ has at least $(1-\\varepsilon)d|S|$ distinct neighbors, which implies $(1-2\\varepsilon)d|S|$ unique neighbors. Theorem 2.2 strengthens the result to two-sided lossless expanders: for any constant imbalance $\\beta\\in(0,1]$, there are infinite families of $(kd_L,kd_R)$-biregular bipartite graphs in which small sets on both sides expand by a $(1-\\varepsilon)$ factor. The graphs are produced by taking a constant-sized gadget graph and forming a tripartite line product with coded incidence graphs of Ramanujan Cayley cubical complexes. The paper further proves the resulting graphs carry a free group action of size linear in the number of vertices, which resolves the conjecture from [LH22b] and yields new good quantum LDPC codes with linear-time decoding.","pith_inferences":["The proof does not really depend on the Hadamard code specifically; the authors note that any sufficiently balanced linear code would work, so replacing the code is a natural way to trade rate against the degree-versus-$\\varepsilon$ constants.","The same local-to-global lifting through expanding cubical complexes plausibly applies to edge expansion; the paper names ultra-lossless edge expanders as a related open direction, and the coded-incidence structure here looks like a promising ingredient for that problem.","A reader could test the robustness of the method by checking whether simpler Ramanujan Cayley graph families satisfy the cubical-generating-set property; if they do, the rest of the analysis would transfer unchanged."],"forward_implications":["The construction settles the long-open question of whether explicit constant-degree lossless vertex expanders exist.","The same machinery yields two-sided lossless expanders with any constant imbalance between the left and right degrees.","Because the graphs admit a free group action of linear size, they instantiate the hypothesis of [LH22b] and therefore give new good quantum LDPC codes with linear-time decoding.","The $(1-\\varepsilon)$-vertex expansion implies $(1-2\\varepsilon)$-unique-neighbor expansion, so the graphs meet the requirement for expander-code constructions that motivated the problem.","The construction is uniform and runs in polynomial time: for each sufficiently large degree $d$, a single algorithm outputs the $n$-vertex graph for every $n$."],"supporting_citations":[{"why":"Supplies the Ramanujan Cayley graphs whose generators become cubical generating sets and give the eigenvalue bound.","marker":"[LPS88]"},{"why":"Essentially contains the construction of expanding cubical complexes that Theorem 3.5 makes explicit and self-contained.","marker":"[RSV19]"},{"why":"Introduces the tripartite line product and the two-part left-to-middle and middle-to-right analysis used in the proof.","marker":"[HMMP24]"},{"why":"Provides the constant-sized gadget graph lemma, the small-set skeleton expansion notion, and the collision-graph argument.","marker":"[HLMOZ25]"},{"why":"Conjectures that two-sided lossless expanders with a free group action yield good quantum LDPC codes with linear-time decoding, which the paper resolves.","marker":"[LH22b]"},{"why":"Supplies the isoperimetric/entropy inequality used to prove the small-set subcube density bound.","marker":"[LW49]"}],"fun_headline_variants":["First explicit lossless vertex expanders","Explicit lossless expanders enable new quantum codes","Lossless expansion: explicit construction","New explicit constant-degree lossless expanders"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole proof leans on one algebraic fact: the specially chosen generator sets commute with each other as sets and give the stated eigenvalue bound for the associated bipartite graphs; if that fact failed, the expansion guarantee would not follow.","fun_headline_variants_meta":{"raw":{"variants":["First explicit lossless vertex expanders","Explicit lossless expanders enable new quantum codes","Lossless expansion: explicit construction","New explicit constant-degree lossless expanders"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000821,"raw_usage":{"total_tokens":3587,"prompt_tokens":930,"completion_tokens":2657,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":546,"completion_tokens_details":{"reasoning_tokens":2603}},"tokens_in":546,"tokens_out":2657,"duration_ms":19500,"temperature":1.0,"reasoning_tokens":2603,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:34:38.680364+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For an explicit choice of primes $p_1,\\ldots,p_k$ and $q$ as in Theorem 3.5, compute the second eigenvalue of the bipartite graph $I_{y,y\\oplus x}$ for each nonzero $x$; if any exceeds $2k\\sqrt{d_x(X)}$, the $2k$-expanding property fails. Alternatively, search over small subsets $U\\subseteq\\Gamma\\times\\mathcal{H}_k$ and count the $k$-faces meeting $U$ in at least $2\\sqrt{k}$ vertices; exceeding $O(D^{5/8})|U|$ would falsify Lemma 3.12.","supporting_citations":[],"review_version":1}