Congratulations to Prof. Aaron Bernstein, who has received a best paper award from the 63rd IEEE Symposium on Foundations of Computer Science (FOCS) 2022, which is considered one of two top conferences in theoretical computer science. FOCS is an annual conference that accepts around 30% of 400 submissions; Aaron's paper is one of two to win the best paper award this year. The paper is joint work with Danupon Nanongkai at Max Planck Institute and Christian Wulff-Nilsen at University of Copenhagen.
The paper addresses one of the fundamental problems of algorithmic research: given two points in a graph, what is the shortest path between them? It has been known since the 50's how to solve this problem quickly when all edges in the graph have positive weight (Dijkstra's algorithm), but no similarly fast algorithms were known for graphs where some edges have a negative weight. Aaron's paper closes this gap by showing a new algorithm that is fast even in a graph with negative edge-weights.
