For 1: Seems a little unlikely, as it feels like saying that $pc(f),pc(g) \leq n$ implies $pc(f+g) \leq n+1$ (where pc=permanental complexity), whereas it's probably close to tight that $pc(f+g) \leq 2n+1$... What's the crucial difference between that and the 0-1 setting that would allow your Q1 to have a positive answer? Have you tried computer experiments, even to check if $R_2(4) \subseteq R(5)$, for example?

I had trouble finding an actual copy of the Papakyriakopoulos paper, but I did find this later paper [Whittlesey '58] with a proof of the same result, so I thought others might find the link useful: jstor.org/stable/2033313. I'd be grateful for a digital version of the Papakyriakopoulos paper.

Can you say more or provide a reference as to how the classification of quiver representations is the basis for persistence diagrams? I am familiar with both of these objects (more with quivers than with persistent homology), but didn't know of such a connection.

@TimothyChow: Great answer! The current link is to Tener's PhD thesis, supervised by Deo. Is that what you meant to link to (in which case it should probably just be "Tener"), or is there another paper by the two of them you meant to point to?

@TimothyChow: I agree with you in terms of clarity of the underlying issue. However, the point of mentioning Reverse Math is that it is an active area of mathematical research that deals precisely with questions of the form "Is A necessary to prove B?", but it is an area of math that many mathematicians are not aware even exists (and they cannot even conceive how one might prove such a statement). So, in that sense, I suppose mentioning this area of math is more for the benefit of advertising than anything else.

@TimothyChow: I agree with both you and Amit. Following on Amit's comments, I'd like to draw your attention to the seeming conflict between your answer to his question 1, and the first sentence of your posted answer. I think a fairer answer, which I hope you'd agree with, might be to say that Reverse Math would be the right domain in which to try to prove that diagonalization is necessary for uncountability of the reals, but the difficulty is that no one has any idea how to formalize the notion of "diagonalization" within Reverse Math.

I am guessing that one cannot find the exact minimum-size set without trying all possibilities. It sounds like you are looking for an algorithm to run in practice (rather than worst-case guarantees). In that case, you might try looking at the color-distance partition from each vertex (from a given v, how many vertices have color c and distance d from v?) and choose the vertex for which its color-distance partition has the most parts.

I'd be shocked to see an answer with (fixed) k > 5. Related (although somewhat outdated/incorrect, but still maybe of interest): cstheory.stackexchange.com/a/11403/129

It's perhaps worth mentioning that at the moment we don't even know how to extend [BIP] from multiplicity zero vs nonzero to multiplicity 1 vs >1, let alone something like "small vs large".

Also, even if you are pessimistic about actually resolving Valiant's Conjecture using multiplicity obstructions, studying and learning more about the multiplicities seems like it could still be a useful guide to finding separating modules (that is, it could help you hone in on which isomorphism types of G-modules to be looking for, and therefore what kind of concomitants might possibly be used to separate).

It's worth noting that the rank of the Hessian is precisely what's used to get the current best lower bound on perm v det, namely $n^2 / 2$ see Mignon-Ressayre, Cai-Chen-Li (comput. complex. 2010) and Landsberg-Manivel-Ressayre. (Also, two small things: you misspelled my name :), and you can link to the final journal version dx.doi.org/10.1007/s00037-015-0103-x since it's open access - it's updated quite a bit from the original arXiv post.)

You are asking for relativizable classes $\mathcal{C}, \mathcal{D}$ such that $\mathcal{C}^A \subseteq \mathcal{D}^A$ with probability 1 (over $A$), but $\mathcal{C} \not\subseteq \mathcal{D}$. The problem is, aside from the time & space hierarchy theorems (which relativize), and very low-level classes like $\mathsf{AC}^0$ or $\mathsf{ACC}$, we don't know many unconditional results of the form $\mathcal{C} \not\subseteq \mathcal{D}$

@Qfwfq: No need to apologize - thanks for the helpful comments!

@Qfwfq: Thanks! I agree with the geometric viewpoint, and I appreciate your comments about the functorial one. But how do you reconcile those with this answer, which seems to be saying that part of the value is that you can often easily define a functor and do geometry with it, but then if you can show that it has particularly nice geometry (e.g. is representable, is a variety, etc.) then that's icing on the cake? Is your point that, functorial viewpoint or not, stacks/alg. spaces allow more permissive notions of gluing than schemes, so they are often easier to construct, etc?

This would also serve as an answer to some much more general question about the relationship between schemes (which I think of as "level n" of AG abstraction for some small n, affine algebraic varieties over C being level 0) and stacks, algebraic spaces, and the functorial viewpoint on AG ("level n+1")...and it's great. I'd up vote multiple times if I could!

The Kolmogorov complexity proof that the $n$-th prime number $p_n$ is at most $n \log^2 n$ is only one log off from the correct growth rate, and the proof is basically the same as the K. complexity proof of the infinitude of the primes. See p.4 of Lance Fortnow's note