The paper looks great.  Again, all comments from me at this point are just at the advice level, although one comment about the notation is incorrect.

p1: "The proof uses a space-time tradeoff and the Main Theorem can be restated to highlight the space requirements."

I would say "generalized" rather than "restated".   It's the same proof, but the result per se is more general.

p4: "We slightly abuse notation and use \tilde{O} also to mean 'equal up to constants and logarithms'."

This is incorrect.  There is no abuse of notation and the footnote is not needed, because \tilde{O}(f(n)) already means "up to constants and logarithms".  Actually the paper itself says the same thing on page one, so the footnote contradicts the (correct) introduction to the paper.

Well, almost correct.  In the formula on page 1; the upper bound should be f(n) < cg(n)(log(g(n))^k.  See:

https://cs.stackexchange.com/questions/63264/what-does-tilde-mean-in-big-o-notation

Also, it's a bit funny to use k for two different things in the first half of the first page of the paper.

p4 and maybe elsewhere: On that note, in some places where the current paper has \tilde{O}(f(n)), O(f(n)) would also be correct and would perhaps be a clearer statement. For example, on page 4, it would be correct to say (n choose i) = O(n^i).  Evaluating \bar{\phi}_{\le k} is a sum over O(n^k) subdiagrams.  (Even then you get \tilde{O}(n^k) running time because the coefficients have O(log(n)) digits.)

Granted, in the main theorem and in many other places, the tilde is certainly needed.  In any case, since all bounds are correct with the tildes, the authors can decide whether to remove some of these tildes in the cases where they can be removed.