Summary
The paper mainly focuses on the problem of deriving tractability conditions for compositional operations over circuits as to solve a number of queries. By fixing the language of circuits over semirings, the paper generalizes known results and introduce novel ones regarding the tractability of queries solved via algebraic circuits. In addition, it analyzes scenarios where milder structural conditions might be required, when compared to previous results.
Strengths
The results of this paper are part of a series of many theoretical results regarding the tractability of complex operations over circuits. I think the paper positively contributes to the current research area, with a more general understanding of already known results but also new ones. For instance, the exponential separation (Theorem 9) provides an example where lifting the X-first property not needed for computing 2AMC queries on particular semirings might provide an exponential expressiveness advantage. However, note that I lack background regarding the causal probabilistic queries being considered in Section 4.2, and I am not able to fully check the claims regarding their complexity.
I believe the paper is very well written: the notation is very clear, most of the claims are well motivated from the beginning, and there are concise examples across the paper. The proofs in the appendix are also easily readable once having understood the structural properties being used.
The reason of the lower scores related to soundness and contribution are listed in the weaknesses section. However, note that I am somewhat confident that the authors can solve the following issues during the rebuttal phase and therefore potentially improving my score.
Weaknesses
I think that some results requiring particular semirings and homomorphisms require so many properties that make me wonder their actual contribution.
Tractable mapping (Theorem 4) requires the following combination of properties to be both true:
1. $\tau$ is additive OR $C$ is deterministic
2. $\tau$ is multiplicative OR ($\tau$ maps the multiplicative identity AND for each product $\alpha$, one of its input must output zero or one as a constant).
I think that the authors should have stressed the limitations of the given properties on $\tau$. E.g., if $C$ is not deterministic and there are no product units satisfying the above, then which functions $\tau$ are we restricted to in practice? See the question 1 below for more on this.
Theorem 3 claims that one can compute the product of support compatible circuits linearly in the maximum circuit size for both time and memory. However, I think the authors should state that this complexity assumes that (i) we already know the isomorphism between nodes, and (ii) we already know how to "match" the supports of sum nodes in the algorithm. I think that without (ii) one would definitely need linear space and quadratic time instead.
In line L298-L300, the authors claim that for particular semirings and mappings, one could relax the determinism property from the circuit for tractable 2AMC. However, this does not seem to be reflected in table 2, where X-Det is present in all 2AMC queries. I think the authors should either make a milder claim or explicitly show in table 2 a case of such a query.
Looking at Algorithm 2 and 3, I think there are corner cases that are not covered neither by them nor by the proofs. For example, the case of multiplying a sum node and a product node is missing. The case of multiplying input nodes and sum/product nodes is also missing. In fact, these algorithms are way too small when compared to the algorithm of the product showed in [35] (Algorithm 3 in the appendix). I believe the cases must be covered for completeness.
I believe a minor weakness of the presentation of this paper is that it mixes two kinds of theoretical results. It contains some results that leverage algebraic circuits and specific properties regarding semirings and morphisms (e.g., Theorem 4). However, it seems the majority of the other results do not actually need any specific property of the semiring being chosen, and could have been part of a work following the compositional atlas paper on circuits [35]. When reading the paper, I often found myself asking whether the theorems and proof I was looking at were the result of a property of semirings I was missing. This is because of the title and the definition of algebraic circuits is the first definition appearing, and I was expected the rest of the paper being very dependent on it. Instead, it seems many theorems can stand on their own with the usual circuit definition given in [35]. Although minor, I think it would be beneficial if the authors stressed at the beginning that the chosen semiring is not really important for many of the results being shown.
Questions
1. If we restrict $\tau$ to be both additive and multiplicative homomorphisms, then does this imply it can only be identity function? It looks like it can only be identity function as for Lemma 3.8 in the appendix of [35]. Do the authors agree on this? If yes, then I think it is necessary to refine the conditions required by Theorem 4 as to include these results about the satisfaction of Cauchy functional equations.
2. Following Question 1, are there examples of both additive and multiplicative homomorphisms for some particular choices of source and destination semirings?
3. It seems the support-compatibility definition does not consider how scopes of products are factorized. What is the relationship between support compatibility between circuits and compatibility + determinism? Is structured decomposability PLUS determinism in a circuit more restrictive than support-compatibility with itself?
Limitations
I have discussed the presence of limitations in the weaknesses section.