Bernshteyn's work on descriptive combinatorics

Stream: computer science

[Matt Diamond]

I read this pop-sci article on recent work connecting descriptive combinatorics and distributed algorithms. Sounded pretty cool... is this something that would be amenable to formalization? Or are we still missing a lot of foundational theory in the relevant areas?

https://www.quantamagazine.org/a-new-bridge-links-the-strange-math-of-infinity-to-computer-science-20251121/

[Shreyas Srinivas]

Well. We’re formalising distributed algorithms

[Shreyas Srinivas]

There’s a lot of missing work here and many of the models are actually a bit poorly defined (many definitions masquerading as one)

[Shreyas Srinivas]

The work is split between branches in Shreyas4991/DGAlgorithms between several branches but much of the work is local to Henrik’s machine and mine.

[Shreyas Srinivas]

The paper gives a definition of LOCAL model and LCL problems that is specific to it

[Shreyas Srinivas]

And it sidesteps important questions on the size of the ID

[Shreyas Srinivas]

It’s definition will also not give you the best way to compose local algorithms in sequence since you have to deal with nasty termination detection issues.

[Shreyas Srinivas]

The correct way to define it is using an asynchronous version of the model with some constraints on message passing