[a_tartaruga]

> He wanted to show that every efficient local algorithm can be turned into a Lebesgue-measurable way of coloring an infinite graph

To me this is quite surprising. Distributed systems were not designed to solve measure theory problems.

[jsrozner]

Perhaps it’s that a global solution in the language of set theory was hard to find, but distributed systems — which need to provide guarantees only from local node behavior, without access to global — offered an alternate perspective. They weren’t designed to do so but they ended up being useful.

[Ar-Curunir]

> They weren’t designed to do so but they ended up being useful.

an object doing something that it wasn’t designed for seems to me to be the definition of “surprising”

[zmgsabst]

They’re literally exploring the same object: properties of networks.

That you can express the constraints of network colorings (ie, the measure theory problem) as network algorithms strikes me as a “well duh” claim — at least if you take that Curry-Howard stuff seriously.

[Ar-Curunir]

Curry-Howard is not some magic powder you can just sprinkle around to justify claims. The isomorphism provides a specific lens to move between mathematics and computation. It says roughly that types and logical propositions can be seen equivalently.

Nothing in the result in the article talks about types, and even if it could be, it’s not clear that the CH isomorphism would be a good lens to do so.

[zmgsabst]

Curry-Howard literally says that a proof your object has a property is equivalent to an algorithm which constructs a corresponding type.

I’m not “sprinkling magic powder”, but using the very core of the correspondence:

A proof that your network has some property is an algorithm to construct an instance of appropriate type from your network.

In this case, we’re using algorithms originally designed for protocols in CS to construct a witness of a property about a graph coloring. In the article, it details exactly his realization this was true — during a lecture, seeing the types of things constructed by these algorithms corresponding to the types of objects he works with.

[Certhas]

Do you have any actual evidence that this result can be viewed as an instance of CH?

The networks on the measure theory side and on the algorithmic side are not the same. They are not even the same cardinality. One has uncountably many nodes, the other has countably many nodes.

The correspondence outlined is also extremely subtle. Measurable colorings are related to speed of consensus.

You make it sound like this is a result of the type: "To prove that a coloring exists, I prove that an algorithm that colors the network exists." Which it is not, as far as I understand.

It seems to me you are mischaracterizing CH here as well:

> A proof that your network has some property is an algorithm to construct an instance of appropriate type from your object.

A proof that a certain network has some property is an algorithm that constructs an instance of an appropriate type that expresses this fact from the axioms you're working from.

[zmgsabst]

> You make it sound like this is a result of the type: "To prove that a coloring exists, I prove that an algorithm that colors the network exists." Which it is not, as far as I understand.

This is the crux of the proof, as I understand it: to classify network coloring measurability, I classify algorithms that color the network.

Which I can do because there’s a correspondence between network colorings (in graph theory) and algorithms that color networks (in CS). Which I’m arguing is an instance of CH: they’re equivalent things, so classifying either is classifying both.

> They are not even the same cardinality. One has uncountably many nodes, the other has countably many nodes. […] Measurable colorings are related to speed of consensus.

Yes — this is why the work is technically impressive, because proving the intuition from above works when extending to the infinite case is non-trivial. But that doesn’t change that fundamentally we’re porting an algorithm. I’m impressed by the approach to dealing with labels in the uncountable context which allows the technique to work for these objects — but that doesn’t mean I’m surprised such a thing could work. Or that work on network colorings (in CS) turned out to have techniques useful for network colorings (in math).

> It seems to me you are mischaracterizing CH

You then go on to make some quibble about my phrasing that, contrary to your claim about mischaracterizing, doesn’t conflict with what you wrote.

Edit: removing last paragraph; didn’t realize new author.

[Certhas]

CH as I understand it has nothing to do with this. As an example that illustrates why, consider the simple infinite coloring discussed in the article that uses the axiom of choice. You could not write an algorithm that actually performs this coloring (because Axiom of Choice, and because it requires uncountably many actions). CH says that the statement "all such graphs can be colored" can be computed (in finitely many steps) by a program from the axioms. Even though the colorings can-not be done by a computation.

What CH does not allow you to do is turn an existence proof (a coloring exists) into a constructive proof (a means to actually construct such a coloring). In fact, this is generally not true. Mathematical statements correspond to computations in a much more subtle and indirect way than that.

Honestly, I get the impression that you have a very superficial understanding of the topics at hand, but I am far from an expert myself. If you really know a way to see this as an instance of CH I would be very intrigued to learn about it.