Skip to main content Skip to navigation

Theory and Foundations News

Archive news content can be found here.

Select tags to filter on

Cambridge-Oxford-Warwick Quantum Computing Project

An EPSRC Robust and Reliable Quantum Computing Grant will be awarded to Anuj Dawar (Cambridge), Tom Gur (Warwick), Tom Melham (Oxford), and Sergii Strelchuk (Cambridge). The project sets out to explore the role of symmetry and structure in quantum computation, with applications to classical verification and simulation of quantum computation.

In addition, the project aims to strengthen and create new connections and collaborations between Cambridge, Oxford, and Warwick in the field of Quantum Computing (building on existing initiatives such as the Cambridge-Warwick Quantum Colloquium) and establish new partnerships with Warwick Quantum.

Tue 28 Feb 2023, 13:54 | Tags: Grants Theory and Foundations

5+ papers accepted to STOC 2023

ACM logoSTOC logo SIGACT logo

Several papers from the Theory and Foundations (FoCS) Research Group and the Centre for Discrete Mathematics and its Applications (DIMAP) have been accepted to the 55th ACM SIGACT Symposium on Theory of Computing (STOC 2023), the ACM flagship conference in theoretical computer science that will be held on June 20-23, 2023 in Orlando, Florida, USA:

Further, there are two more accepted papers autored by Shuichi Hirahara, who was affiliated with the department and the FoCS group during the submission time, in Autumn 2022:

  • "Capturing one-way functions via NP-hardness of meta-complexity" by Shuichi Hirahara.
  • "Hardness self-amplification: Simplified, optimized, and unified" by Shuichi Hirahara and Nobutaka Shimizu.
Sun 19 Feb 2023, 12:18 | Tags: Research Theory and Foundations

Prof. Adi Shamir receives Honorary Doctorate from Warwick

Prof. Adi ShamirProf. Adi Shamir (Weizmann Institute of Science), the world-renowned cryptographer and a recipient of the ACM Turing Award 2002 (the highest honour in computer science received jointly with Prof. Ronald Rivest and Prof. Leonard M. Adleman), visited our campus in January 2023 to collect an Honorary Doctorate from the University of Warwick. During his visit, Prof. Shamir gave also a research talk at the DIMAP seminar and CS Colloquium entitled "Efficient Detection of High Probability Cryptanalytic Properties of Boolean Functions."

Prof. Paterson introducing Prof. Shamir in DIMAP seminarProf. Shamir has been known in Warwick since 1976, when he spent a year as a post-doc with our own Prof. Mike Paterson. Directly after Warwick Prof. Shamir went to MIT, where together with Adleman and Rivest he invented the famous RSA public-key cryptography algorithm for encoding and decoding messages, used nowadays by millions to securely transmit messages over the internet. The work on RSA has been immensely influential and led to the 2002 A.M. Turing Award for the three co-inventors, cited for the “ingenious contribution for making public-key cryptography useful in practice.” Other noticeable awards (for RSA and other numerous contributions to cryptography and computing) received by Prof. Shamir include the 2000 Institute of Electrical and Electronics Engineers Koji Kobayashi Computers and Communications Award, the Israel Mathematical Union Erdős Prize in Mathematics (1983), the Vatican Pontifical Academy PIUS XI Gold Medal (1992), the Association for Computing Machinery Paris Kannellakis Theory and Practice Award (1996), the Israel Prize in Computer Science (2008), and the Japan Prize in the field of electronics, information, and technology (2017), and the Foreign Member of the Royal Society (2018).

Complexity breakthrough by Dr Shuichi Hirahara

Dr Shuichi Hirahara, a research fellow affiliated with the Theory and FoundationsLink opens in a new window group and an Associate Professor at the National Institute of Informatics in Tokyo, has made a significant advance towards our understanding of the limits and possibilities of efficient computations. In his recent paper "NP-Hardness of Learning Programs and Partial MCSP", published at the 63rd IEEE Annual Symposium on Foundations of Computer Science (FOCS 2022), Dr Hirahara established the NP-hardness of learning efficient programs and of estimating the circuit complexity of an explicitly given partial Boolean function. The main result of the paper addresses a question that dates back to the pioneering work of Stephen Cook and Leonid Levin on the theory of NP-completeness from the 1970s.

The new result has been presented at several institutions, including UT Austin, Columbia University, Warwick (Online Complexity Seminar), MIT, and the Simons Institute for the Theory of Computing at UC Berkeley. The latter is running a semester-long program on "Meta-Complexity" that is closely related to Hirahara's recent contributions.

You can read more about it at the popular Computational Complexity Blog, where the discovery has been named "Complexity Result of the Year" (see also Gödel’s Lost Letter and P=NP).
Fri 03 Feb 2023, 17:36 | Tags: People Highlight Research Theory and Foundations

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

Older news