{"id":"d62e427b-17d0-4cd1-b9fe-4aab881b7057","arxiv_id":"1908.07215","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"The authors adapt the Kim-Kopparty decoding algorithm to any downset code, yielding a deterministic polynomial-time unique decoder over a product grid.","lead":"This paper extends a recent deterministic decoding algorithm from bounded-degree polynomials to the larger family of downset codes over finite grids. The result gives a general decoding method for many natural polynomial-based code families in one clean framework.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the cited weighted-distance lemma is easily verified and the induction proof is internally sound.","rationale":"The reader accepted the paper with high confidence and low correctness risk, flagging Lemma 4 as the weakest assumption. I stress-tested exactly that point and found it is not an actual risk: the lemma is an elementary pointwise calculation rather than a deep external fact, and the citation to KK17 is appropriate. I also checked the induction in Theorem 5. At each recursive step, the algorithm's δ_i and σ_x are constructed so that inequality (1) holds in all cases, including the boundary case δ_i=1 where the unique-decoding guarantee of WeightedRSDecoder is used correctly. The key bound Δ(f_i,P_i)<μ(~S,D_{d-i})/2 follows from Lemma 3 Item 2 exactly as stated. The argument does not require any unstated generic-code assumption beyond what KK17 already uses. The minor pseudocode typo in Algorithm line 9 is not part of the proof, and the real-weight model is inherited from the cited framework. I therefore see no reason to adjust the ACCEPT verdict.","tokens_in":7158,"tokens_out":14744,"duration_ms":157766,"concrete_test":"Verify Lemma 4 directly by checking the three pointwise cases for the weighted-distance definition; if the inequality holds for every u∈[0,1], the recursive proof's reliance on it is secure. As an independent check, re-derive inequality (1) with the tie case δ_i(x)=1 spelled out: the decisive point is that a decoder success at distance < μ/2 would have returned C_{i,x} instead of G_x, contradicting δ_i(x)=1.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After reading the proof of Theorem 5, I find no load-bearing concern. The only non-proved ingredient is Lemma 4, cited to [KK17, Lemma 2.1], but this lemma is immediate for the paper's weighted distance: at each grid point, if G(x)=H(x) the two weighted contributions sum to at least 0, and if G(x)≠H(x) the contributions sum to at least 1 because either f matches one of them, giving u/2+(1-u/2)=1, or f matches neither, giving 2-u≥1. Summing gives Δ(w,G)+Δ(w,H) ≥ Δ(G,H) ≥ μ(S,D). The recursive proof of Theorem 5 then goes through: inequality (1) is valid in all three cases, including the boundary case δ_i(x)=1, where unique decoding by WeightedRSDecoder forces Δ(w_{i,x},C_{i,x}) ≥ μ(S_m,{0,...,d-i})/2. The downset slicing in Lemma 3 supplies exactly the factor needed for the induction step. The only textual slips are the pseudocode in Algorithm line 9, which should refer to w_i(x,y) rather than w(x,y), and the real-valued [0,1] weights inherited from the KK framework; neither affects the mathematical claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies unique decoding of downset codes over product grids. A downset code C(S,D) is the evaluation code of polynomials whose monomial support lies in a downset D. The main result (Theorem 5) is a deterministic polynomial-time algorithm, adapted from Kim and Kopparty, that given any weighted received word and a downset D finds the unique codeword at weighted distance < mu(S,D)/2, if it exists; if none exists, it outputs an arbitrary polynomial. The proof uses the Schwartz-Zippel lemma for downset codes (via Macaulay's theorem), a slicing lemma on the largest degree in the last variable, and induction on m with Forney's generalized-minimum-distance decoding for the m=1 base. The core inequality (1) is established by a case analysis, and the induction step uses Lemma 3 to bound mu(~S,D_{d-i}).","tokens_in":7418,"tokens_out":6666,"duration_ms":62988,"significance":"If the result holds, it provides a clean generalization of the Kim-Kopparty decoder to a natural and fairly general family of polynomial codes, subsuming total-degree, individual-degree, and multilinear cases. The paper is clearly written and the proof is rigorous; the external dependencies are standard and correctly cited. The main theorem gives an explicit algorithmic guarantee, and the manuscript does not rely on fitted parameters or circular reasoning. The main limitation is the reliance on the cited weighted-distance triangle inequality (Lemma 4), but this lemma is true and easy to verify in the specialized setting.","major_comments":[],"minor_comments":[{"comment":"The pseudocode defines w_{i,x}(y) = w(x,y), but the proof and the preceding line require w_{i,x}(y) = w_i(x,y); additionally, the codomain should be F x [0,1] rather than F, since the decoder receives a weighted word. Please correct this so the pseudocode is self-contained and type-correct.","section":"Algorithm 1, line 9"},{"comment":"The phrase 'weighted codeword' should be 'weighted received word', since w is not a codeword but the received word that is input to the decoder.","section":"Theorem 5 and Section 2"},{"comment":"Since this inequality is load-bearing for both the case analysis and the induction, please include the short pointwise proof or state it as a specialized corollary of [KK17, Lemma 2.1] with a few lines of argument; the current one-sentence reference is correct but less self-contained than the rest of the paper.","section":"Lemma 4"},{"comment":"The comment 'finite grid in Fn' should be 'finite grid in F^m'; the grid is a product of m subsets of F.","section":"Algorithm 1, input comment"},{"comment":"The notation Delta(f_i(x), P_i(x)) overloads Delta for a pointwise quantity; consider denoting this quantity by d_x to avoid confusion with the global distance Delta(f_i, P_i).","section":"Display before Inequality (1)"}],"recommendation":"minor_revision","confidential_remarks":"This is a solid contribution. The only reason I am not recommending an outright accept is the typographical slip in the pseudocode in Algorithm 1 line 9; once that is fixed and the short proof of Lemma 4 is added for self-containedness, the paper is publishable as is."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the paper gives a deterministic polynomial-time algorithm for unique decoding of downset codes over product grids, generalizing Kim-Kopparty. It is a real generalization, not a repackaging: the downset family encompasses total-degree, individual-degree, weighted-degree, and sparse-support constraints, and the recursive proof is genuinely new.\n\nThe paper does several things well. It formulates the code family cleanly, proves a downset version of the Schwartz-Zippel minimum-distance bound via Macaulay's theorem, and then shows the KK weighted-decoding recursion works in this generality. The induction on m is natural and the key inequality (1) holds case by case. I checked the one non-proved ingredient, Lemma 4, cited to KK17; it is immediate from the definition of weighted distance: at each grid point the two contributions sum to at least 1 when the two codewords disagree, and at least 0 otherwise, so the triangle inequality is just the Hamming distance. The stress-test note gets this right.\n\nSoft spots, all minor. The pseudocode in Algorithm 1, line 9, says w(x,y) when it should be w_i(x,y); the surrounding prose makes the intent clear. The algorithm inherits real-valued weights in [0,1], which is a bit odd for an algorithmic paper but makes no difference to the claims. Lemma 4 is stated without proof; given how short the argument is, it would have been kinder to include it. The paper is not groundbreaking — it generalizes a known framework rather than inventing a new one — but it is a solid, correct extension with honest attribution to KK17, Forney, and Reed.\n\nThe citation pattern is fine; the main dependencies are standard and correctly cited. No circularity. The mathematical claims hold up.\n\nWho is this for? People working on algebraic decoding, especially Reed-Muller and related polynomial codes. It is a good, citable result for that subfield. It deserves a serious referee; I would send it out rather than desk-reject. I would probably cite it if I were writing about decoding polynomial codes.","headline":"A clean, correct generalization of the Kim-Kopparty decoder to downset codes; the one cited-but-unproved lemma is elementary, and the paper deserves a serious referee.","tokens_in":7867,"tokens_out":2127,"would_cite":true,"duration_ms":18824,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94B35","68W30"],"pacs":[],"model":"deepseek-v4-flash","headline":"A deterministic polynomial-time algorithm decodes every downset code over a finite grid up to half its minimum distance.","keywords":["downset codes","unique decoding","Reed-Muller codes","product sets","weighted distance","Schwartz-Zippel lemma","monomial enumeration theorem","polynomial code decoding"],"falsifier":"Search over a small instance, such as $S=\\{0,1\\}^2$ with the downset $D=\\{1,X\\}$ (so $\\mu=2$), trying weighted received words with weights drawn from a fine grid and all distinct pairs $G,H\\in C(S,D)$; if any triple satisfies $\\Delta(w,G)+\\Delta(w,H)<2$, then Lemma 4 is false and the theorem's proof does not close. Running the described decoder on that triple would then show whether it actually returns the wrong codeword.","tokens_in":7017,"feed_emoji":"🔑","tokens_out":10733,"duration_ms":100444,"temperature":0.7,"pith_summary":"The paper claims that the deterministic polynomial-time unique-decoding algorithm originally built for bounded-total-degree polynomials over a product grid can be adapted to decode every downset code over a finite grid. A downset code is specified by a monomial set $D$ that is closed under taking factors, and the code consists of all evaluations of polynomials whose monomials lie in $D$. The adaptation is a recursive decoder that, given a weighted received word, finds the unique codeword within weighted distance $\\mu(S,D)/2$ whenever one exists, where $\\mu(S,D)=\\min_{\\alpha\\in D}|\\nabla(\\alpha)|$ is the code's minimum distance. This matters because downset codes package many natural polynomial code families---total-degree, individual-degree, weighted-degree, and support-size constraints---into one class with a uniform decoding procedure.","feed_headline":"Downset codes get a polynomial-time unique decoder","feed_subtitle":"One recursive algorithm covers total-degree, individual-degree, weighted-degree, and support-constrained polynomial codes.","key_machinery":"The central object is the downset $D$, a finite set of monomials closed under taking factors; the code $C(S,D)$ evaluates all polynomials whose monomials lie in $D$, with each variable individually bounded by the grid size. The argument is carried by coefficient peeling along a distinguished variable: write every codeword as a polynomial in the last variable $Y$, decode each vertical line with the univariate weighted Reed-Solomon decoder, convert the recovered leading coefficients into a weighted word on the $(m-1)$-dimensional grid, and repeat. Three ingredients keep the recursion exact: Lemma 2 gives the minimum distance $\\mu(S,D)=\\min_{\\alpha\\in D}|\\nabla(\\alpha)|$, Lemma 3(2) bounds the distance of a sliced downset by the product of the slice distances, and Lemma 4 supplies the weighted-distance inequality that prevents two distinct codewords from both being inside the promised radius.","core_discovery":"The central claim, Theorem 5, is that for every finite grid $S_1\\times\\cdots\\times S_m$ over a field, every downset $D\\subseteq M$, and every weighted received word $w:S\\to F\\times[0,1]$, there is a deterministic polynomial-time algorithm that outputs a codeword $C\\in C(S,D)$ with $\\Delta(w,C)<\\mu(S,D)/2$ whenever such a $C$ exists. The algorithm decomposes a codeword as $\\sum_{i=0}^d P_i(X)Y^{d-i}$, decodes each vertical line $\\{x\\}\\times S_m$ as a univariate weighted Reed-Solomon code to recover the coefficient of $Y^{d-i}$, assembles those coefficients into a weighted word in the remaining $m-1$ variables, and recurses until the base case $m=1$. The proof shows by induction that the recovered coefficient polynomial at each level is exactly the true one, using the downset version of the Schwartz-Zippel lemma for the distance formula and the weighted-distance inequality of Lemma 4 to rule out two close codewords. The result subsumes product-set Reed-Muller decoding, individual-degree-bounded decoding, and linear decoding of multilinear polynomials over the Boolean cube.","pith_inferences":["A testable extension is to run the same coefficient-peeling scheme on other families where a distance bound factors over a product structure; the proof suggests that only the distance inequality and the base decoder matter, not the grid's field geometry.","The repeated use of weighted received words means the decoder could plausibly serve as a subroutine in soft-decision or list-decoding pipelines, since those produce weights rather than hard symbol values.","The downset formulation gives a design knob for explicit codes: choosing a factor-closed monomial set shapes rate and distance, and this paper shows any such choice is decodable; constructing good downset codes for specific noise models is an obvious next step.","A more speculative consequence is that codes defined by other combinatorial closure properties, such as closure under a different partial order on monomials, may admit the same recursion if they have an analogous distance formula."],"forward_implications":["Every downset code over a finite grid has a deterministic polynomial-time unique decoder up to half its minimum distance, with the radius computed directly from the monomial set $D$.","The decoder unifies previously separate settings: total-degree Reed-Muller codes over product sets, codes with individual degree bounds, weighted-degree codes, and multilinear decoding over the Boolean cube.","Because the minimum distance formula is explicit, designing a downset code comes with a computable decoding radius, not just an existence guarantee.","Weighted received words are supported throughout, so the decoder can take reliability information as input at every level of the recursion.","If no codeword lies within $\\mu(S,D)/2$, the algorithm still runs in polynomial time and outputs an arbitrary polynomial, so the theorem is a true promise-style unique decoder."],"supporting_citations":[{"why":"Provides the original product-grid Reed-Muller decoder and the weighted-distance inequality imported as Lemma 4, which the recursion relies on.","marker":"[KK17]"},{"why":"Forney's generalized minimum distance decoding is the univariate weighted Reed-Solomon base case for $m=1$.","marker":"[Jr.66]"},{"why":"The classical monomial-enumeration theorem behind the downset Schwartz-Zippel lemma, which yields the exact minimum distance formula.","marker":"[Mac27]"},{"why":"Supplies the monomial-order and Macaulay-theorem background used in the proof of Lemma 2.","marker":"[CLO07]"}],"fun_headline_variants":["Universal polynomial-time decoder for downset codes","One decoder uniquely handles every downset code","Downset codes: a single recursive decoder for many families","Polynomial-time unique decoding for all downset codes","Downset codes get a general deterministic decoder"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is Lemma 4, the weighted-distance triangle-type inequality, which is cited from the earlier paper and not proved here; if two distinct codewords could both sit within half the minimum distance of a weighted received word, the recursive decoder would have no way to choose correctly.","fun_headline_variants_meta":{"raw":{"variants":["Universal polynomial-time decoder for downset codes","One decoder uniquely handles every downset code","Downset codes: a single recursive decoder for many families","Polynomial-time unique decoding for all downset codes","Downset codes get a general deterministic decoder"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000279,"raw_usage":{"total_tokens":1624,"prompt_tokens":879,"completion_tokens":745,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":495,"completion_tokens_details":{"reasoning_tokens":674}},"tokens_in":495,"tokens_out":745,"duration_ms":8114,"temperature":1.0,"reasoning_tokens":674,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:22:21.427094+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Search over a small instance, such as $S=\\{0,1\\}^2$ with the downset $D=\\{1,X\\}$ (so $\\mu=2$), trying weighted received words with weights drawn from a fine grid and all distinct pairs $G,H\\in C(S,D)$; if any triple satisfies $\\Delta(w,G)+\\Delta(w,H)<2$, then Lemma 4 is false and the theorem's proof does not close. Running the described decoder on that triple would then show whether it actually returns the wrong codeword.","supporting_citations":[],"review_version":1}