pith. sign in

arxiv: 2606.23579 · v1 · pith:HHOULELYnew · submitted 2026-06-22 · 🧮 math.CO · cs.CR· cs.IT· math.IT

Optimal Small Set Expanders and Their Codes

Tristram Bogart , Marcelo Fiori , Pedro Raigorodsky , Mauricio Velasco This is my paper

Pith reviewed 2026-06-26 07:46 UTC · model grok-4.3

classification 🧮 math.CO cs.CRcs.ITmath.IT
keywords small-set expandersbipartite graphsgirthexpander graphstransfer boundscombinatorial characterizationpost-quantum cryptographyerror-correcting codes
0
0 comments X

The pith

Optimal small-set expanders in left-regular bipartite graphs are characterized by girth.

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

The paper studies left-regular bipartite graphs where every small set of left vertices has many neighbors. It defines optimality as achieving the largest possible number of neighbors for sets up to a given size. The central result is a combinatorial characterization of such optimal graphs using the girth of the graph. The authors establish existence of these optimal graphs for every choice of the size parameter s and show that optimality for size s produces new lower bounds on the number of neighbors for all larger sets of size h at least s. These constructions are then applied to the design of codes for key exchange in post-quantum cryptography.

Core claim

A left-regular bipartite graph is an optimal small-set expander precisely when its girth satisfies a certain combinatorial threshold; for every s such graphs exist, and s-optimality transfers to give improved lower bounds on the neighbor count of every set of size h greater than or equal to s.

What carries the argument

The girth condition that combinatorially identifies s-optimal small-set expanders.

If this is right

  • s-optimal expanders exist for every positive integer s.
  • s-optimality produces explicit transfer lower bounds on the expansion of every set of size h greater than or equal to s.
  • Optimal small-set expanders supply new constructions of codes suitable for key exchange in post-quantum cryptography.

Where Pith is reading between the lines

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

  • The transfer mechanism may extend to give bounds on other expansion-like quantities such as edge expansion or vertex expansion in the same graphs.
  • If girth is easy to control in explicit constructions, the existence result supplies a route to explicit optimal expanders rather than only random ones.
  • The coding application suggests that the same graphs could improve parameters in other expander-based cryptographic primitives that rely on small-set expansion.

Load-bearing premise

The assumption that girth alone determines the maximum number of neighbors any small set can have.

What would settle it

A single left-regular bipartite graph whose girth meets the stated threshold yet some set of size at most s has strictly fewer neighbors than the claimed optimum.

read the original abstract

A left-regular bipartite graph $G$ of degree $d$ is called a $(t,\alpha)$-small-set-expander if every subset $X$ of left vertices of size at most $t$ has at least $\alpha |X|$ neighbors. Such a graph is an optimal small-set expander if small subsets have as many neighbors as possible. We characterize optimal expanders combinatorially via girth and prove the existence of $s$-optimal expanders for every $s$. We also prove that $s$-optimality yields new "transfer" lower bounds on the number of neighbors of sets of size $h\geq s$. Finally, as an application, we discuss the use of optimal small-set expanders in building good codes for key exchange protocols in post-quantum cryptography.

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.

Referee Report

3 major / 3 minor

Summary. The paper defines (t,α)-small-set-expanders on left-regular bipartite graphs of degree d, where every left-set X with |X|≤t has |N(X)|≥α|X|. It claims a combinatorial characterization of optimal such expanders via a girth condition that forces every set of size at most s to achieve the Moore-like maximum number of neighbors; proves existence of s-optimal expanders for every s; derives new transfer lower bounds on |N(X)| for |X|≥s; and discusses applications to codes for post-quantum key exchange.

Significance. If the girth characterization holds, the work supplies an explicit combinatorial criterion for optimality, existence constructions for every s, and transfer bounds that extend small-set expansion results. These could inform explicit constructions in coding theory. The paper provides no machine-checked proofs or parameter-free derivations, but the claimed if-and-only-if equivalence and transfer bounds would be the primary contributions if verified.

