First, and most importantly, the paper is written in an inaccessible way. It is not because it is too complex, but because it does not provide details which are essential for a reader to understand the paper. On the other hand, the paper presents and uses a number of concepts that are never explained, which makes the reader confused. As a result I was not able to check the proofs and I find the current form not satisfying basic standards of a research paper.
As for the results, the fact that the results are theoretic is not a problem itself, but it would be interesting to see what is the impact of succinctness gaps. For example if it has any theoretical applications, or impact on practical performance.
In what follows I will mention some places in which paper has problems in writing, which make it very unclear, imprecise, and impossible to me to understand even though I have an expertise in this area.
The introduction uses a lot of unexplained notions, for example at this point it is not clear what does it mean that “Each graded modality tests one threshold in c.”, as it is not even explained what is c and what is meant by thresholds. Similarly, “R-simple network” is unexplained and non-standard notion, so claiming some result about it is a mistake. The statement “The lower bound allows recursion, binary thresholds, directed acyclic graph (DAG) sharing, and global counting, and remains exponential” is completely unclear, as it is not clear what is “the lower bound” in this context, and what are all the mentioned components. The mentioned “logical gap” is unclear; I believe it is actually about succinctness gap. The statement “At depth one, weighted aggregation yields a 2Ω(m) separation by a two- dimensional slope argument.” is also unclear as it is not explained what “weighted aggregation” is, what does it mean that it yields “separation”, and what “two dimensional slope argument” is.
The description of the main results in Table 1 are unclear and at this stage cannot be understood by a reader as the symbols and notions used therein are not explained.
The setting used in the paper is not explained well. Description of GMSC is incomplete and lacks precision. For example \varphi and \psi are not described, and it is essential. It should be explained that for every X a program has a base and induction rules. Notions like “rounds” or “graded indices” are used but not explained. Global-counting extension is also not clear as it is not clear where the additional modality can occur and what is \varphi.
Similarly GNN[F] is not well defined; for example it is unclear what is SUM_S, what is x_v^0. Also d is not defined and it is not clear how \lambda is taken into account by a GNN. Statement “reads out after its finite sequence of transitions” is very imprecise as it is not clear what does it mean to “read out” and what are “transitions”, and what are their sequences. Also, I do not understand the whole paragraph about “encoded parameter size”; it is not explained what is “straight-line circuit over the inputs [p ∈λ(v)]”, what is “clipped-ReLU gate over S” or what are “parity networks”. “Automata witness” occurs also unexplained, so I am not sure what object it is.
Automaton description is also imprecise. For example it is not clear what “distinguished node” is, as it is not specified. The notion of bounded automaton is not precisely formulated. The sentence “The bound excludes small state spaces under every
encoding, not compact circuits for π, δ, or F.” remains unclear to me.
I find formulations of the theoretical results imprecise. For example what is a “breakpoint”, the main notion in the first result, is not even described. Also, what are tree and DAG syntax, which were never explained? As a result, in the current form it cannot be understood what Lemma 3.1 claims.
Other results and proofs have similar problems. For example the notion of a GNNs “clock” was not explained but it is heavily used, which makes Theorem 3.2 not accessible. The notion of “Under the explicit-feedforward convention” was never explained. Corollary 3.3 is very unclear too. It seems to refer to the previous theorem but it is unreadable in its current form. For example “For the recurrent family, source size m = Θ(n) forces GMSC size 2Ω(m)” is completely unclear.