Pith. sign in

REVIEW 1 major objections 5 minor 1 cited by

Explicit Lossless Vertex Expanders

T0 review · 1 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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…

desk verdict First explicit constant-degree lossless vertex expanders; the proof is coherent and the paper resolves a genuine open problem. read the letter →

arxiv 2504.15087 v1 pith:RHP3PYLQ submitted 2025-04-21 math.CO cs.CCcs.DMcs.DSmath.GR

Jun-Ting Hsieh , Alexander Lubotzky , Sidhanth Mohanty , Assaf Reiner , Rachel Yun Zhang This is my paper · ORCID
classification math.COcs.CCcs.DMcs.DSmath.GR MSC 05C4805C25
keywords losslessvertexexpandersexplicitconstructioncubicalcomplexesRamanujangraphssmall-setexpansionquantumLDPCcodesHadamardcodetripartitelineproduct
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 5 minor

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.

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 (1)
  1. [Section 3.1, Satisfying degree constraints] 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.
minor comments (5)
  1. [Section 4.2, Lemma 4.9; Definition 3.4; Theorem 3.5] 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.
  2. [Section 3, proof of Lemma 3.3] 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.
  3. [Section 3.2, Claim 3.14] The definition of Delta(sigma) contains a typo: sigma_{j1}[i] != sigma_{j2}[k] should read sigma_{j1}[i] != sigma_{j2}[i].
  4. [Theorem 2.2] 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.
  5. [Remark 2.3] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity; the derivation is self-contained given independent Ramanujan and probabilistic gadget ingredients.

full rationale

The central theorem is not a restatement of its inputs. The gadget graph H is an external probabilistic-existence object (Lemma 2.9 from [HLMOZ25]) whose properties are not equivalent to the target infinite-family lossless expansion result, and the base graphs are explicitly constructed from LPS Ramanujan Cayley graphs via quaternion set-commutation (Lemmas 4.8 and 4.9), with the Ramanujan property used only as a black box. The small-set subcube density lemma (Lemmas 3.12 through 3.16) is proved in the paper from the 2k-expanding definition using entropy arguments and the expander mixing lemma, rather than imported as an assumption. The skeleton expansion and special-set structure of the base graphs are verified in Section 3.1. Self-citations to [HMMP24] and [HLMOZ25] supply the tripartite product framework, the constant-sized gadget existence lemma, and an orientation lemma; these are prior independent results with stated assumptions that do not include the target theorem, so they do not constitute circularity. The quantum LDPC application verifies Conjecture A.1 of [LH22b] rather than assuming it, so there is no definitional equivalence between the conjecture and the present construction. No fitted parameter is relabeled as a prediction. The apparent 2k versus 2^k factor in Lemma 4.9 affects only constants hidden in O_k(1) and does not change the logical dependence chain.

Assumptions & free parameters 0 free parameters · 8 assumptions · 0 invented entities

The main argument introduces no fitted numerical constants: epsilon and beta are theorem inputs, while k, D, delta, dL, dR are slack parameters fixed by inequalities, and all residual O_k(1) and o_D(1) constants are allowed to depend on epsilon and beta. The construction relies on standard number-theoretic and spectral theorems listed above. No new physical or formal entities are postulated; the cubical complex is constructed explicitly.

