Many machine learning tasks involve analysis of set valued inputs, and thus the learned functions are expected to be permutation invariant. Recent works (e.g., Deep Sets) have sought to characterize the neural architectures which result in permutation invariance. These typically correspond to applying the same pointwise function to all set components, followed by sum aggregation. Here we take a different approach to such architectures and focus on recursive architectures such as RNNs, which are not permutation invariant in general, but can implement permutation invariant functions in a very compact manner. We first show that commutativity and associativity of the state transition function result in permutation invariance. Next, we derive a regularizer that minimizes the degree of non-commutativity in the transitions. Finally, we demonstrate that the resulting method outperforms other methods for learning permutation invariant models, due to its use of recursive computation.
The rebuttal did not address my concerns convincingly. There were also simple fixes that the authors could have implemented but they decided not to update the paper. I will keep my original assessment. 
--------------
The premise of the work is very interesting: RNNs that are permutation-invariant. Unfortunately, the paper seems rushed and needs a better justification for not having a RNN memory that is associative. It also should cast the contributions in light of other existing work (not cited). The paper says "In this section and the remainder of the paper, we focus on the latter [commutative RNN memory operator], namely introducing a constraint (or equivalently, regularizer) that is commutative", but it never talks about the impact of a RNN memory using a non-associative operator. Being commutative is easy, isn't Equation (2.4) commutative if \Theta = W? Being associative is hard, since non-linear activations are not easily amenable to associativity.
Section 4: "The above example demonstrates that RNNs can in some cases be a natural computational model for permutation invariant functions." => Janossy pooling (Murphy et al., 2019) gives an alternative way to use RNNs, with a way to make their method tractable. Actually, my guess to why the RNNs experiments work well, even without an associative memory, is because the training examples come in multiple permuted forms, which is the data-augmentation version of the pi-SGD optimization described in Janossy pooling. 
On page 1, "consider the problem of computing the permutation invariant function f(x_1, . . . , x_n) = max_i x_i", what follows is not a proof of necessity. It is an informal argument that either should be made formal or should be described as informal.
There is a lot of missing related work for sets:
Murphy, Ryan L., Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. "Janossy pooling: Learning deep permutation-invariant functions for variable-size inputs." ICLR 2019.
Wagstaff, Edward, Fabian B. Fuchs, Martin Engelcke, Ingmar Posner, and Michael Osborne. "On the limitations of representing functions on sets." ICML 2019.
Lee, Juho, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. "Set Transformer: A Framework for Attention-based Permutation-Invariant Neural Networks." ICML 2019.
Also missing related work for graphs:
Bloem-Reddy, Benjamin, and Yee Whye Teh. "Probabilistic symmetry and invariant neural networks." arXiv:1901.06082 (2019).
Murphy, Ryan L., Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. "Relational Pooling for Graph Representations." ICML 2019.
The paper has an interesting question but needs to build on prior work. As of now, I am unconvinced that not having an associative operator for the RNN memory will lead to a good nearly permutation invariance function (unless there is data augmentation, per Janossy pooling).