Skip to main content Skip to navigation

News

View the latest news from departments within the Faculty of Science, Engineering and Medicine below.
Select tags to filter on

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

Breakthrough result on the power of memory in computation

A recent paperLink opens in a new window published by Dr. Ian MertzLink opens in a new window, 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 James CookLink opens in a new window 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 56th Annual ACM Symposium on the Theory of Computing (STOC 2024)Link opens in a new window, has been invited to the special issue of SIAM Journal on Computing (SICOMP)Link opens in a new window 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, Warwick (Online Complexity Seminar)Link opens in a new window, McGill University, and others.

Sun 23 Jun 2024, 22:27 | Tags: People Highlight Research Theory and Foundations

News Read more from News

Physics Department News Read more from Physics Department News

News Library Read more from News Library

Four Warwick Chemists win prestigious Royal Society of Chemistry prizes

Professors Reinhard Maurer, Scott Habershon, Tim Bugg, and Sébastien Perrier, have been recognised for their contributions to Chemistry.

Wed 12 Jun 2024, 12:12 | Tags: news PolymerChem people MatPolymers ChemBio Research news CaTCh

Life Sciences News Read more from Life Sciences News

School of Engineering News Read more from School of Engineering News

WMG News Read more from WMG News

Maths Read more from Mathematics Institute News

News from Medical School Read more from Latest News

Psychology Read more from Psychology News