assumptions (8)
  • standard math Jacobi's four-square theorem: r4(n) = 8 sum_{m|n} m for odd n (Fact 4.1).
    Used to count quaternion generators of a given norm, giving |A(p)| = p+1 and |A(p1...pk)| = prod_i (p_i+1).
  • standard math Unique factorization of Lipschitz quaternions with odd norm up to unit migration (Fact 4.4).
    Used in Lemma 4.8 to prove A(p1) ... A(pk) = A(p1...pk), which is the cubical generating-set property at the base of the construction.
  • standard math LPS Ramanujan theorem: Cay(PSL(2,F_q); A(p)) has all nontrivial eigenvalues at most 2 sqrt(p) (Theorem 4.7).
    Black-box spectral bound from which the 2k-expanding property of the cubical complexes and the skeleton expansion of coded incidence graphs follow.
  • standard math Dirichlet's theorem on primes in arithmetic progressions and explicit density bounds for primes in short intervals (Lemma 4.10, Fact 4.11).
    Yields infinitely many primes q for the base complex and nearby primes p_i in [x,2x] that realize the degree parameters D_L and D_R.
  • domain assumption Existence of a constant-sized (dL,dR)-biregular gadget H with lossless expansion and spread properties (Lemma 2.9, cited from HLMOZ25).
    The gadget is found by brute force from the probabilistic existence lemma; the current paper does not prove Lemma 2.9. It is a key local-to-global ingredient but is not the target result.
  • standard math Loomis-Whitney / Shearer entropy inequality for projections of joint distributions.
    Used in Lemma 3.15 to bound the number of C-faces containing a middle vertex by products of neighbor counts, the core of the subcube density bound.
  • standard math Expander mixing lemma for bipartite graphs with second eigenvalue bound.
    Used in Lemma 3.16 to count middle vertices with large neighbor sets, one of the two pillars of Lemma 3.12.
  • standard math Hadamard code H_k is linear of size k, dimension log k, and pairwise distance k/2.
    The distance-k/2 property makes all links between code points have comparable degree O(sqrt(D)), enabling the subcube density argument.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Explicit Lossless Vertex Expanders." pith.science (2026). https://pith.science/paper/RHP3PYLQ

@misc{pith2026250415087,
  author       = {Pith},
  title        = {Pith review of: Explicit Lossless Vertex Expanders},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RHP3PYLQ}},
  note         = {Machine review of arXiv:2504.15087}
}
abstract

We give the first construction of explicit constant-degree lossless vertex expanders. Specifically, for any $\varepsilon > 0$ and sufficiently large $d$, we give an explicit construction of an infinite family of $d$-regular graphs where every small set $S$ of vertices has $(1-\varepsilon)d|S|$ neighbors (which implies $(1-2\varepsilon)d|S|$ unique-neighbors). Our results also extend naturally to construct biregular bipartite graphs of any constant imbalance, where small sets on each side have strong expansion guarantees. The graphs we construct admit a free group action, and hence realize new families of quantum LDPC codes of Lin and M. Hsieh with a linear time decoding algorithm. Our construction is based on taking an appropriate product of a constant-sized lossless expander with a base graph constructed from Ramanujan Cayley cubical complexes.

Figures

Figures reproduced from arXiv: 2504.15087 by the authors.

