91福利

A published by , a postdoctoral researcher in the Theory and Foundations (FoCS)Link opens in a new window research group and the Centre for Discrete Mathematics and its Applications (DIMAP)Link opens in a new window, has disproved a longstanding conjecture on the limitations of space-bounded computation.

For many years it had been believed that a function, known as Tree Evaluation, would be the key to separating two fundamental classes of problems: those computable quickly (P), and those computable in low space (L). Mertz, along with of Toronto, builds on their earlier work to show a low-space algorithm for Tree Evaluation, thus refuting this belief. In particular, their technique has attracted attention for shedding new light on the power of space-bounded computation, suggesting novel approaches to age-old questions in complexity theory. They show that space can be used in surprising ways, with the same memory serving many simultaneous purposes.

The paper, which Mertz will present at the , has been invited to the special issue of for the conference. STOC is the main conference of the Association of Computing Machinery (ACM) and one of the two premier venues for theoretical computer science, with only the top results being invited for publication in the special issue.

Mertz has also presented this work at many venues, including the Institute for Advanced Study (IAS), Columbia University, Oxford University, 91福利 (, McGill University, and others.

We are happy to announce two recent promotions in the department effective from 1 August 2024:

• Dr Amina Asif has been promoted to Assistant Professor
• Dr Andrew Hague has been promoted to Associate Professor

Many congratulations to our colleagues for their achievements!

The work of Professor Graham Cormode has been recognized with a 鈥渢est of time鈥� award. The ACM SIGMOD conference presents an award each year for the paper from SIGMOD 10-12 years previously that has had the biggest impact, and passed the 鈥渢est-of-time鈥�. The 2014 paper 鈥淧rivBayes: private data release via bayesian networks鈥� (Jun Zhang, Graham Cormode, Cecilia M. Procopiuc, Divesh Srivastava, Xiaokui Xiao) was selected for this honour. The award will be presented at the 2024 ACM SIGMOD Conference in Santiago.