Computer Science News
Amina Asif joins the department as a Teaching Fellow
We are happy to announce that Dr Amina Asif has joined the Department of Computer Science as a Teaching Fellow. Amina has previously worked with us as part of the Tissue Image Analytics (TIA) centre, where her research focussed on weak supervision and model robustness in Computational Pathology. We welcome her to the department!
Cambridge-Oxford-Warwick Quantum Computing Project
An EPSRC Robust and Reliable Quantum Computing Grant will be awarded to Anuj Dawar (Cambridge), Tom Gur (Warwick), Tom Melham (Oxford), and Sergii Strelchuk (Cambridge). The project sets out to explore the role of symmetry and structure in quantum computation, with applications to classical verification and simulation of quantum computation.
In addition, the project aims to strengthen and create new connections and collaborations between Cambridge, Oxford, and Warwick in the field of Quantum Computing (building on existing initiatives such as the Cambridge-Warwick Quantum Colloquium) and establish new partnerships with Warwick Quantum.
5+ papers accepted to STOC 2023
Several papers from the Theory and Foundations (FoCS) Research Group and the Centre for Discrete Mathematics and its Applications (DIMAP) have been accepted to the 55th ACM SIGACT Symposium on Theory of Computing (STOC 2023), the ACM flagship conference in theoretical computer science that will be held on June 20-23, 2023 in Orlando, Florida, USA:
- "Kneser graphs are Hamiltonian" by Arturo Merino, Torsten Mütze, and Namrata.
- "A duality between one-way functions and average-case symmetry of information" by Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, and Igor C. Oliveira.
- "Unprovability of strong complexity lower bounds in bounded arithmetic" by Jiatu Li and Igor C. Oliveira.
- "Sublinear algorithms for (1.5+ϵ)-approximate matching" by Sayan Bhattacharya, Peter Kiss, and Thatchaphol Saranurak.
- "Towards the Erdős-Gallai cycle decomposition conjecture" by Matija Bucic and Richard Montgomery.
Further, there are two more accepted papers autored by Shuichi Hirahara, who was affiliated with the department and the FoCS group during the submission time, in Autumn 2022:
- "Capturing one-way functions via NP-hardness of meta-complexity" by Shuichi Hirahara.
- "Hardness self-amplification: Simplified, optimized, and unified" by Shuichi Hirahara and Nobutaka Shimizu.
Prof. Adi Shamir receives Honorary Doctorate from Warwick
Prof. Adi Shamir (Weizmann Institute of Science), the world-renowned cryptographer and a recipient of the ACM Turing Award 2002 (the highest honour in computer science received jointly with Prof. Ronald Rivest and Prof. Leonard M. Adleman), visited our campus in January 2023 to collect an Honorary Doctorate from the University of Warwick. During his visit, Prof. Shamir gave also a research talk at the DIMAP seminar and CS Colloquium entitled "Efficient Detection of High Probability Cryptanalytic Properties of Boolean Functions."
Prof. Shamir has been known in Warwick since 1976, when he spent a year as a post-doc with our own Prof. Mike Paterson. Directly after Warwick Prof. Shamir went to MIT, where together with Adleman and Rivest he invented the famous RSA public-key cryptography algorithm for encoding and decoding messages, used nowadays by millions to securely transmit messages over the internet. The work on RSA has been immensely influential and led to the 2002 A.M. Turing Award for the three co-inventors, cited for the “ingenious contribution for making public-key cryptography useful in practice.” Other noticeable awards (for RSA and other numerous contributions to cryptography and computing) received by Prof. Shamir include the 2000 Institute of Electrical and Electronics Engineers Koji Kobayashi Computers and Communications Award, the Israel Mathematical Union Erdős Prize in Mathematics (1983), the Vatican Pontifical Academy PIUS XI Gold Medal (1992), the Association for Computing Machinery Paris Kannellakis Theory and Practice Award (1996), the Israel Prize in Computer Science (2008), and the Japan Prize in the field of electronics, information, and technology (2017), and the Foreign Member of the Royal Society (2018).
Complexity breakthrough by Dr Shuichi Hirahara
DIMAP Theory Day 2022
On December 12, 2022, we held the DIMAP Theory Day 2022. This event highlighted recent, exciting advances in the field of Algorithms and Complexity and provided means to facilitate interactions within the algorithms research community in the UK. The event was supported by the Centre for Discrete Mathematics and its Applications (DIMAP) and UKRI. We plan to hold further events in this series on a regular basis.
See more details at the DIMAP Theory Day 2022 page
Outstanding MSc students
The department would like to congratulate our 2021-2022 MSc students on their end-of-year results. Additional congratulations go to the following outstanding students, who have been awarded academic prizes: