Theory and Foundations News
Archive news content can be found here.
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
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.
https://www.dcs.warwick.ac.uk/~u2270030/wactLink 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.
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.