Computer Science News
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
Dr Shuichi Hirahara, a research fellow affiliated with the Theory and FoundationsLink opens in a new window group and an Associate Professor at the National Institute of Informatics in Tokyo, has made a significant advance towards our understanding of the limits and possibilities of efficient computations. In his recent paper "NP-Hardness of Learning Programs and Partial MCSP", published at the 63rd IEEE Annual Symposium on Foundations of Computer Science (FOCS 2022), Dr Hirahara established the NP-hardness of learning efficient programs and of estimating the circuit complexity of an explicitly given partial Boolean function. The main result of the paper addresses a question that dates back to the pioneering work of Stephen Cook and Leonid Levin on the theory of NP-completeness from the 1970s.
The new result has been presented at several institutions, including UT Austin, Columbia University, Warwick (Online Complexity Seminar), MIT, and the Simons Institute for the Theory of Computing at UC Berkeley. The latter is running a semester-long program on "Meta-Complexity" that is closely related to Hirahara's recent contributions.
You can read more about it at the popular Computational Complexity Blog, where the discovery has been named "Complexity Result of the Year" (see also Gödel’s Lost Letter and P=NP).
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:
 |
|
 |
|
 |
|
Dr Igor Oliveira awarded an ERC Starting Grant
The European Research Council (ERC) has announced that Dr Igor OliveiraLink opens in a new window is among the winners of its prestigious Starting Grant competition. According to the European Research Council: "The funding is worth in total €636 million and is part of the Horizon Europe programme. It will help excellent younger scientists, who have 2 to 7 years’ experience after their PhDs, to launch their own projects, form their teams and pursue their most promising ideas."
Igor OliveiraLink opens in a new window has been awarded a €1.5M ERC Starting grant for a 5-year project entitled "Synergies Between Complexity and Learning". The project aims to exchange ideas and techniques between Complexity Theory and Learning Theory to accelerate progress in both fields, broaden the arsenal of tools available to attack their open problems, as well as to obtain a deeper understanding of the nature of efficient computation and of its logical aspects.
Two projects in Computer Science and Informatics (PE6 panel) in the United Kingdom were awarded ERC Starting Grants in the 2022 round. The press releaseLink opens in a new window contains more information about the ERC funding programme.
SC22 Best Visualization Award Win for the Full Aero-Engine Compressor Visualization by Warwick Researchers
Numerical simulations and visualizations developed by researchers from the High Performance and Scientific Computing (HPSC) group at Warwick’s Department of Computer Science in collaboration with Rolls-Royce, PPCU Hungary and Universities of Surrey and Birmingham has won the award for the best Visualization in the Scientific Visualization and Data Analytics Showcase at the 2022 Supercomputing (SC) Conference, held in Dallas TX. SC is the premier international conference on supercomputing providing a major forum for presenting the highest level of accomplishments in high-performance computing, networking, storage, and analysis. It is held annually in the US and attended by over 10000 attendees from all over the world.
Christian Ikenmeyer joins the Department of Computer Science and the Warwick Mathematics Institute as a Professor
We are happy to announce that Prof Christian Ikenmeyer joined the Department of Computer Science and the Warwick Mathematics Institute on October 1st 2022. In his research, he combines ideas and challenges from theoretical computer science, algorithmic algebra, algebraic complexity theory, algebraic geometry, representation theory, and algebraic combinatorics. We welcome him to the department!
Best Paper Award at SODA 2023
We are delighted to announce that the paper "Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time", coauthored by Sayan Bhattacharya and Peter Kiss from the Theory and Foundations Research Division at Warwick, along with Thatchaphol Saranurak (University of Michigan) and David Wajc (Stanford University), has received the best paper award at SODA 2023.
Computing a maximum matching in a graph is a fundamental problem in combinatorial optimisation. The paper considers this problem in a dynamic graph, which keeps changing over time via a sequence of edge insertions and deletions. It was a decade-old open question to decide whether one can beat the performance guarantee of the simple greedy algorithm for this problem (which gives 2 approximation), in a dynamic setting. The paper answers this question in the affirmative, and provides the first efficient dynamic algorithm which can maintain a better-than 2 approximation to the size of the maximum matching in the input graph.