Dr Sagnik Mukhopadhyay and Dr Christian Coester have both had papers accepted for the symposium, which is one of the most prestigious conferences in the world on the theory that underpins computing:
1. Cut Query Algorithms with Star Contraction by Dr. Sagnik Mukhopadhyay at Sheffield with coauthors Y. Efron, D. Nanongkai, S. Apers, T. Lee, P. Gawrychowski.
2. Nearly Optimal Communication and Query Complexity of Bipartite Matching by Dr. Sagnik Mukhopadhyay at Sheffield with coauthors J. Blikstad, J. van den Brand, Y. Efron, D. Nanongkai.
Both papers deal with fundamental graph algorithms, such as graph connectivity and bipartite matching, in different (and non-traditional) models of computation, where the full input is not available to the computing processor. Such computing paradigms are extremely relevant currently, due to data explosion and highly connected network computing.
3. Shortest Paths without a Map, but with an Entropic Regularizer by Dr. Christian Coester at Sheffield with coauthors S. Bubeck, Y. Rabani.
This paper solves a 33-year-old open problem which was originally introduced in the 1989 “Shortest Paths Without a Map” paper by Papadimitriou and Yannakakis. The paper deals with a version of the well-known problem where the graph (or ‘map’) is initially unknown and is only discovered over time as the searcher traverses the space. The co-authors provide the theoretically optimal algorithm for the problem by showing how to adapt modern regularisation techniques to a setting where space evolves over time.
This is a great achievement and both Sagnik and Christian should be proud to have their work recognised amongst such illustrious company.
Pietro Oliveto
Department of Computer Science, University of Sheffield
Pietro Oliveto, who is a Professor in Computer Science and Chair of the Department's Algorithms Group, continued: “FOCS, as well as the ACM Symposium on Theory of Computing (STOC), are the most selective and prestigious conferences in the field worldwide. They are widely recognised as the most important venues of publications for theoretical computer science research.
“Our success demonstrates that our rapidly growing Algorithms Group is already establishing itself as an international player of some significance, which is testament to the hard work of all involved.”
Dr Sagnik Mukhopadhyay, Lecturer in Algorithms in the Department of Computer Science, said: “We are pleased that our work has been recognised by the theory community.
“We believe that this is an important area of research - more so in the context of modern computation - and we are happy that we’ve made progress towards our understanding of such computational models.”
Dr Christian Coester, Lecturer in Algorithms in the Department of Computer Science, added: “We’re very happy about the positive feedback received from all reviewers and curious to see whether we can apply our techniques to additional problems.”
FOCS 2022 will be held on October 31—November 3, 2022 in Denver, Colorado, USA.
You can find out more about the Algorithm Research Group here