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).
A new paper demonstrates that the simplex method, a widely used optimization algorithm, is as efficient as it can be, and explains why it performs well in practice despite theoretical limitations.
Alan Turing and John von Neumann saw it early: the logic of life and the logic of code may be one and the same. This article explores the idea that life, at its core, might be computational, drawing parallels between DNA, computation, and the work of Turing and von Neumann.
In this paper, we revisit one of the simplest problems in data structures: the task of inserting elements into an open-addressed hash table so that elements can later be retrieved with as few probes as possible. We show that, even without reordering elements over time, it is possible to construct a hash table that achieves far better expected search complexities (both amortized and worst-case) than were previously thought possible. Along the way, we disprove the central conjecture left by Yao in his seminal paper 'Uniform Hashing is Optimal'. All of our results come with matching lower bounds.