major comments (3)
  1. [Characterization (results paragraph and §3)] The central if-and-only-if characterization (that a left-regular bipartite graph is s-optimal precisely when it meets the stated girth condition forcing maximal |N(X)| for all |X|≤s) is load-bearing for both the existence theorem and the transfer bounds. The 'only if' direction must rule out the possibility of an optimal graph with strictly smaller girth; without an explicit lemma or exhaustive case analysis showing this direction, the subsequent claims that s-optimality implies the transfer lower bounds for h≥s do not follow.
  2. [Existence proof (§4)] Existence of s-optimal expanders for every s is asserted via constructions satisfying the girth condition. If the characterization equivalence fails in either direction, these constructions may achieve the girth bound without attaining optimality, undermining the existence claim and any downstream transfer bounds derived from it.
  3. [Transfer bounds (§5)] The transfer lower bounds for sets of size h≥s are derived directly from s-optimality. Because these bounds rest on the unverified equivalence, the paper must either supply an independent proof of the bounds or confirm the characterization with a concrete verification (e.g., small-s exhaustive check or counter-example search) before the bounds can be accepted.
minor comments (3)
  1. [Abstract] The abstract states that s-optimality 'yields new transfer lower bounds' but does not exhibit the explicit form of the bound or compare it quantitatively to prior expansion results.
  2. [Preliminaries] Notation for the girth threshold and the precise Moore-like neighbor count is introduced without a displayed equation or table summarizing the exact girth value required for each s and d.
  3. [Applications] The cryptographic application section would benefit from a small numerical example (specific d, s, and resulting code parameters) illustrating the claimed improvement.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful and constructive report. The comments correctly identify that the 'only if' direction of the girth characterization would benefit from a more explicit and self-contained treatment to strengthen the logical chain to the existence and transfer results. We will revise the manuscript to address this. Point-by-point responses appear below.

read point-by-point responses

  1. Referee: [Characterization (results paragraph and §3)] The central if-and-only-if characterization (that a left-regular bipartite graph is s-optimal precisely when it meets the stated girth condition forcing maximal |N(X)| for all |X|≤s) is load-bearing for both the existence theorem and the transfer bounds. The 'only if' direction must rule out the possibility of an optimal graph with strictly smaller girth; without an explicit lemma or exhaustive case analysis showing this direction, the subsequent claims that s-optimality implies the transfer lower bounds for h≥s do not follow.

    Authors: We agree that an isolated lemma would improve readability. The current proof of the 'only if' direction (Theorem 3.1) proceeds by contraposition: a girth defect produces a short cycle whose vertices can be used to build a left-set X with |X|≤s whose neighborhood is strictly smaller than the Moore-type maximum. In the revision we will extract this argument into a new standalone Lemma 3.2 containing an exhaustive case analysis on the possible cycle lengths (4,6,…,2s) and how each yields a deficient set. This makes the dependence on the girth condition fully explicit before the existence and transfer sections are invoked. revision: yes

  2. Referee: [Existence proof (§4)] Existence of s-optimal expanders for every s is asserted via constructions satisfying the girth condition. If the characterization equivalence fails in either direction, these constructions may achieve the girth bound without attaining optimality, undermining the existence claim and any downstream transfer bounds derived from it.

    Authors: The constructions (incidence graphs of geometries and suitable random lifts) are already known to meet the girth lower bound required by the characterization. With the new explicit Lemma 3.2 in place, the same constructions immediately certify s-optimality. Section 4 will be updated with a one-paragraph forward reference to the lemma, confirming that girth attainment implies the optimal expansion property for all sets of size ≤s. revision: yes

  3. Referee: [Transfer bounds (§5)] The transfer lower bounds for sets of size h≥s are derived directly from s-optimality. Because these bounds rest on the unverified equivalence, the paper must either supply an independent proof of the bounds or confirm the characterization with a concrete verification (e.g., small-s exhaustive check or counter-example search) before the bounds can be accepted.

    Authors: The transfer argument in §5 applies the per-set expansion guarantee repeatedly. To decouple it from the full if-and-only-if statement we will add a short appendix that derives the same lower bounds on |N(X)| for |X|≥s using only the 'if' direction (girth implies optimal small-set expansion) together with a simple counting argument on the number of paths of length 2. This supplies an independent route to the transfer bounds while the strengthened characterization remains the primary contribution. revision: partial

Circularity Check

0 steps flagged

No circularity: combinatorial characterization and existence proofs are self-contained

full rationale

