A connection between descriptive set theory and computer science has been discovered, allowing problems in one field to be rewritten and solved in the other by Anton Bernshteyn.
Problems in descriptive set theory (measuring infinite graph colorings) are mathematically equivalent to problems in distributed algorithms (efficient network coloring).
Problems in descriptive set theory (measuring infinite graph colorings) are mathematically equivalent to problems in distributed algorithms (efficient network coloring).
Descriptive set theorists study the niche mathematics of infinity. Now, they’ve shown that their problems can be rewritten in the concrete language of algorithms.
A new mathematical proof resolves a 35-year-old bet between Noga Alon and Peter Sarnak regarding the prevalence of optimal expander graphs, demonstrating that both mathematicians were partially incorrect. The proof, building on work in random matrix theory, reveals that approximately 69% of regular graphs are Ramanujan graphs.
