Skip to main content Skip to navigation

Computer Science News

Select tags to filter on

Best Paper Award and 6 papers at ICALP 2024

Six papers co-authored by DIMAP and Theory and Foundations researchers were presented earlier in July at ICALP 2024, the 51st International Colloquium on Automata, Languages, and Programming:

ICALP is the main conference and annual meeting of the European Association for Theoretical Computer Science (EATCS). This year's ICALP took place in Tallinn, Estonia, on the 8th to 12th of July 2024.

Dmitry ChistikovDmitry's paper "Integer Linear-Exponential Programming in NP by Quantifier Elimination" won the Best Paper Award of ICALP's Track B, which is a flagship research meeting on Automata, Logic, Semantics, and Theory of Programming. The paper studies the following problem: given a system of linear equations and constraints of the form y=2x, does it have a solution over the natural numbers? By using and extending a method that generalises Gaussian elimination, Dmitry and his co-authors Alessio Mansutti and Mikhail Starchak show that the problem belongs to the complexity class NP. This result provides a way to efficiently certify the existence of a solution, even if all solutions are very big (towers of exponentials).

This is the second time in a row that this award goes to a Warwick paper: Henry Sinclair-Banks, a DIMAP PhD student, was an awardee in 2023.

Wed 31 Jul 2024, 11:30 | Tags: Conferences Highlight Research Theory and Foundations

Latest academic promotions

We are happy to announce that Dr Florin Ciucu (CS), Dr Long Tran-Thanh (CS) and Dr Paul Jenkins (Statistics and CS) have been promoted to Professor, effective 1st August 2024.

Many congratulations to our colleagues for all their achievements!

 Florin Long Paul

Mon 29 Jul 2024, 16:00 | Tags: People Highlight

DCS Summer BBQ

The Department of Computer Science celebrated the end of the academic year with a staff BBQ, along with some games of rounders and a tug of war.

Thank you everyone for your hard work this year!

Thu 18 Jul 2024, 16:00 | Tags: Highlight

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

Latest academic promotions

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

Many congratulations to our colleagues for their achievements!

Wed 19 Jun 2024, 14:17 | Tags: People Highlight

Latest academic promotion

We are happy to announce the recent promotion of Arpan Mukhopadhyay to Associate Professor within our department.
Many congratulations to Arpan for all his achievements!
Mon 22 Apr 2024, 02:04 | Tags: People Highlight

New Computer Science programme with the Kharkiv National University of Radio Electronics (NURE)

The University of Warwick will launch a new Computer Science programme with the Kharkiv National University of Radio Electronics (NURE) this September. This announcement coincides with the second anniversary of the University of Warwick's official twinning with NURE (29 Mar). The full story is available hereLink opens in a new window.

Wed 10 Apr 2024, 13:51 | Tags: Courses Highlight Research Faculty of Science

Older news