Combinatorics · arXiv:2611.16295 v1 · submitted 12 Nov 2026 · 123 references
Polynomial Swap Coboundary Expansion with Applications to LTCs and PCPs
The paper says
“Swap coboundary expansion, introduced independently by Bafna–Minzer and Dikstein–Dinur, is a local-to-global property that underlies agreement tests in the low-acceptance regime and recent constructions of succinct PCPs.”
more of the abstract
Previous works obtained bounds of exp(−O(√r)) for the r-swap coboundary expansion of Chapman–Lubotzky complexes. We establish the first inverse-polynomial bounds for bounded-degree complexes: suitable skeleta of Kac–Moody–Steinberg (KMS) complexes have r-swap coboundary expansion at least r−O(1). Our theorem supplies a key ingredient in forthcoming work of Ben Yaacov–Dikstein–Liu, which obtains local tests for sparse algebraic codes with guarantees even at arbitrarily small acceptance probability. These tests use exp(poly(1/ε)) queries and guarantee that any word accepted with probability at least ε agrees with a codeword on an εO(1) fraction of coordinates. Separately, substituting our bound into the existing analysis of Bafna–Minzer–Vyas–Yun improves the soundness dependence of their two-query PCP construction, giving perfect completeness, soundness ε, and proof length n(logn)exp(poly(1/ε)). Our proof exploits the product structure of the groups arising in KMS complexes. The main new ingredient is a decomposition lemma for Dehn functions, which separates the analysis of group relations into independent problems on much smaller factors, with only polynomial overhead.
from the abstract
Pith says
Machine review · deepseek-v4-flash · 13 Nov 2026 · what was read was not recorded · not checked by a person
It can be wrong. Challenge this review or reply to it.
The passes disagreed. Reader: holds up. Skeptic: agrees with the reader. Referee: major revision.
First inverse-polynomial swap coboundary expansion—real progress, but the load-bearing external results are still preprints. This line is wrong
3 major objections · 8 minor
How often objections from reviews like this one are right: not yet measured
Not checked: figures, code, what the 123 references say.
The paper says, at §2.4 (Theorems 2.20, 2.21)
The review did not quote this passage.
Pith says: Objection 1 of 3 · major
The vanishing first cohomology (H^1(X,Λ)=1) and the local spectral expansion bound (λ_2 ≤ 2/(√q–2)) are cited from the unpublished preprints [OV25] and [LO25], respectively. The entire construction of the swap coboundary expander in Theorem 1.2 depends on these two properties holding for the specific parameter regime: q ≥ q_0 = poly(r) (the paper states q_0 ≥ 10^4) and d ≥ d_0 = r^{55}.
more of objection 1
The referee cannot verify that [OV25] and [LO25] already cover the required ranges without hidden parameter incompatibilities (e.g., whether the vanishing-cohomology argument requires d bounded independently of q, or whether the spectral bound requires a larger lower bound on q for the dimension d = r^{55}). Because the proof chain (local-to-global, colored faces, links, Dehn function) collapses without these inputs, the authors should either (a) include a summary of the relevant parts of the proofs from [OV25] and [LO25] that confirms they apply to the stated parameter regime, or (b) explicitly state these two properties as assumptions of Theorem 1.2, clarifying the reliance on forthcoming work.
The paper says, at §3.1–3.2 (application of Theorem 3.3 and Theorem 3.11)
The review did not quote this passage.
Pith says: Objection 2 of 3 · major
The local-to-global reduction (Theorem 3.3 from [DD23c]) assumes that FrX is a γ-local spectral expander for γ < 1/(rT). The paper verifies this for the KMS complexes using the bound from Theorem 2.20. However, the parameter γ_1 in Theorem 3.1 is chosen as a value slightly less than 1/r^{11}, and the spectral bound from Theorem 2.20 gives λ ≤ 2/(√q–2).
more of objection 2
To satisfy γ_1 > 2/(√q–2), q must be large enough – the paper sets q_0 accordingly. This is consistent, but the dependence on the cited spectral bound from [LO25] remains: if that bound deteriorates for the relevant links (e.g., because the trickle-down theorem has an extra factor that depends on dimension in a way not captured by the exposition), the spectral condition may fail. The paper should provide a more concrete calculation showing that the required inequality holds under the cited theorem's hypotheses.
The paper says, at Appendix A
The review did not quote this passage.
Pith says: Objection 3 of 3 · major
The PCP application in Appendix A is presented as a sketch that follows [Baf+25] and records parameter changes. While this is acceptable for an appendix, the paper should state explicitly that the PCP theorem (Theorem 1.3) is contingent on the correctness of Theorem 1.2 and on the unmodified analysis of [Baf+25]. No new PCP analysis is claimed, so the sketch suffices, but a brief remark about this conditional nature would help the reader.
8 minor objections
The paper says, at Abstract
Pith says: minor objection 1 of 8
The phrase 'Bafna--Minzer' should use en-dashes or hyphens consistently (here it is a double hyphen; either is fine, but be consistent).
The paper says, at §2.2.2 (Definition of reduced cohomology)
Pith says: minor objection 2 of 8
The sentence 'We will say that the k-th cohomology is trivial if H^k(X,Λ) = {[ϕ≡1]}, denoted H^k(X,Λ)=1' could be clarified by writing 'denoted H^k(X,Λ) = 1' after stating that 1 denotes the trivial cohomology class.
show 6 more
The paper says, at §2.6 (Dehn functions)
Pith says: minor objection 3 of 8
The notation 'Dehn_X(t)' is defined but never used; later the notation 'Dehn_{S,R}(m)' is used; consider unifying.
The paper says, at Lemma 3.7
Pith says: minor objection 4 of 8
The lemma states 'T ≥ r^{10}' but the proof sets 'T = r^{10}' for concreteness. The condition 'T ≥ r^{10}' is fine, but the proof should cover the general case or state that T can be taken exactly r^{10} without loss.
The paper says, at §4 (color sampling lemma)
Pith says: minor objection 5 of 8
The proof uses the inequality 'd+1 ≥ 100(r+1)^2 T^2', but this is not restated in the lemma. It might be helpful to include the explicit numeric condition in the lemma statement.
The paper says, at §5.3 (Theorem 5.5)
Pith says: minor objection 6 of 8
The constant C' is said to be universal but no explicit upper bound is given. While not required, an estimate (e.g., C' ≤ 360) from the proof would be informative.
The paper says, at §7 (Lemma 7.2)
Pith says: minor objection 7 of 8
The lemma claims 'Dehn_{Y_ℓ}(s) ≤ As' for a universal constant A, but the proof shows A = 4C_0 C' + C_1, where C_0, C_1, C' are from earlier arguments. It would be good to note that A is independent of all parameters, which is the important point.
The paper says, at Throughout
Pith says: minor objection 8 of 8
The paper uses 'poly(r)' without specifying the degree. For critical parameters such as d_0 = r^{55}, it is explicit, but for many intermediate quantities (e.g., the number of colors T, the spectral gap γ) the polynomial dependence is not made precise. Adding explicit exponents when they are fixed (e.g., T = r^{10}) would improve clarity.
What would settle it
Independently verify that the spectral gap bound λ₂ ≤ 2/(√q–2) from [LO25] holds for every dimension d = r⁵⁵ (where r ≥ 10⁴) when q is a prime power ≥ q₀ = exp(poly(r)). Similarly, confirm that the vanishing cohomology result of [OV25] applies to the same q and d, and that the group Λ with no p‑torsion includes all finite groups with order not divisible by p (as required). If either test fails for the stated parameter range, the swap coboundary expansion claim is unsupported.
from the skeptic's reading
How the review went
4 readings by deepseek-v4-flash · 13 Nov 2026
- Reader holds up
- Skeptic agrees
- Editor wrote the verdict above
- Referee major revision: 3 major objections, 8 minor
Not run on this paper: the simulated authors' defence.
Pith did not check this review's objections against the paper.
The review in full
The review in brief, machine-written
This paper does what it says: it gives the first polynomial (r−34) swap coboundary expansion for bounded-degree KMS complexes, improving the previous subexponential bounds. That is a genuine advance, and the applications to low-degree tests and PCP parameters are concrete. The main new technical idea—a decomposition lemma that separates the Dehn function analysis across blocks—is clearly explained and seems solid. The probabilistic color-sampling lemma also checks out. I’d say the core combinatorial and group-theoretic machinery is the paper’s own work and is well executed.
The soft spot is the reliance on two external results: vanishing first cohomology from [OV25] and local spectral expansion from [LO25; GV25]. These are cited as preprints (arXiv, so visible), not as fully published theorems. The paper states the parameter regimes under which they are claimed to hold and does not verify them internally. If those results have hidden parameter incompatibilities—say, a hidden bound on d versus q that clashes with the paper’s q0 = poly(r) and d = r55—then the whole chain of reductions falls. That’s a genuine load-bearing dependency. However, this is standard in a fast-moving area; the authors are honest about it. The stress-test note is correct that this is the weakest point, but it does not make the paper unserious. I’d say it’s a contingent advance: if the cited results are right, this is a clean, important step.
The paper’s own arguments (decomposition, Dehn function, color sampling) are novel and well-argued. The PCP appendix is sketchy—it’s a parameter plug-in rather than a full construction—but the main theorem does not depend on it.
Who should read this: anyone working on high-dimensional expanders, agreement tests, or PCP constructions. The paper deserves a serious referee. My recommendation: accept after the authors confirm that the required parameter range is indeed covered by the available versions of [OV25] and [LO25]. That’s a small check; the paper’s own math is solid.
The strongest objection
The proof of Theorem 1.2 crucially depends on two external results: (i) H¹(X,Λ)=1 for the KMS complex, cited from the preprint [OV25], and (ii) local spectral expansion λ₂ ≤ 2/(√q–2), cited from [LO25] (Theorem 2.20–2.21). These bounds must hold for the specific parameter regimes used: q ≥ q₀ = poly(r) (with q₀ ≥ 10⁴ in the proof) and d ≥ d₀ = r⁵⁵ (Theorem 3.1). The paper does not reproduce or verify these proofs; it only states the conditions under which they are claimed to hold. If either citation contains a hidden parameter incompatibility—for instance, if the vanishing cohomology argument in [OV25] requires d to be bounded independently of q, or if the spectral bound in [LO25] requires a larger lower bound on q for the dimension d = r⁵⁵—then the entire chain of reductions (local-to-global, colored faces, links, Dehn function) would be invalid. The paper acknowledges this indirectly by citing 'forthcoming work' and 'recent results', but no independent verification is offered. This is a genuine risk because the construction of the swap coboundary expander is entirely built on these properties; without them, the Dehn‑function and cone arguments cannot be applied. The paper's own probabilistic color‑sampling lemma and the decomposition lemma are well‑founded given the nice‑ness assumption, but the foundational spectral and cohomological inputs are not.
The reader's weakest_assumption already identified the reliance on [OV25] and [GV25; LO25] as the most fragile part outside the paper's own argument. I concure. The paper's internal estimates (color sampling, Dehn decomposition, matrix‑group presentation) are carefully parameterized and appear sound. However, the two external citations are for non‑trivial geometric group theory results; if they contain gaps or do not scale to the needed polynomial‑in‑r regime, the entire construction collapses. The concrete test I propose would settle this concern by checking the hypotheses of those preprints against the parameters used in this paper. Since the paper does not provide an independent proof, the risk is real, but it is not a fatal flaw because the cited works are by experts and the conditions stated (q large enough, d large enough) are the same as those claimed. Therefore the verdict 'ACCEPT' remains appropriate; the reader's verdict should not be changed.
The referee's report
If the central claim holds, this is a substantial quantitative improvement: earlier bounds were exp(-O(√r)), whereas the present work gives r^{-O(1)}. This polynomial strengthening directly benefits applications: the query complexity of local tests becomes exp(poly(1/ε)) instead of exp(exp(poly(1/ε))), and the proof-length overhead in the PCP construction of Bafna-Minzer-Vyas-Yun is reduced from exp(exp(poly(1/ε))) to exp(poly(1/ε)). The decomposition lemma for Dehn functions in product groups and the probabilistic color-sampling argument are clean and likely to be reusable.
Pith's reading of the paper (a machine's summary, not the authors')
This paper proves that certain skeleta of Kac–Moody–Steinberg (KMS) complexes are swap coboundary expanders with a polynomial parameter β = $r^{{-34}}$, where r is the face dimension. Previous constructions only achieved subexponential bounds. The result gives a robust local-to-global property: if a labeling on faces passes a random consistency test with probability ε, then it is close to a global assignment. This polynomial improvement is crucial for two applications: it yields efficient local tests for sparse algebraic codes even at very low acceptance probabilities, and it improves the proof length of a recent two-query PCP construction, reducing the polylogarithmic overhead from doubly exponential to singly exponential in 1/ε.
What carries the argument. The central new ingredient is a decomposition lemma for Dehn functions. The groups underlying the vertex links of the colored faces complexes decompose as direct products of smaller upper-triangular matrix groups (bins). The lemma allows one to bound the Dehn function of the full coset complex by the sum of the Dehn functions of these factors, at a polynomial overhead in r. Each factor is then shown to have a linear Dehn function using a block-matrix presentation of Unip_n(F_q) with five large blocks, whose relations come from the 'nice' arrangement of color sets guaranteed by a probabilistic sampling lemma.
Core claim. The paper establishes that for every r, there exist q₀, d₀ = poly(r) such that for all prime powers q ≥ q₀ and dimensions d ≥ d₀, the congruence KMS complex of type A_d over F_q is an (r, Ω($r^{{-34}}$), m)-swap coboundary expander for every m < char(F_q). This is the first inverse-polynomial bound for bounded-degree complexes; all prior results gave exp(-O(√r)) or weaker. The proof holds for coefficient groups Λ with no nontrivial p-torsion when q = p^m.
The premise it rests on. The proof relies on two properties—vanishing first cohomology and local spectral expansion—that are cited from previous works [OV25] and [GV25; LO25]; the paper does not verify that these properties hold for the full parameter range (q,d) required by the main theorem, and it also assumes a probabilistic color-sampling lemma (Lemma 3.7) that requires d ≥ 100(r+1)²T², which must be satisfied by the explicit parameter choices.
If the paper is right (Pith's inferences, not the authors')
The polynomial swap expansion directly improves the query complexity of the derandomized low-degree test in forthcoming work of Ben Yaacov–Dikstein–Liu from exp(exp(poly(1/ε))) to exp(poly(1/ε)).
Substituting the bound into the Bafna–Minzer–Vyas–Yun PCP construction reduces the proof length exponent from doubly exponential in 1/ε to singly exponential, giving length n(log n)^{exp(poly(1/ε))} with perfect completeness and soundness ε.
The result establishes that KMS complexes simultaneously provide strong local spectral expansion and polynomial swap coboundary expansion, making them a versatile family of high-dimensional expanders for coding and PCP applications.
The linear Dehn bound for each factor shows that the cone radius of the vertex links is polynomial in r, which directly implies the coboundary expansion via the cone method.
The polynomial expansion β = r^{-34} is unlikely to be optimal; the authors suggest a constant independent of r may be possible. Improving the exponent from -34 to a constant would further shrink the polylogarithmic overhead in PCP constructions.
The decomposition lemma for Dehn functions may apply to other coset complexes with a product structure, potentially yielding new swap expanders beyond KMS complexes.
If the probabilistic color-sampling lemma can be derandomized, one could construct explicit complexes with the same guarantees, eliminating the randomness in the construction of the witness color sets.
Check this review
Pith stored no record of this review's passes and took no fingerprint of it. Reviews made by code from 13 Nov 2026 on carry both.
How often reviews like this one are right
Reviews like this one: written by deepseek-v4-flash, where what was read was not recorded.
How often objections from reviews like this one are right: not yet measured
Reviews by people
This review was written by a machine. No person has reviewed this paper on Pith yet. A scientist listed on Pith can review it for a fee, and their review is published here whatever it concludes.
The paper
Abstract
Swap coboundary expansion, introduced independently by Bafna–Minzer and Dikstein–Dinur, is a local-to-global property that underlies agreement tests in the low-acceptance regime and recent constructions of succinct PCPs. Previous works obtained bounds of exp(−O(√r)) for the r-swap coboundary expansion of Chapman–Lubotzky complexes. We establish the first inverse-polynomial bounds for bounded-degree complexes: suitable skeleta of Kac–Moody–Steinberg (KMS) complexes have r-swap coboundary expansion at least r−O(1). Our theorem supplies a key ingredient in forthcoming work of Ben Yaacov–Dikstein–Liu, which obtains local tests for sparse algebraic codes with guarantees even at arbitrarily small acceptance probability. These tests use exp(poly(1/ε)) queries and guarantee that any word accepted with probability at least ε agrees with a codeword on an εO(1) fraction of coordinates. Separately, substituting our bound into the existing analysis of Bafna–Minzer–Vyas–Yun improves the soundness dependence of their two-query PCP construction, giving perfect completeness, soundness ε, and proof length n(logn)exp(poly(1/ε)). Our proof exploits the product structure of the groups arising in KMS complexes. The main new ingredient is a decomposition lemma for Dehn functions, which separates the analysis of group relations into independent problems on much smaller factors, with only polynomial overhead.
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. No sentence in this record was written by a model.
abstract compiled · 2026-11-13
The authors' main claim, as the classifier picked it out 1.00
“We establish the first inverse-polynomial bounds for bounded-degree complexes: suitable skeleta of Kac--Moody--Steinberg (KMS) complexes have $r$-swap coboundary expansion at least $r^{-O(1)}$.”
How the main claim is stated: asserted 1.00
What the abstract itself states, as probabilities: claims first 0.83 · states limitation 0.17 · human participants 0.01 · controlled comparison 0.06 · randomized assignment 0.02 · states quantitative result 0.98 · compares with prior results 0.97 · mentions code or data availability 0.02
The abstract, sentence by sentence
This table labels the abstract only (arXiv listing abstract v1). The number is the probability the classifier gave the label.
| Sentence | Role | The authors' own work | States the main conclusion | Strength |
|---|---|---|---|---|
| Swap coboundary expansion, introduced independently by Bafna--Minzer and Dikstein--Dinur, is a local-to-global property that underlies agreement tests in the low-acceptance regime and recent constructions of succinct PCPs. | background 1.00 | 0.04 | 0.04 | asserted 1.00 |
| Previous works obtained bounds of $\exp(-O(\sqrt{r}))$ for the $r$-swap coboundary expansion of Chapman--Lubotzky complexes. | background 0.94 | 0.03 | 0.02 | asserted 1.00 |
| We establish the first inverse-polynomial bounds for bounded-degree complexes: suitable skeleta of Kac--Moody--Steinberg (KMS) complexes have $r$-swap coboundary expansion at least $r^{-O(1)}$. | result 0.96 | 0.96 | 0.90 | asserted 1.00 |
| Our theorem supplies a key ingredient in forthcoming work of Ben Yaacov--Dikstein--Liu, which obtains local tests for sparse algebraic codes with guarantees even at arbitrarily small acceptance probability. | future work 0.60 | 0.18 | 0.06 | asserted 0.99 |
| These tests use $\exp(\operatorname{poly}(1/\varepsilon))$ queries and guarantee that any word accepted with probability at least $\varepsilon$ agrees with a codeword on an $\varepsilon^{O(1)}$ fraction of coordinates. | result 0.34 | 0.08 | 0.04 | asserted 1.00 |
| Separately, substituting our bound into the existing analysis of Bafna--Minzer--Vyas--Yun improves the soundness dependence of their two-query PCP construction, giving perfect completeness, soundness $\varepsilon$, and proof length $n(\log n)^{\exp(\operatorname{poly}(1/\varepsilon))}$. | result 0.56 | 0.79 | 0.08 | asserted 1.00 |
| Our proof exploits the product structure of the groups arising in KMS complexes. | method 0.99 | 0.83 | 0.03 | asserted 1.00 |
| The main new ingredient is a decomposition lemma for Dehn functions, which separates the analysis of group relations into independent problems on much smaller factors, with only polynomial overhead. | method 0.84 | 0.93 | 0.06 | asserted 1.00 |
What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00
What was examined, and what was not
Sources read
- arXiv listing abstract v1
Not examined
- full text
- figures and tables
- references and citing sentences
- relations to other papers
Levels run
- P abstract
Not run
- S sections
- T body sentences
- C citations
- R cross-paper relations
How the labels were made
Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-11-13: 1 request, 6,613 input tokens.
Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. This record as JSON
Figures (5)
Figures are the authors', reproduced from the paper.
References (123)
- [1] Inga. High-dimensional expanders from. 2026 , type = on Pith
- [2] From Grassmannian to Simplicial High-Dimensional Expanders , author=. arXiv preprint arXiv:2305.02512 , year= on PithPith's reviewarXiv
- [3] Gromov, M. , year =. Singularities, Expanders and Topology of Maps. Part 2: from Combinatorics to Topology Via Algebraic Isoperimetry , volume =. Geom. Funct. Anal. , doi = on Pith
- [4] Swap Cocycle Expansion , author=. 2023 , Eprint = on Pith
- [5] Yotam Dikstein and Irit Dinur , title =. CoRR , volume =. 2023 , url =. doi:10.48550/arXiv.2304.01608 , eprinttype =. 2304.01608 , timestamp = on PithPith's reviewarXivdoi:10.48550/arxiv.2304.01608
- [6] Liu, Siqi and Mohanty, Sidhanth and Schramm, Tselil and Yang, Elizabeth , title =. 2023 , isbn =. doi:10.1145/3564246.3585106 , booktitle = on Pithdoi:10.1145/3564246.3585106
- [7] Local spectral expansion approach to high dimensional expanders part I: Descent of spectral gaps , author=. Discrete & Computational Geometry , volume=. 2018 , publisher= on Pith
- [8] The smallest eigenvalues of Hamming graphs, Johnson graphs and other distance-regular graphs with classical parameters , author=. Journal of Combinatorial Theory, Series B , volume=. 2018 , publisher= on Pith
- [9] Association schemes and coding theory , author=. IEEE Transactions on Information Theory , volume=. 1998 , publisher= on Pith
- [10] Boolean functions on high-dimensional expanders , author=. arXiv preprint arXiv:1804.08155 , year= on PithPith's reviewarXiv
- [11] Yotam Dikstein and Irit Dinur , title =. Proceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science , year = on Pith
- [12] Spectrum of Johnson graphs , author=. Discrete Mathematics , volume=. 2023 , publisher= on Pith
- [13] Howard Garland , journal =. p -Adic Curvature and the Cohomology of Discrete Subgroups of p -Adic Groups , volume = 97, year = 1973, doi = on Pith
- [14] Expansion of building-like complexes , author=. Groups, Geometry, and Dynamics , volume= on Pith
- [15] Quantitative aspects of acyclicity , author=. Research in the Mathematical Sciences , volume=. 2019 , publisher= on Pith
- [16] Tali Kaufman and Izhar Oppenheim , title =. 48th International Colloquium on Automata, Languages, and Programming,. 2021 , url =. doi:10.4230/LIPIcs.ICALP.2021.84 , bibsource = on Pithdoi:10.4230/lipics.icalp.2021.84
- [17] Tali Kaufman and David Mass , note =. Good Distance Lattices from High Dimensional Expanders , year = 2018, eprint = on Pith
- [18] On some lemmas in the theory of groups , author=. American Journal of Mathematics , volume=. 1933 , publisher= on Pith
- [19] Combinatorial group theory , author=. 1977 , publisher= on Pith
- [20] Alev, Vedat and Jeronimo, Fernando and Tulsiani, Madhur , year =. Proc. 59th IEEE Symp. on Foundations of Computer Science , title = on Pith
show 80 more
- [21] Tali Kaufman and Alexander Lubotzky , title =. Innovations in Theoretical Computer Science, ITCS'14, Princeton, NJ, USA, January 12-14, 2014 , pages = on Pith
- [22] Dinur, Irit and Meshulam, Roy , title=. Archiv der Mathematik , year=. doi:10.1007/s00013-022-01720-6 , url= on Pithdoi:10.1007/s00013-022-01720-6
- [23] Roy Gotlib and Tali Kaufman , Title =. 2022 , Eprint = on Pith
- [24] Yotam Dikstein and Irit Dinur , title =. CoRR , volume =. 2023 , url =. doi:10.48550/ARXIV.2308.09582 , eprinttype =. 2308.09582 , timestamp = on PithPith's reviewarXivdoi:10.48550/arxiv.2308.09582
- [25] Mitali Bafna and Dor Minzer , title = on Pith
- [26] Michael Chapman and Alexander Lubotzky , Title =. 2023 , Eprint = on Pith
- [27] Surowski, David , year =. Covers of simplicial complexes and applications to geometry , volume =. Geometriae Dedicata , doi = on Pith
- [28] Garland's Technique for Posets and High Dimensional Grassmannian Expanders , author=. arXiv preprint arXiv:2101.12621 , year= on PithPith's reviewarXiv
- [29] Homological connectivity of random 2-complexes , author=. Combinatorica , volume=. 2006 , publisher= on Pith
- [30] The number of triangles covering the center of an n-set , author=. Geometriae Dedicata , volume=. 1984 , publisher= on Pith
- [31] B. A generalization of Carath. Discrete Mathematics , volume=. 1982 , publisher= on Pith
- [32] Isoperimetric inequalities for Ramanujan complexes and topological expanders , author=. Geometric and Functional Analysis , volume=. 2016 , publisher= on Pith
- [33] Bounded degree cosystolic expanders of every dimension , author=. Proceedings of the forty-eighth annual ACM symposium on Theory of Computing , pages= on Pith
- [34] Explicit constructions of Ramanujan complexes of type Ad , author=. European Journal of Combinatorics , volume=. 2005 , publisher= on Pith
- [35] Homological connectivity of random k-dimensional complexes , author=. Random Structures & Algorithms , volume=. 2009 , publisher= on Pith
- [36] High dimensional expanders imply agreement expanders , author=. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2017 , organization= on Pith
- [37] On eigenvalues of random complexes , author=. Israel Journal of Mathematics , volume=. 2016 , publisher= on Pith
- [38] Ryan O'Donnell and Kevin Pratt , editor =. High-Dimensional Expanders from Chevalley Groups , booktitle =. 2022 , url =. doi:10.4230/LIPIcs.CCC.2022.18 , timestamp = on Pithdoi:10.4230/lipics.ccc.2022.18
- [39] New High Dimensional Expanders from Covers , author=. Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages= on Pith
- [40] Construction of new local spectral high dimensional expanders , author=. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , pages= on Pith
- [41] Hypergraph expanders of all uniformities from Cayley graphs , author=. Proceedings of the London Mathematical Society , volume=. 2020 , publisher= on Pith
- [42] Hypergraph expanders from Cayley graphs , author=. Israel Journal of Mathematics , volume=. 2019 , publisher= on Pith
- [43] Irit Dinur and Yuval Filmus and Prahladh Harsha and Madhur Tulsiani , title =. 12th Innovations in Theoretical Computer Science (ITCS 2021) , year= on Pith
- [44] Explicit Lower Bounds Against Omega (n)-Rounds of Sum-of-Squares , author=. arXiv preprint arXiv:2204.11469 , year= on PithPith's reviewarXiv
- [45] Overlap properties of geometric expanders , author=. Journal f. 2012 , publisher= on Pith
- [46] Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid , author=. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages= on Pith
- [47] Entropic independence I: Modified log-Sobolev inequalities for fractionally log-concave distributions and high-temperature ising models , author=. arXiv preprint arXiv:2106.04105 , year= on PithPith's reviewarXiv
- [48] Mitali Bafna and Noam Lifshitz and Dor Minzer , Title =. 2024 , Eprint = on Pith
- [49] Yotam Dikstein and Irit Dinur and Alexander Lubotzky , Title =. 2024 , url = on Pith
- [50] High dimensional random walks and colorful expansion , author=. 8th Innovations in Theoretical Computer Science Conference (ITCS 2017) , year= on Pith
- [51] Improved analysis of higher order random walks and applications , author=. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages= on Pith
- [52] Hypercontractivity on high dimensional expanders , author=. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages= on Pith
- [53] Evra, Shai , title =. Journal of Topology and Analysis , volume =. 2017 , doi = on Pith
- [54] Chapman, Michael and Linial, Nathan and Peled Yuval , year =. Expander Graphs — Both Local and Global , volume =. Combinatorica , doi = on Pith
- [55] Siqi Liu and Sidhanth Mohanty and Elizabeth Yang , title =. 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) , year = on Pith
- [56] Golowich, Louis , title =. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021) , year = on Pith
- [57] List-decoding with double samplers , author=. SIAM journal on computing , volume=. 2021 , publisher= on Pith
- [58] High-probability list-recovery, and applications to heavy hitters , author=. Leibniz international proceedings in informatics , year= on Pith
- [59] Ramanujan type buildings , author=. Canadian Journal of Mathematics , volume=. 2000 , publisher= on Pith
- [60] Ramanujan geometries of type An , author=. Discrete mathematics , volume=. 2003 , publisher= on Pith
- [61] Ramanujan hypergraphs , author=. Geometric & Functional Analysis GAFA , volume=. 2004 , publisher= on Pith
- [62] Expander graphs and their applications , author=. Bulletin of the American Mathematical Society , volume= on Pith
- [63] Expander graphs in pure and applied mathematics , author=. Bulletin of the American Mathematical Society , volume= on Pith
- [64] Explicit constructions of linear-sized superconcentrators , author=. Journal of Computer and System Sciences , volume=. 1981 , publisher= on Pith
- [65] Explicit constructions of concentrators , author=. Problemy Peredachi Informatsii , volume=. 1973 , publisher= on Pith
- [66] Constructing expander graphs by 2-lifts and discrepancy vs. spectral gap , author=. 45th Annual IEEE Symposium on Foundations of Computer Science , pages=. 2004 , organization= on Pith
- [67] Ramanujan graphs , author=. Combinatorica , volume= on Pith
- [68] Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors , author=. Proceedings 41st Annual Symposium on Foundations of Computer Science , pages=. 2000 , organization= on Pith
- [69] Marcus, Adam W. and Spielman, Daniel A. and Srivastava, Nikhil , year =. Interlacing families I: Bipartite Ramanujan graphs of all degrees , volume =. Annals of Mathematics , doi = on Pith
- [70] The PCP theorem by gap amplification , author=. Journal of the ACM (JACM) , volume=. 2007 , publisher= on Pith
- [71] Reingold, Omer , title =. 2008 , issue_date =. doi:10.1145/1391289.1391291 , journal = on Pithdoi:10.1145/1391289.1391291
- [72] Explicit, almost optimal, epsilon-balanced codes , author=. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pages= on Pith
- [73] Good Locally Testable Codes , author=. arXiv preprint arXiv:2207.11929 , year= on PithPith's reviewarXiv
- [74] Pavel Panteleev and Gleb Kalachev , editor =. Asymptotically good Quantum and locally testable classical. 2022 , url =. doi:10.1145/3519935.3520017 , timestamp = on Pithdoi:10.1145/3519935.3520017
- [75] NLTS Hamiltonians from good quantum codes , author=. Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages= on Pith
- [76] Eigenstripping, Spectral Decay, and Edge-Expansion on Posets , author=. arXiv preprint arXiv:2205.00644 , year= on PithPith's reviewarXiv
- [77] COBOUNDARY EXPANDERS , author=. Journal of Topology and Analysis , volume=. 2012 , publisher= on Pith
- [78] The threshold for integer homology in random d-complexes , author=. Discrete & Computational Geometry , volume=. 2017 , publisher= on Pith
- [79] Rubinfeld, Ronitt and Sudan, Madhu , title =. SIAM Journal on Computing , volume =. 1996 , doi = on Pith
- [80] Goldreich, Oded and Safra, Shmuel , title =. RANDOM: International Workshop on Randomization and Approximation Techniques in Computer Science , publisher = on Pith
- [81] Raz, Ran and Safra, Shmuel , title =. Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing , series =. 1997 , isbn =. doi:10.1145/258533.258641 , acmid = on Pithdoi:10.1145/258533.258641
- [82] Dinur, Irit and Reingold, Omer. Assignment Testers: Towards combinatorial proofs of the PCP theorem. SIAM Journal on Computing. 2006 on Pith
- [83] I. Dinur and D. Steurer , booktitle=. Direct Product Testing , year= on Pith
- [84] Irit Dinur and Elazar Goldenberg. Locally testing direct products in the low error range. Proc. 49th IEEE Symp. on Foundations of Computer Science on Pith
- [85] Russell Impagliazzo and Valentine Kabanets and Avi Wigderson , title =. SIAM J. Comput. , volume =. 2012 , pages = on Pith
- [86] Irit Dinur and Inbal. Exponentially Small Soundness for the Direct Product Z-Test , booktitle = on Pith
- [87] Ran Raz. A Parallel Repetition Theorem. SIAM Journal on Computing. 1998 on Pith
- [88] On expansion and topological overlap , author=. Geometriae Dedicata , volume=. 2018 , publisher= on Pith
- [89] Topology of random clique complexes , author=. Discrete mathematics , volume=. 2009 , publisher= on Pith
- [90] Random geometric complexes , author=. Discrete & Computational Geometry , volume=. 2011 , publisher= on Pith
- [91] Random simplicial complexes , author=. arXiv preprint arXiv:1607.07069 , year= on PithPith's reviewarXiv
- [92] Interlacing families ii: Mixed characteristic polynomials and the kadison—singer problem , author=. Annals of Mathematics , pages=. 2015 , publisher= on Pith
- [93] On the complexity of a concentrator , author=. 7th International Telegraffic Conference , volume= on Pith
- [94] Markov chain decomposition for convergence rate analysis , author=. Annals of Applied Probability , pages=. 2002 , publisher= on Pith
- [95] Kolla, Alexandra. Spectral algorithms for unique games. Comput. Complex on Pith
- [96] New cosystolic high-dimensional expanders from. Mathematische Annalen , author =. 2026 , pages =. doi:10.1007/s00208-026-03570-x , number = on Pithdoi:10.1007/s00208-026-03570-x
- [97] A note on the elementary construction of high-dimensional expanders of Kaufman and Oppenheim , author=. arXiv preprint arXiv:1912.11225 , year= on PithPith's reviewarXiv
- [98] Abramenko, Peter , TITLE =. 1996 , PAGES =. doi:10.1007/BFb0094079 , URL = on Pithdoi:10.1007/bfb0094079
- [99] Abramenko, P. and Brown, K. S. , TITLE =. 2008 , PAGES =. doi:10.1007/978-0-387-78835-7 , URL = on Pithdoi:10.1007/978-0-387-78835-7
- [100] Higher generation by subgroups , volume =. Journal of Algebra , author =. 1993 , mrnumber =. doi:10.1006/jabr.1993.1190 , number = on Pithdoi:10.1006/jabr.1993.1190
The first 100 of 123 references are listed here. All of them are in this paper's citation record.
Challenges and discussion
Disagree with the review, or know something it missed? Leave a comment, or challenge this review formally: a challenge becomes a permanent entry in this paper's record, and its decision is published here.
Come back by email
A short list of the week's newly reviewed papers. Nothing is sent until you confirm from your inbox, and every email has a link that stops it. No account.
No comments yet.
Sign in to comment