Skip to main content Skip to navigation

Theory and Foundations News

Archive news content can be found here.

Select tags to filter on

Henry Sinclair-Banks successfully defends his PhD thesis

Many congratulations to Henry Sinclair-Banks for passing his PhD viva today, which was one of the shortest and best in the long memories of the examiners, Dr Richard Mayr from the University of Edinburgh, and our own Professor Ranko Lazic.

Wed 21 Aug 2024, 12:06 | Tags: People Research Theory and Foundations

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

6 papers accepted to FOCS 2024

Six papers from the Theory and Foundations Research Group and the Centre for Discrete Mathematics and Its Applications (DIMAP) have been accepted to the 65th IEEE Symposium on Foundations of Computer Science (FOCS 2024), the flagship conference in theoretical computer science that will be held on October 27 - 30, 2024 in Chicago, USA:

  • "Optimal Coding Theorems for Randomized Kolmogorov Complexity and Its Applications" by Shuichi Hirahara, Zhenjian Lu and Mikito Nanashima.
  • "On the Complexity of Avoiding Heavy Elements" by Zhenjian Lu, Igor C. Oliveira, Hanlin Ren and Rahul Santhanam.
Fri 28 Jun 2024, 20:39 | Tags: Research Theory and Foundations

Older news