A research paper presented by two students of Tata Institute of Fundamental Research (TIFR) was recently adjudged “the best student paper” at the 52nd annual ACM Symposium on Theory of Computing (STOC2020). “This is the first time that a paper authored by students at an Indian university has received this honour at the symposium,” said a statement by TIFR. The conference, which was to be held in Chicago in June, was organised virtually, where Siddharth Bhandari and Sayantan Chakraborty received the honour. Titled “Improved Bounds for Perfect Sampling of k-Colourings in Graphs,” the research paper attempts to provide a solution to an age-old problem. “Map colouring is an example, where researchers try to find a solution to the problem of how to colour a map in a way that no two neighbouring countries have the same colour while computing. The algorithm helps researchers in computer science to allocate minimum resources for a conflict-free assignment.,” said Chakraborty. Presently, the algorithm can be applicable to the theoretical field of statistical physics, Bhandari said, adding, “Complex tasks like air traffic scheduling, or designing timetables are some areas where the algorithm can help provide average statistical information.”