Figure 1
Figure 1. A 3-dimensional (decorated) cubical complex [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. The tripartite line product between a base graph [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. The two bipartite base graphs GL, GR have the structure that M has k parts, and for u ∈ M and v, w ∈ M from a different part, the common neighborhoods NGR (u) ∩ NGR (v) and NGR (u) ∩ NGR (w) ⊆ R are disjoint, each corresponding to a special set in [DR], i.e., NGR (u) ∩ NGR (v) = Nbru(Qi) for some special set Qi ⊆ [DR]. Figure 3a shows an example of RED(S), a subgraph of GR. The middle-to-right analysis involves uppe… view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Discrete Poincar\'e inequalities and universal approximators for random graphs

    math.MG 2025-06 conditional novelty 7.0 of 10

    Independent random regular graphs satisfy a dimension-free nonlinear Poincaré inequality, resolving Kleinberg's problem and giving universal approximators for all p ≥ 1.

Reference graph

Works this paper leans on

53 extracted references · 37 canonical work pages · cited by 1 Pith paper

  1. [1]

    Explicit unique-neighbor expanders

    Noga Alon and Michael Capalbo. Explicit unique-neighbor expanders. In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. , pages 73--79. IEEE, 2002

    2002

  2. [2]

    Bipartite unique-neighbour expanders via Ramanujan graphs

    Ron Asherov and Irit Dinur. Bipartite unique-neighbour expanders via Ramanujan graphs . arXiv preprint arXiv:2301.03072 , 2023

    arXiv 2023

  3. [3]

    N. Alon, J. Edmonds, and M. Luby. Linear time erasure codes with nearly optimal recovery. In Proceedings of IEEE 36th Annual Foundations of Computer Science , pages 512--519, 1995

    1995

  4. [4]

    On-Line Algorithms for Path Selection in a Nonblocking Network

    Sanjeev Arora, FT Leighton, and Bruce M Maggs. On-Line Algorithms for Path Selection in a Nonblocking Network . SIAM Journal on Computing , 25(3):600--625, 1996

    work page 1996

  5. [5]

    Random Cayley graphs and expanders

    Noga Alon and Yuval Roichman. Random Cayley graphs and expanders . Random Structures & Algorithms , 5(2):271--284, 1994

    work page 1994

  6. [6]

    Optimal construction of edge-disjoint paths in random graphs

    Andrei Z Broder, Alan M Frieze, Stephen Suen, and Eli Upfal. Optimal construction of edge-disjoint paths in random graphs. SIAM Journal on Computing , 28(2):541--573, 1998

    work page 1998

  7. [7]

    Combining geometry and combinatorics: A unified approach to sparse signal recovery

    Radu Berinde, Anna C Gilbert, Piotr Indyk, Howard Karloff, and Martin J Strauss. Combining geometry and combinatorics: A unified approach to sparse signal recovery . In 2008 46th Annual Allerton Conference on Communication, Control, and Computing , pages 798--805. IEEE, 2008

    work page 2008

  8. [8]

    Explicit bounds for primes in arithmetic progressions

    Michael A Bennett, Greg Martin, Kevin O’Bryant, and Andrew Rechnitzer. Explicit bounds for primes in arithmetic progressions. Illinois Journal of Mathematics , 62(1-4):427--532, 2018

    work page 2018

Show all 53 references
  1. [9]

    Quasi-Linear Size PCPs with Small Soundness from HDX

    Mitali Bafna, Dor Minzer, and Nikhil Vyas. Quasi-Linear Size PCPs with Small Soundness from HDX . arXiv preprint arXiv:2407.12762 , 2024

    2024 arXiv

  2. [10]

    Tensor products of weakly smooth codes are robust

    Eli Ben-Sasson and Michael Viderman. Tensor products of weakly smooth codes are robust . Theory of Computing , 5(1):239--255, 2009

    2009

  3. [11]

    Two-Sided Lossless Expanders in the Unbalanced Setting , 2024

    Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, and Yunya Zhao. Two-Sided Lossless Expanders in the Unbalanced Setting , 2024

    2024

  4. [12]

    Unique-neighbor Expanders with Better Expansion for Polynomial-sized Sets

    Yeyuan Chen. Unique-neighbor Expanders with Better Expansion for Polynomial-sized Sets . In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 3335--3362. SIAM, 2025

    2025

  5. [13]

    HDX Condensers

    Itay Cohen, Roy Roth, and Amnon Ta - Shma. HDX Condensers . In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages 1649--1664, 2023

    2023

  6. [14]

    Randomness conductors and constant-degree lossless expanders

    Michael Capalbo, Omer Reingold, Salil Vadhan, and Avi Wigderson. Randomness conductors and constant-degree lossless expanders. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing , pages 659--668, 2002

    2002

  7. [15]

    On quaternions and octonions

    John H Conway and Derek A Smith. On quaternions and octonions . AK Peters/CRC Press, 2003

    2003

  8. [16]

    Locally Testable Codes with constant rate, distance, and locality

    Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, and Shahar Mozes. Locally Testable Codes with constant rate, distance, and locality . In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages 357--374, 2022

    2022

  9. [17]

    Arithmetic of quaternions

    Leonard E Dickson. Arithmetic of quaternions. Proceedings of the London Mathematical Society , 2(1):225--232, 1922

    1922

  10. [18]

    Expanders and PCPs: Emergence from Local to Global

    Irit Dinur. Expanders and PCPs: Emergence from Local to Global . FOCS 2024 Plenary Talk, YouTube video, 2024. https://www.youtube.com/watch?v=5eGoy6NfkZE

    2024

  11. [19]

    Expansion of High-Dimensional Cubical Complexes: with Application to Quantum Locally Testable Codes

    Irit Dinur, Ting-Chun Lin, and Thomas Vidick. Expansion of High-Dimensional Cubical Complexes: with Application to Quantum Locally Testable Codes . In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages 379--385. IEEE, 2024

    2024

  12. [20]

    Robust local testability of tensor products of LDPC codes

    Irit Dinur, Madhu Sudan, and Avi Wigderson. Robust local testability of tensor products of LDPC codes . In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. , pages 304--315. Springer, 2006

    2006

  13. [21]

    Almost Euclidean subspaces of _1^N via expander codes

    Venkatesan Guruswami, James R Lee, and Alexander Razborov. Almost Euclidean subspaces of _1^N via expander codes . Combinatorica , 30(1):47--68, 2010

    2010

  14. [22]

    _p -Spread and Restricted Isometry Properties of Sparse Random Matrices

    Venkatesan Guruswami, Peter Manohar, and Jonathan Mosheiff. _p -Spread and Restricted Isometry Properties of Sparse Random Matrices . In 37th Computational Complexity Conference (CCC 2022) . Schloss Dagstuhl-Leibniz-Zentrum f \"u r Informatik, 2022

    2022

  15. [23]

    New explicit constant-degree lossless expanders

    Louis Golowich. New explicit constant-degree lossless expanders. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 4963--4971. SIAM, 2024

    2024

  16. [24]

    Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes

    Venkatesan Guruswami, Christopher Umans, and Salil Vadhan. Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes . Journal of the ACM (JACM) , 56(4):1--34, 2009

    2009

  17. [25]

    Explicit Two-Sided Vertex Expanders Beyond the Spectral Barrier

    Jun-Ting Hsieh, Ting-Chun Lin, Sidhanth Mohanty, Ryan O'Donnell, and Rachel Yun Zhang. Explicit Two-Sided Vertex Expanders Beyond the Spectral Barrier . In Proceedings of the 57th Annual ACM Symposium on Theory of Computing , 2025

    2025

  18. [26]

    Expander graphs and their applications

    Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin (new series) of the American Mathematical Society , 43(4):439--561, 2006

    2006

  19. [27]

    Explicit two-sided unique-neighbor expanders

    Jun-Ting Hsieh, Theo McKenzie, Sidhanth Mohanty, and Pedro Paredes. Explicit two-sided unique-neighbor expanders. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 788--799, 2024

    2024

  20. [28]

    Monotone circuits for the majority function

    Shlomo Hoory, Avner Magen, and Toniann Pitassi. Monotone circuits for the majority function. In International Workshop on Approximation Algorithms for Combinatorial Optimization , pages 410--425. Springer, 2006

    2006

  21. [29]

    The Ramanujan property for regular cubical complexes

    Bruce W Jordan and Ron Livn \'e . The Ramanujan property for regular cubical complexes . Duke Math. J. , 104(1):85--103, 2000

    2000

  22. [30]

    Explicit Abelian Lifts and Quantum LDPC Codes

    Fernando Granha Jeronimo, Tushant Mittal, Ryan O'Donnell, Pedro Paredes, and Madhur Tulsiani. Explicit Abelian Lifts and Quantum LDPC Codes . In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) , pages 88--1. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Inf...

    2022

  23. [31]

    Eigenvalues and expansion of regular graphs

    Nabil Kahale. Eigenvalues and expansion of regular graphs. Journal of the ACM (JACM) , 42(5):1091--1106, 1995

    1995

  24. [32]

    Deterministic construction of a high dimensional _p section in _1^n for any p < 2

    Zohar S Karnin. Deterministic construction of a high dimensional _p section in _1^n for any p < 2 . In Proceedings of the forty-third annual ACM symposium on Theory of computing , pages 645--654, 2011

    2011

  25. [33]

    Combinatorics via closed orbits: number theoretic Ramanujan graphs are not unique neighbor expanders

    Amitay Kamber and Tali Kaufman. Combinatorics via closed orbits: number theoretic Ramanujan graphs are not unique neighbor expanders . In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages 426--435, 2022

    2022

  26. [34]

    Simple Constructions of Unique Neighbor Expanders from Error-correcting Codes

    Swastik Kopparty, Noga Ron - Zewi, and Shubhangi Saraf. Simple Constructions of Unique Neighbor Expanders from Error-correcting Codes . arXiv preprint arXiv:2310.19149 , 2023

    2023 arXiv

  27. [35]

    Unbalanced Expanders from Multiplicity Codes

    Itay Kalev and Amnon Ta - Shma. Unbalanced Expanders from Multiplicity Codes . In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) , pages 12--1. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2022

    2022

  28. [36]

    Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs

    Dmitriy Kunisky and Xifan Yu. Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs . In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages 1621--1633. IEEE, 2024

    2024

  29. [37]

    c^3 -Locally Testable Codes from Lossless Expanders

    Ting-Chun Lin and Min-Hsiu Hsieh. c^3 -Locally Testable Codes from Lossless Expanders . In 2022 IEEE International Symposium on Information Theory (ISIT) , pages 1175--1180. IEEE, 2022

    2022

  30. [38]

    Good quantum LDPC codes with linear time decoder from lossless expanders

    Ting-Chun Lin and Min-Hsiu Hsieh. Good quantum LDPC codes with linear time decoder from lossless expanders . arXiv preprint arXiv:2203.03581 , 2022

    2022 arXiv

  31. [39]

    Ramanujan graphs

    Alexander Lubotzky, Ralph Phillips, and Peter Sarnak. Ramanujan graphs. Combinatorica , 8:261--277, 1988

    1988

  32. [40]

    Explicit constructions of R amanujan complexes of type A _d

    Alexander Lubotzky, Beth Samuels, and Uzi Vishne. Explicit constructions of R amanujan complexes of type A _d . European Journal of Combinatorics , 26(6):965--993, 2005

    2005

  33. [41]

    Ramanujan complexes of type A _d

    Alexander Lubotzky, Beth Samuels, and Uzi Vishne. Ramanujan complexes of type A _d . Israel Journal of Mathematics , 149:267--299, 2005. Probability in mathematics

    2005

  34. [42]

    Discrete groups, expanding graphs and invariant measures , volume 125

    Alex Lubotzky. Discrete groups, expanding graphs and invariant measures , volume 125. Springer Science & Business Media, 1994

    1994

  35. [43]

    An inequality related to the isoperimetric inequality

    LH Loomis and H Whitney. An inequality related to the isoperimetric inequality . Bulletin of the American Mathematical Society , 55(10):961--962, 1949

    1949

  36. [44]

    High-Girth Near-Ramanujan Graphs with Lossy Vertex Expansion

    Theo McKenzie and Sidhanth Mohanty. High-Girth Near-Ramanujan Graphs with Lossy Vertex Expansion . In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) . Schloss Dagstuhl-Leibniz-Zentrum f \"u r Informatik, 2021

    2021

  37. [45]

    Existence and explicit constructions of q+1 regular R amanujan graphs for every prime power q

    Moshe Morgenstern. Existence and explicit constructions of q+1 regular R amanujan graphs for every prime power q . J. Combin. Theory Ser. B , 62(1):44--62, 1994

    1994

  38. [46]

    On the arithmetic of quaternions

    Gordon Pall. On the arithmetic of quaternions. Transactions of the American Mathematical Society , 47(3):487--500, 1940

    1940

  39. [47]

    Self-routing superconcentrators

    Nicholas Pippenger. Self-routing superconcentrators. In Proceedings of the twenty-fifth annual ACM symposium on Theory of Computing , pages 355--361, 1993

    1993

  40. [48]

    Asymptotically good quantum and locally testable classical LDPC codes

    Pavel Panteleev and Gleb Kalachev. Asymptotically good quantum and locally testable classical LDPC codes . In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages 375--388, 2022

    2022

  41. [49]

    Infinite series of quaternionic 1-vertex cube complexes, the doubling construction, and explicit cubical Ramanujan complexes

    Nithi Rungtanapirom, Jakob Stix, and Alina Vdovina. Infinite series of quaternionic 1-vertex cube complexes, the doubling construction, and explicit cubical Ramanujan complexes . International Journal of Algebra and Computation , 29(06):951--1007, 2019

    2019

  42. [50]

    Theory at the Institute and Beyond, February 2025

    Nikhil Srivastava. Theory at the Institute and Beyond, February 2025 . Simons Institute Blog , February 2025. https://simons.berkeley.edu/news/theory-institute-beyond-february-2025

    2025

  43. [51]

    Expander codes

    Michael Sipser and Daniel Spielman. Expander codes. IEEE Trans. Inform. Theory , 42(6, part 1):1710--1722, 1996

    1996

  44. [52]

    Lossless condensers, unbalanced expanders, and extractors

    Amnon Ta - Shma, Christopher Umans, and David Zuckerman. Lossless condensers, unbalanced expanders, and extractors. Combinatorica , 27:213--240, 2007

    2007

  45. [53]

    Linear-time decoding of regular expander codes

    Michael Viderman. Linear-time decoding of regular expander codes. ACM Transactions on Computation Theory (TOCT) , 5(3):1--25, 2013

    2013

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.