Skip to main content Skip to navigation

Computer Science News

Select tags to filter on

DIMAP Theory Day 2022

On December 12, 2022, we held the DIMAP Theory Day 2022. This event highlighted recent, exciting advances in the field of Algorithms and Complexity and provided means to facilitate interactions within the algorithms research community in the UK. The event was supported by the Centre for Discrete Mathematics and its Applications (DIMAP) and UKRI. We plan to hold further events in this series on a regular basis.

See more details at the DIMAP Theory Day 2022 page

Wed 18 Jan 2023, 18:57 | Tags: Conferences Theory and Foundations

Workshop on Algebraic Complexity Theory (WACT)

The University of Warwick will be hosting the Seventh Workshop on Algebraic Complexity Theory (WACT) from March 27 to March 31, 2023. opens in a new window

Algebraic Complexity Theory is a vibrant field that has been seeing a tremendous amount of activity in the recent years. Its classical questions have been interwoven with deep questions from algebraic geometry, invariant theory, and representation theory. Researchers study a wide range of interlinked topics: arithmetic circuit lower bounds, algorithmic algebra, algorithmic invariant theory, geometric complexity theory, tensor rank, polynomial identity testing, and polynomial reconstruction, to name a few. The workshop brings together experts from different parts of this rich field to discuss the current state of the art, discover new connections, and set the directions for the future.

Sat 26 Nov 2022, 23:59 | Tags: Conferences Theory and Foundations

Warwick Quantum papers accepted to the top quantum conference QIP

Two papers by members of Warwick Quantum were accepted to QIP 2023, the most prestigious conference in Quantum Computing and Quantum Information.

These works provide a methodology for boosting the power of quantum algorithms using deep mathematical tools from additive combinatorics, as well as provide the techniques, tools, and abstractions necessary to answer when classical zero-knowledge protocols remain secure against quantum attacks.

  • "Quantum Worst-Case to Average-Case Reductions for All Linear Problems" by Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, and Sathyawageeswar Subramanian.
  • "Post-Quantum Zero Knowledge, Revisited" by Alex Lombardi, Fermi Ma and Nicholas Spooner.
Fri 25 Nov 2022, 17:43 | Tags: Research Theory and Foundations

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.

Wed 23 Nov 2022, 07:39 | Tags: Highlight Research Theory and Foundations

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!

Wed 09 Nov 2022, 12:49 | Tags: People Highlight Theory and Foundations

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.

Wed 19 Oct 2022, 21:55 | Tags: Highlight Research Theory and Foundations

Ian Mertz joins the department as a Research Fellow

We're happy to announce that Ian Mertz has joined the department as a Research Fellow. He is currently funded by the project "New approaches to unconditional computational lower bounds", with support from the Royal Society.

Ian Mertz completed his PhD at the University of Toronto in 2022 under the supervision of Toniann Pitassi, with stints at the Simons Institute for the Theory of Computing (UC Berkeley) and at the Institute for Advanced Study in Princeton.

Ian's primary research area is computational complexity theory. His interests at the moment include catalytic computing, lifting theorems, arithmetic circuit complexity, and proof complexity.

Tue 11 Oct 2022, 09:19 | Tags: People Highlight Theory and Foundations

Older news