Data Science News
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).
Outstanding MSc students
The department would like to congratulate our 2021-2022 MSc students on their end-of-year results. Additional congratulations go to the following outstanding students, who have been awarded academic prizes:
|
|
|
|
|
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.