News
View the latest news from departments within the Faculty of Science, Engineering and Medicine below.
Faculty of Science, Engineering and Medicine News Read more from Faculty of Science, Engineering and Medicine News
Computer Science News Read more from Computer Science News
6 papers accepted to FOCS 2024
Six papers from the Theory and Foundations Research Group and the Centre for Discrete Mathematics and Its Applications (DIMAP) have been accepted to the 65th IEEE Symposium on Foundations of Computer Science (FOCS 2024), the flagship conference in theoretical computer science that will be held on October 27 - 30, 2024 in Chicago, USA:
- "Reverse Mathematics of Complexity Lower Bounds" by Lijie Chen, Jiatu Li and Igor C. Oliveira.
- "Faster (\Delta+1)-Edge Coloring: Breaking the m\sqrt{n} Time Barrier" by Sayan Bhattacharya, Din Carmon, Martin Costa, Shay Solomon and Tianyi Zhang.
- "Fully Dynamic k-Clustering with Fast Update Time and Small Recourse" by Sayan Bhattacharya, Martin Costa, Naveen Garg, Silvio Lattanzi and Nikos Parotsidis.
- "The Tractability Border of Reachability in Simple Vector Addition Systems with States" by Dmitry Chistikov, Wojciech Czerwiński, Łukasz Orlikowski, Filip Mazowiecki, Henry Sinclair-Banks and Karol Węgrzycki.
- "Optimal Coding Theorems for Randomized Kolmogorov Complexity and Its Applications" by Shuichi Hirahara, Zhenjian Lu and Mikito Nanashima.
- "On the Complexity of Avoiding Heavy Elements" by Zhenjian Lu, Igor C. Oliveira, Hanlin Ren and Rahul Santhanam.