Referee report for "Computing finite-type invariants efficiently"

This paper establishes an algorithm to compute any finite-type invariant of some fixed degree k (or all of them together) with time and space complexity \tilde{O}(n^{\ceil{k/2}}).   The algorithm combines two algorithmic ideas. First, a summation over Gaussian subdiagrams of size k is split into a meet-in-the-middle enumeration to achieve a nearly quadratic acceleration. Second, since the subdiagrams may interleave arbitrarily, partial sums are calculated using a hyperoctree decomposition for the space of subdiagrams of size b.  Both of these ideas are standard in computer science, but they are rarely used together.  The effective use of these methods for this problem is not at all obvious, and the overall construction is very clever.  I have also thought through what is going on and I feel convinced that the paper is correct.  In my opinion, the paper easily meets the standards of the Proceedings and should be accepted for publication.

I recommend some minor revisions mostly for the sake of a more standard and clearer presentation, although I noticed one easily fixable mistake.

p1: The paper describes k as the "type" of a finite type invariant. I think that "degree" is the clearest term, since it comes from a vector space filtration and is analogous to the degree of a polynomial.

p1: I think that it is confusing to number the main theorem in Theorem 4.1.  I recommend Theorem 1.1, and to repeat that if you want to repeat the statement of the result in Section 4.

p1 and later: The tilde notation which is defined at the bottom of the page and is used in the statement of the main theorem is both non-standard (because of the extra log factors) and outmoded.  The best and most standard for asymptotics is so-called "Big O" notation, which dates back to Bachmann and Landau and was extended and popularized by Knuth, particularly in computer science.  See:

https://en.wikipedia.org/wiki/Big_O_notation

The standard way to state the theorem is that the finite type invariants of any fixed degree k can be computed in time \tilde{O}(n^{\ceil{k/2}}), where the tilde diacritic allows for a polylog factor rather than just a constant factor.  Likewise the standard form for the definition at the bottom of page 1 is f(n) = \tilde{\Theta}(g(n)).

p1: Since the algorithm is a space-time tradeoff, the main theorem should state that the new algorithm uses \tilde{O}(n^{\ceil{k/2}}) space as well as time.

p1: It may be understood by the authors, but it is not explicitly stated in the paper, that it is almost impossible to get rid of log factors in robust models of computation with random access memory and growing numerical values.  In fact, the paper has an omission on this point although the construction does work.  Namely, there should be a statement that all calculated counts have only a polylog number of digits.

p1: I am not sure about the phrase "standardly believed", which according to Google Ngram is about 1/1000 as common as the phrase "commonly believed". Besides, instead of accusing people of commonly believing the wrong thing, it might be more diplomatic to say "it is easy to believe that this is the fastest possible".

p2: Although it's okay to refer impatient readers to refer to equation (3) for the main idea, by itself it's not that illuminating.   It would be reasonable to let readers know that the main ideas are meet-in-the-middle and hyperoctrees:

https://en.wikipedia.org/wiki/Meet-in-the-middle_attack
https://www.reddit.com/r/algorithms/comments/efgvbj/need_suggestions_how_to_improve_a_meetinthemiddle/
https://en.wikipedia.org/wiki/Octree
https://math.stackexchange.com/questions/644032/name-of-the-generalization-of-quadtree-and-octree

These standard phrases could also be used in the abstract.

p2 and later: The given definition of a Gauss diagram makes clumsy use of intervals.  Really a Gauss diagram is an oriented perfect matching of the integers from 0 to 2n-1.  Since it is standard to define intervals in ordered sets, including half-open intervals, I recommend the tidy notation [0,2n)_{\mathbb{Z}} for this set of integers.  From the next page onward the paper often intersects an interval in the reals with the integers, which in my opinion is clumsy.  It would be better to write (a,b)_{\mathbb{Z}}, [a,b)_{\mathbb{Z}}, etc.

Likewise instead of "parametrized" and "reparametrized", it would be simpler and clearer to say "numbered" and "renumbered".

p2 and later: The phrase "decorated arrows" is duly visual but it is not precise.  I recommend the phrase "oriented perfect matching".  An "arrow" as used later is then an "edge" (of the matching).

p3 and later: The data used to combine two Gauss diagrams of size k and \ell into a larger one of size k+\ell is set up in a not-very-intuitive, asymmetric way in my opinion.  Instead of a non-decreasing function \lambda, the data could be expressed as a subset S of [0,2(k+\ell))_\mathbb{Z}, or as a partition into two subsets.

p3: I guess superimposition is okay as a term here, but

p3: It doesn't look like the paper uses \bar{\phi}_k except to define \phi_k.  I think that the two sentences could be combined.

p4: Following Wikipedia, this is not the definition of a "lookup table", which instead refers to a precomputed array with numbered indexing:

https://en.wikipedia.org/wiki/Lookup_table

Rather, a searchable collection of key-value pairs is called an associative array:

https://en.wikipedia.org/wiki/Associative_array

Note that an associative array is not necessarily lex ordered.   It can be implemented in any of several ways so that retrieving a value --- and incrementally adding or removing a key-value pair --- takes \tilde{O}(1) time.

p4: Instead of \bar{n}, you can use [0,n)_\mathbb{Z} as in the rest of the paper.

p4: "this Theorem" -> "this theorem"

p4: The "<<" upper bound in the statement of Theorem 3.1 is plainly vestigial.  The "<<" lower bound is needed only to protect the specific meaning of the paper's specific asymptotic notation, and even for that purpose is stronger than necessary.  Another formulation is to let Q be a multiset elements in [0,n)_\mathbb{Z}^\ell, and then say that the time and space complexity to build the table are both \tilde{O}(q), while the time complexity \tilde{O}(1), with a modified meaning of the tilde to allow factors of both log q and log n.

p4: I was thrown by the word "rectangle". I would call a typical shipping box a rectangular box and not a rectangle.

p4: It is cool that the authors might have independently discovered the concept of a hyperoctree and thought of this way to use it.  Still, that standard concept and term would be better as the stated theme of Section 3.2 than dyadic intervals.

p4: The opening sentence of section 3.2 uses the exact same notation [a,b)_\mathbb{Z} (except without the subscript) that would be useful for so much else in the paper.  Note that there is no need to make the integers non-negative.

p5: "can be decomposed" -> "decomposes uniquely"

p5: "View Q \cap R as the sum..."  It would be better to go ahead and state Corollary 3.3 in the very nice Theorem 3.1, for one reason because it is a corollary of the proof and not the theorem.  Actually, Corollary 3.3 is subtly incorrect as stated; or at a minimum, not well stated.  If the weights are reciprocals of distinct primes, then you can get a denominator explosion when you add them.  Of course denominators are not needed in the paper until the very end, where you cannot get a denominator explosion.  I recommend stating "Corollary" 3.3 in terms of a finite-rank free abelian group rather than a rational vector space.  It should also say something about the sizes of the numbers involved.

p6: In the second sentence of the proof of the main theorem, the paper has "\sum_{i=1,\cdots,k}".  Of course \sum_{i=1}^k which appeared before would be better.

p6: The variables k = e+f are unfortunate, both because it is a change of variables from k+\ell on page 3, and because f is commonly used as the name of a function and for other purposes.  I recommend using something like k = \ell+m consistently across both sections.

p6: "that fits in the complement" -> "that lies in the complement"

p7: I highly recommend including arXiv numbers in the bibliography, particularly for [Rou] which is not published elsewhere, but also for references that are published in journals.