REVIEW 3 major objections 4 minor 16 references
The paper pins down the exact two-symbol service rate region for Reed-Muller codes, and proves the full rate region for RM(r,r+1) is a simplex.
Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →
T0 review · deepseek-v4-flash
2026-08-05 00:18 UTC pith:UOLBFHL6
load-bearing objection Solid new result for RM(r,r+1), but the two-symbol projection theorem has a counting error that sinks the main claim. the 3 major comments →
New Results Towards the Characterization of Service Rate Region of Reed-Muller Codes
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
At the center of the paper is the claim that two-symbol projections of the SRR are no longer approximate. For RM(r,m), fix message symbols s_i and s_j of orders ℓ1 < ℓ2. The paper derives two upper bounds on (λ_i, λ_j): a linear bound λ_i + λ_j ≤ 1 + (2^m − 2^{ℓ2})/(2^{r+1} − 2^{ℓ2}), and a capacity bound (2^{r+1} − 2^{ℓ1})λ_i + (2^{r+1} − 2^{ℓ2})λ_j ≤ 2^m + 2^{r+1} − 2^{ℓ1+1}. Theorem 4 asserts these bounds are tight, so the two-symbol SRR is conv{0, λ_i^max e_i, λ_j^max e_j, u_{i,j}} with u_{i,j} = 2e_i + ((2^m − 2^{r+1})/(2^{r+1} − 2^{ℓ2}))e_j. Achievability is by explicit allocation over recovery sets: rate 2 on the lower-order symbol is obtained by pairing its large recovery sets with t
What carries the argument
The machinery is the recovery-set structure of Reed-Muller codes. A minimal recovery set of a message symbol is a minimal set of servers whose stored columns span that symbol. For a symbol of order ℓ there is a unique recovery set of size 2^ℓ, and every other minimal recovery set has size at least 2^{r+1} − 2^ℓ. The paper classifies how these recovery sets intersect (nested versus partially overlapping, according to whether the monomial's variable set is contained in the other), converts the resulting covering constraints into dual linear programs over server weights to obtain upper bounds, and constructs rate allocations along common (r+1)-dimensional subspaces to show that the bounds are a
Load-bearing premise
The achievability proof of the two-symbol vertex assumes that for any two symbols whose monomials do not nest, the number of large recovery sets of the lower-order symbol that contain the higher-order symbol's special recovery set minus the first server is exactly the Gaussian binomial count [m−ℓ2 choose r+1−ℓ2]_2, with each such set paired one-to-one with a recovery set of the higher-order symbol; if that count is wrong, the claimed vertex may not be achievable.
What would settle it
Fix RM(2,4) and the two symbols v2 (order 1) and v3v4 (order 2). Enumerate all six-server recovery sets of v2 that contain the three servers {2,3,4} (the order-2 symbol's unique recovery set minus server 1). Theorem 4 requires exactly 3 such sets, each sharing a common four-dimensional subspace with a recovery set of v3v4. Any count other than 3, or a set that fails the subspace pairing, disproves the claimed two-symbol vertex u_{i,j} and hence the projection characterization.
If this is right
- For RM(r,r+1), the entire service rate region is exactly the simplex {λ ≥ 0 : Σ λ_i ≤ 2}; no other inequality constrains service, and total demand exceeding 2 is impossible.
- For any two symbols of different orders in any RM(r,m), the achievable rate-pair region is fully described by four vertices, so the pair-level bounds in Theorems 2 and 3 leave no gap.
- The convex hull B, built by adding the new pair vertices to the per-symbol vertices, is an inscribed polytope lying strictly between the earlier maximal inner simplex and minimal outer simplex, giving a tighter feasible approximation of the full SRR.
- For RM(2,4), the total achievable demand bound improves from 4.75 to 13/3, with an explicit allocation that saturates most servers.
- The one-to-one pairing between recovery sets of different-order symbols used to achieve rate 2 gives a general template for serving a lower-order symbol at double its typical rate while still serving a higher-order symbol.
Where Pith is reading between the lines
- If the two-symbol projection theorem holds, a natural completion the paper leaves implicit is that the full SRR is cut out by all such pairwise inequalities together with the per-order and total bounds from Lemma 2; this would identify the missing facets of the polytope.
- The construction behind the new vertex lets the lower-order symbol borrow the higher-order symbol's recovery-set structure; a similar borrowing might push total-rate bounds below the earlier aggregate bound for other RM(r,m) parameters, not just RM(2,4).
- For pairs whose monomials partially overlap, the proof's Gaussian-binomial count is the delicate point: if a correction is needed, the same framework would likely still work with a modified fourth vertex, so the quadrilateral shape of the projection may survive.
- The explicit RM(2,4) allocation suggests a testable pattern: the new vertices correspond to pairings of recovery sets that share a common subspace, so searching for analogous subspace pairings among larger groups of symbols could yield achievable polytopes beyond B.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the service rate region (SRR) of binary Reed-Muller codes. It first proves that for RM(r, r+1) with r ≥ 2 the SRR is exactly the simplex {λ ∈ R_{\ge 0}^k : Σ_i λ_i ≤ 2}. It then proposes, for general RM(r, m), upper bounds on the sum of demands of any two message symbols of different orders (Theorems 2 and 3), and claims in Theorem 4 that these bounds are tight, so that every two-dimensional projection of the SRR is conv{0, λ_max_i e_i, λ_max_j e_j, u_{i,j}}. From this it defines an inscribed polytope B approximating the SRR, and reports a new total-rate bound for RM(2,4).
Significance. If Theorem 4 were correct, the paper would give a substantial refinement of the partial results of Ly, Soljanin, and Lalitha: exact two-dimensional projections of the SRR for all RM(r, m) and a strictly larger inner polytope than the earlier maximal achievable simplex. The proof of Theorem 1 is a clean LP-duality argument and appears sound; Example 3 also gives a concrete allocation for a special case. However, the central achievability construction in Theorem 4 rests on a false cardinality claim, so the main new characterization is not established. The paper does contain useful ideas and explicit allocations, but the central claim needs major reworking.
major comments (3)
- [Section III-B, Theorem 2 Case 2] The definition of R*_{i,j} and its cardinality are incorrect. Every R ∈ R*_i has the form V' \ R_{i,1} for an (r+1)-dimensional subspace V' containing R_{i,1}; hence R is disjoint from R_{i,1}. For R to contain R_{j,1}\{1}, the set R_{j,1}\{1} must be disjoint from R_{i,1}. By Corollary 1, if T_i ∩ T_j ≠ ∅ and ℓ1 ≥ 1, then R_{j,1}\{1} contains points of R_{i,1}, so R*_{i,j} is empty. Even when T_i ∩ T_j = ∅, the number of (r+1)-subspaces containing both R_{i,1} and R_{j,1} is [m-(ℓ1+ℓ2) choose r+1-(ℓ1+ℓ2)]_2, not [m-ℓ2 choose r+1-ℓ2]_2. Thus the claimed one-to-one correspondence with R*_j and the allocation achieving λ_i^* = 2 are unsupported. Since u_{i,j} is the new vertex in the claimed 2D projection, this is load-bearing.
- [Section III-B, Theorem 2 Case 2] The dual feasible solution for the case T_i ⊈ T_j is asserted without verification: the text says 'Similar as the previous case, it can be verified... Due to space limitations the details are omitted.' This is not acceptable for a central upper bound. The verification is nontrivial because one must check that the weight assignment, which places positive weight only on server 1, on N, and outside R_{j,1}, satisfies the constraints for all recovery sets of both symbols. The omitted details may be fillable, but they are not supplied.
- [Section III-B, Theorem 4] The proof claims that combining (2) and (3) yields the upper bound with vertex u_{i,j}. Even if the inequalities are valid, the paper does not explicitly verify that the intersection of the half-planes defined by (2), (3), the individual upper bounds λ_i ≤ λ_max_i, λ_j ≤ λ_max_j, and nonnegativity is exactly the convex hull of the four stated vertices. This is a routine but necessary step for a complete characterization of the projection.
minor comments (4)
- [Section III, Example 2] Example 2 is inconsistent with the generator matrix ordering of Example 1. For s2 = v4, the unique recovery set of size 2 containing server 1 is {1,9}, not {1,2}; for s6 = v3v4, the corresponding set is {1,5,9,13}. The example should be recomputed under the stated column ordering.
- [Section II, Lemma 1 / Corollary 1] Corollary 1 is stated as being 'inferred from the proofs in [14]' without a proof or precise statement in [14]. Since Theorem 4 relies on the geometric structure of R_{i,1} and R_{j,1}, the corollary should either be proved directly or cited with a precise reference to the extended version [16].
- [Section III, Remark 2] Remark 2 states a new upper bound Σ_{j=1}^{11} λ_j ≤ 13/3 for RM(2,4), but only gives an allocation achieving equality. An upper bound requires a proof (e.g., a dual feasible solution or a sum of valid inequalities); as written, the remark establishes achievability, not an upper bound.
- [Section III-B, Theorem 3] The proof of Theorem 3 uses the claim that any recovery set other than R_{i,1} contains at least 2^{r+1} - 2^{ℓ1} servers outside R_{i,1}. This is stated in the proof of Theorem 2 as a consequence of Lemma 1, but Lemma 1 itself is not phrased in terms of 'outside R_{i,1}'. A short justification would improve clarity.
Circularity Check
No circularity detected: the derivation relies on external prior-work lemmas and LP duality, not on its own conclusions.
full rationale
The paper's derivation chain is not circular. Theorem 1 uses Lemma 1 from [14] plus LP duality: the upper bound comes from an explicit dual feasible solution, and achievability is by explicit allocations to the two recovery sets of each symbol. Theorems 2 and 3 derive upper bounds from recovery-set size facts borrowed from [14] and a capacity argument; Theorem 4 builds an explicit rate allocation from the recovery-set counts stated in Lemma 1. The paper does borrow Corollary 1 as "inferred from the proofs in [14]", but that is external prior work by different authors, not self-citation, and it is not equivalent to the target SRR statement. The main vulnerability is the unproved geometric claim about the cardinality and correspondence of the family R*_{i,j} in the proof of Theorem 4; if that claim fails, the achievability proof is incomplete, but that is a soundness or missing-proof issue, not circularity. No fitted parameters are renamed as predictions, and no conclusion is assumed as an input.
Axiom & Free-Parameter Ledger
axioms (4)
- domain assumption Recovery set structure of RM codes as stated in Lemma 1 (from [14])
- domain assumption Corollary 1: intersection sizes of unique smallest recovery sets for symbols with related index sets
- ad hoc to paper Recovery sets of size 2^{r+1}-2^l are complements of the smallest recovery set in (r+1)-dimensional subspaces, and the one-to-one correspondence in Theorem 4
- standard math Strong duality of linear programming
Cite this review
Pith. "Pith review of New Results Towards the Characterization of Service Rate Region of Reed-Muller Codes." pith.science (2026). https://pith.science/paper/UOLBFHL6
@misc{pith2026260800810,
author = {Pith},
title = {Pith review of: New Results Towards the Characterization of Service Rate Region of Reed-Muller Codes},
year = {2026},
howpublished = {\url{https://pith.science/paper/UOLBFHL6}},
note = {Machine review of arXiv:2608.00810}
}
read the original abstract
The Service Rate Region (SRR) serves as a critical metric for evaluating the concurrent service capacity of distributed storage systems. While several works have characterized the SRR for MDS codes and first order Reed-Muller codes, for high-order Reed-Muller codes the problem becomes way more complicated and only partial results were given by Ly, Soljanin, and Lalitha [IEEE ISIT 2025]. In this paper, we refine the SRR analysis by explicitly characterizing the intersection patterns of recovery sets for high-order Reed-Muller codes, deriving the exact region for the case m=r+1 and providing new types of strictly tighter constraints to bridge the gap between existing approximations and the exact SRR polytope.
Reference graph
Works this paper leans on
-
[1]
Service Rate Region: A New Aspect of Coded Distributed System Design,
M. Aktas ¸, G. Joshi, S. Kadhe, F. Kazemi, and E. Sol- janin, “Service Rate Region: A New Aspect of Coded Distributed System Design,”IEEE Transactions on In- formation Theory, vol. 67, no. 12, pp. 7940–7963, 2021
work page 2021
-
[2]
Service Rate Regions of MDS Codes and Fractional Matchings in Quasi-Uniform Hy- pergraphs,
H. Ly and E. Soljanin, “Service Rate Regions of MDS Codes and Fractional Matchings in Quasi-Uniform Hy- pergraphs,”IEEE Transactions on Information Theory, 2026
work page 2026
-
[3]
The Service Rate Region of Hamming Codes,
P. Choudhary and M. Bhaintwal, “The Service Rate Region of Hamming Codes,”arXiv preprint arXiv:2509.22898, 2025
-
[4]
F. Kazemi, S. Kurz, and E. Soljanin, “A Geometric View of the Service Rates of Codes Problem and its Application to the Service Rate of the First Order Reed- Muller Codes,” in2020 IEEE International Symposium on Information Theory (ISIT). IEEE, 2020, pp. 66–71
work page 2020
-
[5]
Maximal Achievable Service Rates of Codes and Connections to Combinatorial De- signs,
H. Ly and E. Soljanin, “Maximal Achievable Service Rates of Codes and Connections to Combinatorial De- signs,”arXiv preprint arXiv:2506.16983, 2025
arXiv 2025
-
[6]
Large matchings in uniform hypergraphs and the conjectures of Erd ˝os and Samuels,
N. Alon, P. Frankl, H. Huang, V . R ¨odl, A. Ruci ´nski, and B. Sudakov, “Large matchings in uniform hypergraphs and the conjectures of Erd ˝os and Samuels,”Journal of Combinatorial Theory, Series A, vol. 119, no. 6, pp. 1200–1215, 2012
work page 2012
-
[7]
Application of Boolean algebra to switch- ing circuit design and to error detection,
D. E. Muller, “Application of Boolean algebra to switch- ing circuit design and to error detection,”Transactions of the IRE professional group on electronic computers, no. 3, pp. 6–12, 1954
work page 1954
-
[8]
A class of multiple-error-correcting codes and the decoding scheme,
I. Reed, “A class of multiple-error-correcting codes and the decoding scheme,”Transactions of the IRE Profes- sional Group on Information Theory, vol. 4, no. 4, pp. 38–49, 1954
work page 1954
-
[9]
Reed–Muller Codes Achieve Capacity on Erasure Channels,
S. Kudekar, S. Kumar, M. Mondelli, H. D. Pfister, E. S ¸as ¸oˇglu, and R. L. Urbanke, “Reed–Muller Codes Achieve Capacity on Erasure Channels,”IEEE Transac- tions on Information Theory, vol. 63, no. 7, pp. 4298– 4316, 2017
work page 2017
-
[10]
G. Reeves and H. D. Pfister, “Reed–Muller Codes on BMS Channels Achieve Vanishing Bit-Error Probability for All Rates Below Capacity,”IEEE Transactions on Information Theory, vol. 70, no. 2, pp. 920–949, 2023
work page 2023
-
[11]
A proof that Reed-Muller codes achieve Shannon capacity on symmetric channels,
E. Abbe and C. Sandon, “A proof that Reed-Muller codes achieve Shannon capacity on symmetric channels,” pp. 177–193, 2023
work page 2023
-
[12]
R. Calderbank, S. Howard, and S. Jafarpour, “Construc- tion of a Large Class of Deterministic Sensing Matrices That Satisfy a Statistical Isometry Property,”IEEE jour- nal of selected topics in signal processing, vol. 4, no. 2, pp. 358–374, 2010
work page 2010
-
[13]
General con- structions for information-theoretic private information retrieval,
A. Beimel, Y . Ishai, and E. Kushilevitz, “General con- structions for information-theoretic private information retrieval,”Journal of Computer and System Sciences, vol. 71, no. 2, pp. 213–247, 2005
work page 2005
-
[14]
On the Service Rate Region of Reed-Muller Codes,
H. Ly, E. Soljanin, and V . Lalitha, “On the Service Rate Region of Reed-Muller Codes,” in2025 IEEE International Symposium on Information Theory (ISIT), 2025
work page 2025
-
[15]
F. J. MacWilliams and N. J. A. Sloane,The theory of error-correcting codes. Elsevier, 1977, vol. 16
work page 1977
-
[16]
On the Service Rate Region of Reed-Muller Codes,
H. Ly, E. Soljanin, and V . Lalitha, “On the Service Rate Region of Reed-Muller Codes,” 2026. [Online]. Available: https://arxiv.org/abs/2501.13105
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.