The paper defines s-optimal expanders directly from the neighbor-count maximality condition and then states a girth-based combinatorial characterization as a theorem to be proved. No equations reduce a derived quantity to a fitted parameter by construction, no load-bearing self-citations are invoked to justify the central equivalence, and the existence and transfer-bound results are presented as consequences of the (to-be-proved) characterization rather than presupposing it. The derivation therefore rests on standard combinatorial arguments rather than on any of the enumerated circular patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based solely on the abstract, the claims rest on standard definitions and axioms of bipartite graphs and neighbor sets; no free parameters, invented entities, or ad-hoc assumptions are mentioned.

axioms (1)
  • standard math Standard definitions and properties of left-regular bipartite graphs and their neighbor sets
    The (t,α) definition and girth characterization rely on basic graph-theoretic notions.

pith-pipeline@v0.9.1-grok · 5667 in / 1270 out tokens · 34083 ms · 2026-06-26T07:46:34.294344+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

14 extracted references · 4 canonical work pages

  1. [1]

    Specification document for the QC-MDPC code-based KEM using bit-flipping decoding

    BIKE Team,BIKE: Bit-Flipping Key Encapsulation, Technical Report Spec v4.0, BIKE Consortium, 2020. Specification document for the QC-MDPC code-based KEM using bit-flipping decoding

    2020

  2. [2]

    215, posted on 2022, 43:1–43:3, DOI 10.4230/LIPIcs.ITCS.2022.43

    Xue and Cheng Chen Kuan and Li,Improved decoding of expander codes, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), Leibniz International Proceedings in Informatics (LIPIcs), V ol. 215, posted on 2022, 43:1–43:3, DOI 10.4230/LIPIcs.ITCS.2022.43

    work page doi:10.4230/lipics.itcs.2022.43 2022

  3. [3]

    G. A. Margulis,Explicit constructions of concentrators, Problems of Information Transmission9(1973), no. 4, 325–332

    1973

  4. [4]

    1, 39–46

    ,Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators, Problems of Information Transmission24(1988), no. 1, 39–46

    1988

  5. [5]

    6, 1710–1722

    Michael Sipser and Daniel A Spielman,Expander codes, IEEE transactions on Information Theory42(1996), no. 6, 1710–1722

    1996

  6. [6]

    1, 157–187

    Omer Reingold, Salil Vadhan, and Avi Wigderson,Entropy waves, the zig-zag graph product, and new constant- degree expanders, Annals of Mathematics155(2002), no. 1, 157–187

    2002

  7. [7]

    Louis Golowich,New explicit constant-degree lossless expanders, arXiv preprintarXiv:2306.07551(2024)

    arXiv 2024

  8. [8]

    4, 439–561

    Shlomo Hoory, Nathan Linial, and Avi Wigderson,Expander graphs and their applications, Bulletin of the American Mathematical Society43(2006), no. 4, 439–561

    2006

  9. [9]

    Noga and Hoory Alon Shlomo and Linial,The Moore Bound for Irregular Graphs, Graphs and Combinatorics18 (2002), 53–57, DOI 10.1007/s003730200002

    work page doi:10.1007/s003730200002 2002

  10. [10]

    1, 7–16, DOI 10.1016/0167-7152(91)90170-V

    Werner Ehm,Binomial approximation to the Poisson binomial distribution, Statistics & Probability Letters11 (1991), no. 1, 7–16, DOI 10.1016/0167-7152(91)90170-V

    work page doi:10.1016/0167-7152(91)90170-v 1991

  11. [11]

    Shlomo Hoory,The Size of Bipartite Graphs With a Given Girth, Journal of Combinatorial Theory, Series B86 (2001), DOI 10.1006/jctb.2002.2123

    work page doi:10.1006/jctb.2002.2123 2001

  12. [12]

    Sheida Rabeti and Mohsen Moradi and Hessam Mahdavifar,Bounds and New Constructions for Girth-Constrained Regular Bipartite Graphs, 2025 IEEE International Symposium on Information Theory (ISIT) (2025), 1-6

    2025

  13. [13]

    Jessie MacWilliams and Neil J

    F. Jessie MacWilliams and Neil J. A. Sloane,The Theory of Error-Correcting Codes, North-Holland Publishing Company, Amsterdam, 1977

    1977

  14. [14]

    Berlekamp and Robert J

    Elwyn R. Berlekamp and Robert J. McEliece and Henk C. A. van Tilborg,On the Inherent Intractability of Certain Coding Problems, IEEE Transactions on Information Theory24(1978), no. 3, 384–386

    1978