We prove that to store n bits x so that each
prefix-sum query Sum(i) := sum_{k < i} x_k can be answered
by non-adaptively probing q cells of log n bits, one needs
memory > n + n/log^{O(q)} n.

Our bound matches a recent upper bound of n +
n/log^{Omega(q)} ... more >>>

We show that k-tree isomorphism can be decided in logarithmic
space by giving a logspace canonical labeling algorithm. This improves
over the previous StUL upper bound and matches the lower bound. As a
consequence, the isomorphism, the automorphism, as well as the
canonization problem for k-trees ... more >>>

Graph Isomorphism is the prime example of a computational problem with a wide difference between the best known lower and upper bounds on its complexity. There is a significant gap between extant lower and upper bounds for planar graphs as well. We bridge the gap for this natural and ... more >>>