{"id":"e7f84e75-55f8-49d7-bada-e368f00b7a28","arxiv_id":"2411.19713","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"CantorNet gives two equivalent ReLU networks for the same self-similar decision boundary, one with O(k) neurons and one with O(2^k) neurons, as a sandbox for complexity measures.","lead":"The paper defines CantorNet, a small family of ReLU neural networks whose decision boundaries are jagged, self-similar curves built from the Cantor set construction. It provides two equivalent network descriptions with O(k) versus O(2^k) neurons, offering a controlled testbed for complexity measures.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's minimality proof is an unsupported transfer from Kolmogorov complexity to a neuron-count lower bound; the claimed Ω(k) lower bound for ReLU networks is never derived.","rationale":"The reader's weakest assumption identified exactly the same gap: the transfer from the O(k) Kolmogorov complexity of the triadic decision problem to a lower bound on ReLU neuron count is asserted, not proved. This is load-bearing because the paper's main theoretical contribution is the claim that the recursion-based representation is provably minimal in neuron count. The construction itself is clean, and the forward direction (O(k) neurons for the recursive representation, O(2^k) for the DNF) is credible, but 'minimal' requires a matching lower bound. This is fixable: a formal lower bound can likely be obtained by counting the affine pieces of the decision boundary and using the activation-pattern correspondence. Because the gap is in the proof, not necessarily in the truth of the theorem, the reader's CONDITIONAL verdict remains appropriate. I do not see a reason to strengthen or weaken the verdict based on this stress-test pass; the concern confirms the need for the stated revisions rather than overturning the paper's core idea.","tokens_in":9553,"tokens_out":7475,"duration_ms":71055,"concrete_test":"Prove or disprove Theorem 1 by counting affine pieces: (i) compute the number of distinct affine segments of the boundary ∂R_k from Eq. (3) for k = 1, ..., 8; (ii) check whether this number is at least c·2^k for some c > 0. If yes, combine with the standard activation-pattern bound (number of linear regions of any ReLU network with N neurons is at most 2^N, which the paper itself cites as a one-to-one correspondence in Section 2) to obtain N ≥ k, making the O(k) lower bound rigorous. If the segment count is only polynomial in k, the claimed minimality is false. An alternative check is to attempt to construct a ReLU network with o(k) neurons whose zero set equals R_k for all k; any such construction would refute Theorem 1.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is Theorem 1: the recursion-based ReLU representation of Eq. (4) is of minimal complexity order in terms of the number of neurons, i.e., any equivalent ReLU network requires Ω(k) neurons. The only argument given is in Section 4: 'As a recursion step given by Eq. (5) and Eq. (6) is equivalent to a recursion in the triadic number expansion (Alg. 1), which is of the minimal order of Kolmogorov complexity, there cannot exist an equivalent ReLU network of strictly lower order of Kolmogorov complexity.' This is an assertion, not a derivation. It conflates the Kolmogorov complexity of an algorithm that enumerates k-digit triadic prefixes with the minimal number of neurons in a ReLU network realizing the decision boundary. These are different complexity measures: a network could in principle encode k in its weights, or use a different algorithmic strategy, without having a program of size proportional to k. To prove Theorem 1, one needs a lower bound of the form: any ReLU network whose zero set equals R_k (Eq. (3)) must have Ω(k) neurons. No such bound is supplied. The paper's own observation that there is a one-to-one correspondence between activation patterns and linear regions could supply the missing tool, since any network with N neurons has at most 2^N activation patterns and hence at most 2^N linear regions; if the boundary ∂R_k has exponentially many affine pieces in k, the lower bound follows. But the paper does not state or use this argument, so the minimality claim is currently unproven.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes CantorNet, a family of ReLU neural networks whose decision boundary is obtained by recursively composing the piecewise-linear function A(x)=max{-3x+1,0,3x-2}. For each recursion level k, the decision region R_k is defined in Eq. (3) as the subgraph of (A^{(k)}(x)+1)/2. The authors give two ReLU representations: a recursion-based network N_A^{(k)} with O(k) neurons and a disjunctive-normal-form network N_B^{(k)} with O(2^k) neurons, and they relate activation patterns of N_A^{(k)} to prefixes of triadic expansions. The central theoretical claim is Theorem 1, which states that the recursion-based representation is of minimal complexity order (Omega(k) neurons) among all ReLU networks realizing the same decision boundary. The paper also discusses applications to testing geometrical and topological complexity measures, data augmentation, and adversarial robustness.","tokens_in":9896,"tokens_out":12988,"duration_ms":109589,"significance":"The idea of a synthetic, analytically known, arbitrarily ragged ReLU decision surface is useful and timely: it gives the community a controlled benchmark for complexity measures, and the authors provide code. The explicit two-representation construction (recursion vs. DNF) is clear, and the O(k) versus O(2^k) neuron counts are easy to verify. However, the paper's main theorem is not proved as written: the Section 4 argument transfers an informal Kolmogorov-complexity claim to a neuron-count lower bound without a formal derivation. The missing lower bound is likely obtainable from the paper's own observation that activation patterns correspond to linear regions, since with N neurons there are at most 2^N activation patterns and the Cantor boundary has at least 2^k of them. Thus the central claim is plausible and repairable, but the current manuscript does not establish it rigorously. There are also local mathematical inaccuracies in the triadic-expansion discussion that should be corrected.","major_comments":[{"comment":"Definition 1 states that N^{-1}(0)=R_k, but R_k defined in Eq. (3) is the two-dimensional set {y <= (A^{(k)}(x)+1)/2}, while the 0-preimage of the network N_A^{(k)} from Eqs. (4)-(5) is the one-dimensional boundary curve y=(A^{(k)}(x)+1)/2 (the network takes negative values below this curve). To make the definition consistent, one must either apply a final ReLU max(0,.) to N_A^{(k)} so that the zero set becomes the closed subgraph, or redefine R_k to be the boundary curve. This ambiguity affects all subsequent statements about insets, outsets, and activation patterns.","section":"Definition 1, Eq. (3)-(5)"},{"comment":"The proof of Theorem 1 consists of the assertion that the recursion step is equivalent to a triadic recursion 'which is of the minimal order of Kolmogorov complexity, there cannot exist an equivalent ReLU network of strictly lower order of Kolmogorov complexity.' This transfers a claim about the descriptive complexity of an algorithm to a lower bound on the number of neurons in any equivalent ReLU network, and no argument is given to rule out networks that encode the boundary in a different way, e.g., by using k-dependent weights or a different algorithmic strategy. A formal lower bound should be supplied. A natural route is to use the paper's own one-to-one correspondence between activation patterns and linear regions: since the Cantor-boundary construction has at least 2^k distinct activation patterns (or affine pieces along the x-axis) and any ReLU network with N neurons has at most 2^N activation patterns, N=Omega(k) follows. Without such an argument, Theorem 1 is unproved.","section":"Section 4, Theorem 1"},{"comment":"The claim that any x in I1 union I3 can be described in a triadic system with arbitrary precision l as x = sum_{i=1}^l a_i/3^i with a_i in {0,2} is false. For instance, x=1/9 in I1 has the ternary expansion 0.01_3, which contains the digit 1. Only points of the middle-third Cantor set have a ternary expansion composed solely of 0s and 2s. The isomorphism between activation codes and triadic prefixes should be stated for points that stay in I1 union I3 for k iterations, or the code should be defined as ending when the point falls into I2. As written, this section overstates the correspondence and makes Lemma 1's proof imprecise.","section":"Section 3.2"}],"minor_comments":[{"comment":"The statement that 'there is a one-to-one correspondence between an activation pattern and a linear region' should be qualified to 'non-empty activation patterns', since many binary vectors can define empty polyhedra for a given network.","section":"Section 2"},{"comment":"The interval-to-digit mapping is inconsistent: Fig. 1 labels I1, I2, I3 as digits 0, 1, 2, while Algorithm 1 outputs 0 for I1, terminates for I2, and outputs 1 for I3. Please align the notation, e.g., by treating termination in I2 as a special marker for the digit 1.","section":"Figure 1, Algorithm 1"},{"comment":"The phrase 'spans the whole spectrum of possible Kolmogorov complexities' is stronger than what is shown; the paper provides two endpoints and mentions an 'intermediate example' without demonstrating a continuum. Please qualify the claim.","section":"Abstract and Section 4"},{"comment":"Proposition 1 is only sketched; for a journal version, please provide the complete inductive construction with explicit definitions of the affine functions h_i for arbitrary k.","section":"Appendix B"}],"recommendation":"major_revision","confidential_remarks":"The manuscript reads as a workshop paper (and was accepted at a NeurIPS workshop): the central example is nice, but the proof of Theorem 1 is only a sketch. The false ternary-expansion statement in Section 3.2 should be corrected in revision. I did not find evidence of problematic citation practice; the self-citations are relevant. Adding the activation-counting argument for the lower bound, as suggested in the major comments, would make the paper much stronger and more suitable for a full journal."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nCantorNet is a clean, explicitly constructed sandbox: two ReLU representations of the same arbitrarily ragged decision boundary, with neuron counts O(k) for the recursion-based version and O(2^k) for the DNF version. The weight matrices are written out, the code is public, and the activation-pattern/triadic-expansion connection is a nice pedagogical touch. If you work on complexity measures for neural networks, this is a useful testbed.\n\nWhat's genuinely new is the specific pair of equivalent representations of a Cantor-set-like boundary. Prior work (Montúfar et al., Arora et al.) gives general bounds on linear-region counts, but not this clean two-representation example. That counts.\n\nThe soft spots are real but fixable. Definition 1 says N^{-1}(0) = R_k, but R_k in Eq. (3) is the region under the curve, while the 0-preimage of the Eq. (5) network is the boundary curve itself. So the definition and construction don't line up. Second, Section 3.2 claims every x in I1 ∪ I3 has a triadic expansion with digits only in {0,2}; that's false as written — for example 4/27 has no such expansion. What's true is that points in the k-th Cantor set layer do. Third and most important, Theorem 1's minimality claim is asserted, not derived. The argument that 'the triadic recursion has minimal Kolmogorov complexity, therefore no ReLU net with fewer neurons exists' is a non-sequitur. The missing proof is straightforward: the boundary has 2^k affine pieces, and an N-neuron ReLU net has at most 2^N activation patterns, hence at most 2^N linear regions; so N ≥ k. The theorem is probably true, but as written it isn't proven.\n\nThere are minor overstatements too: 'spans the whole spectrum of possible Kolmogorov complexities' is really just two points plus concatenations.\n\nMy take: it's a workshop-level paper with a genuinely useful construction and a gap in the proof that is easy to fill. I'd send it to review — a competent referee can ask for the fix. The paper is for people studying complexity measures, geometry of ReLU activation patterns, or synthetic robustness benchmarks.\n\nRecommendation: engage with it, but ask for the definitional corrections and the real lower-bound proof.","headline":"A genuinely useful two-representation ReLU sandbox whose minimality theorem is asserted rather than proven, but the missing proof is straightforward.","tokens_in":10410,"tokens_out":6344,"would_cite":false,"duration_ms":51413,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07","68Q30","28A80"],"pacs":[],"model":"deepseek-v4-flash","headline":"CantorNet gives a ReLU decision surface whose recursive construction is minimal at O(k) neurons and whose polyhedral twin costs O(2^k), a controlled scale for testing complexity measures.","keywords":["CantorNet","ReLU neural networks","Cantor set","fractals","Kolmogorov complexity","triadic expansion","decision boundary","topological complexity"],"falsifier":"Try to build a ReLU network that computes the level-$k$ triadic-prefix decision for all points of $[0,1]$ using $o(k)$ neurons, for example by encoding several ternary digits per neuron or sharing subcircuits across depth, and test it on the $2^k$ interval endpoints; any correct sublinear construction would falsify Theorem 1.","tokens_in":9357,"feed_emoji":"📐","tokens_out":11642,"duration_ms":97234,"temperature":0.7,"pith_summary":"This paper introduces CantorNet, a family of ReLU neural networks (networks built from the activation $\\max(x,0)$) whose decision boundary is the level-$k$ middle-third construction that defines the Cantor set. The same boundary is built in two ways: a recursion that reuses a fixed five-neuron block and needs $O(k)$ neurons total, and an explicit union of polyhedral pieces that needs $O(2^k)$ neurons. The authors claim the recursive representation is of minimal complexity order among ReLU networks for this surface, in the sense of description length as measured by neuron count. If correct, CantorNet supplies a tractable, analytically known family of decision surfaces that can be tuned from simple to arbitrarily ragged, giving complexity measures a ground truth to test against.","feed_headline":"Fractal decision surface: one ReLU net is provably minimal","feed_subtitle":"The same boundary needs O(k) neurons recursively and O(2^k) polyhedrally, giving a controlled testbed.","key_machinery":"The load-bearing object is the one-dimensional generating function $A(x)=\\max\\{-3x+1,0,3x-2\\}$, nested $k$ times and lifted to a two-dimensional decision manifold $R_k=\\{(x,y)\\in[0,1]^2 : y\\le(A^{(k)}(x)+1)/2\\}$. The recursion is encoded by fixed weight matrices so that each extra level costs a constant number of neurons, giving the $O(k)$ representation. The triadic-expansion isomorphism is what connects activation patterns to the first $k$ digits of the input's base-3 expansion and carries the minimality argument. The opposing construction writes the same manifold as a min/max expression of affine half-spaces and uses the fact that $\\min$ is itself expressible as a ReLU network, producing the exponential-size disjunctive normal form.","core_discovery":"The central claim is that the recursion-based ReLU network $N_A^{(k)}$, formed by nesting the generating function $A(x)=\\max\\{-3x+1,0,3x-2\\}$ through the weight matrices of Eq. (4), represents the level-$k$ Cantor decision manifold with $O(k)$ neurons, and that this is optimal: no equivalent ReLU network can have strictly lower order of complexity in neuron count. The proof route is an isomorphism between the network's activation patterns and the triadic (base-3) digit expansion of the input up to $k$ digits; deciding those digits has minimal description length $O(k)$, and the nested construction realizes it with exactly that many neurons. The same manifold also admits a disjunctive-normal-form description as $\\min(h_1, h_2, h_{r(k)}, D_1, \\ldots, D_{\\lfloor r(k)/4\\rfloor+1})=0$ with 'dent' terms $D_l=\\max(h_{4l-1}, h_{4l}, h_{4l+1})$, whose ReLU realization costs $O(2^k)$ neurons. CantorNet therefore exhibits two exact descriptions of one decision boundary at opposite ends of the description-length spectrum and identifies which one is minimal.","pith_inferences":["The authors leave implicit that the same nesting trick should yield minimal-complexity ReLU networks for other digit-restricted self-similar sets, such as base-$b$ Cantor sets or higher-dimensional Sierpiński-like constructions.","A consequence of the two representations is that any single-number complexity measure should be run on both CantorNet twins; a measure that cannot distinguish $O(k)$ from $O(2^k)$ is measuring the representation rather than the geometry.","One testable extension is to train classifiers on samples from the inset and outset at growing $k$ and check whether generalization or adversarial robustness degrades exactly as predicted by the triadic digit structure.","The weight-sharing structure of the recursive representation suggests a notion of effective network depth based on description length rather than raw layer count, which the paper does not develop."],"forward_implications":["CantorNet provides decision boundaries of exactly known raggedness, so a proposed geometrical or topological complexity measure can be calibrated against a ground-truth complexity of $O(k)$ in one representation and $O(2^k)$ in the other.","Because activation patterns in the recursive network are literally $k$-digit triadic codes, the family gives a closed-form map between input space and activation space for studying linear regions, Betti numbers, and related descriptors.","The same manifold being representable at both complexity extremes means CantorNet can expose measures that mistake representation size for intrinsic surface complexity.","The analytically known, arbitrarily ragged boundary makes CantorNet a natural testbed for showing how geometry-ignorant data augmentation or adversarial perturbations break down as $k$ grows."],"supporting_citations":[{"why":"Supplies the middle-third recursive set that both names and shapes the decision manifold.","marker":"Cantor, 1879"},{"why":"Defines the description-length notion that the minimality claim is formulated in.","marker":"Kolmogorov, 1965"},{"why":"Provides the minimum-description-length approximation that lets neuron count stand for complexity when decision boundaries coincide.","marker":"Grünwald et al., 2005"},{"why":"Used in the proof of Lemma 2 to bound the repeated min-composition layers needed for the exponential-size DNF.","marker":"Arora et al., 2018"},{"why":"Outlines the min/max-as-ReLU representation that the exponentially large CantorNet construction relies on.","marker":"Moser et al."},{"why":"Gives the linear-region counting background used to describe the tessellation induced by CantorNet.","marker":"Montúfar et al., 2014"},{"why":"Establishes the one-to-one activation-pattern/linear-region correspondence used to read triadic codes from the network.","marker":"Shepeleva et al., 2020"}],"fun_headline_variants":["CantorNet: ReLU net with O(k) neurons for fractal decision boundaries","Minimal ReLU net represents Cantor-like surface in O(k) neurons","Self-similar decision boundary: optimal ReLU net with linear size","Complexity testbed: ReLU net with provably minimal neurons for Cantor set"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The theorem's lower bound depends on the claim that a ReLU network cannot decide where a point lands among the first $k$ base-3 digits of the Cantor construction in fewer than order $k$ neurons; the paper asserts this transfer from decision complexity to neuron count rather than deriving it formally.","fun_headline_variants_meta":{"raw":{"variants":["CantorNet: ReLU net with O(k) neurons for fractal decision boundaries","Minimal ReLU net represents Cantor-like surface in O(k) neurons","Self-similar decision boundary: optimal ReLU net with linear size","Complexity testbed: ReLU net with provably minimal neurons for Cantor set"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000301,"raw_usage":{"total_tokens":1788,"prompt_tokens":1052,"completion_tokens":736,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":668,"completion_tokens_details":{"reasoning_tokens":652}},"tokens_in":668,"tokens_out":736,"duration_ms":6380,"temperature":1.0,"reasoning_tokens":652,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T05:54:59.019448+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Try to build a ReLU network that computes the level-$k$ triadic-prefix decision for all points of $[0,1]$ using $o(k)$ neurons, for example by encoding several ternary digits per neuron or sharing subcircuits across depth, and test it on the $2^k$ interval endpoints; any correct sublinear construction would falsify Theorem 1.","supporting_citations":[{"cited_title":"Three approaches to the quantitative definition of information","cited_arxiv_id":null,"evidence_quote":"Defines the description-length notion that the minimality claim is formulated in."},{"cited_title":"Understanding Deep Neural Networks with Rectified Linear Units","cited_arxiv_id":null,"evidence_quote":"Used in the proof of Lemma 2 to bound the repeated min-composition layers needed for the exponential-size DNF."},{"cited_title":"Relu code space: A basis for rating network quality besides accuracy","cited_arxiv_id":null,"evidence_quote":"Establishes the one-to-one activation-pattern/linear-region correspondence used to read triadic codes from the network."}],"review_version":1}