Submitted by Rachel Gardner on Wed, 17/04/2024 - 14:15
Stellar speakers and a growing interest in the power of Theoretical Computer Science to shed light on central problems in mathematics and computation made the inaugural Cambridge Algorithms and Complexity Workshop this week a great success.
"We originally planned a small and intimate workshop, but on the day over 120 attendees showed up," said one of the organisers Tom Gur, an Associate Professor here in Algorithms and Complexity.
The workshop received a further boost just days beforehand when its headline speaker Prof Avi Wigderson from Princeton's Institute for Advanced Studies was named as winner of the Turing Award by the Association for Computing Machinery. This is the highest distinction in the field of Computer Science and is often referred to as 'the Nobel Prize of Computing'.
He was one of a number of highly decorated international researchers who were giving talks. They also included Prof Gil Kalai (Hebrew University of Jerusalem), recipient of the 1992 Pólya Prize, the 1993 Erdös Prize, the 1994 Fulkerson Prize and the 2012 Rothschild Prize.
The workshop for researchers from undergraduates to faculty members is the first event in what is planned to be an annual series. Tom hopes it will help to raise the profile of such research, build up the UK community of algorithms and complexity researchers, and encourage them to see Cambridge as a natural meeting point.
The time is ripe for it, he adds, considering the recent surge of interest in algorithms and complexity and, more broadly, theoretical computer science. "Historically, compared to leading US universities, this important area of research has been significantly under-represented in the UK and across Europe," Tom says. "But this is rapidly changing. There has been massive growth recently and we are keen to capitalise on this momentum."
The growth is being fuelled, he says, by a recognition that this field of study has relevance far beyond its own discipline. "It has become clear that fundamental theoretical research can completely redirect the entire course of Computer Science and beyond. Quantum Computing is a notable example: starting as a purely theoretical model, we are now seeing a multi-billion dollar industry arising as this dream becomes a reality."
And that's not the only example of an idea successfully migrating from theoretical possibility to industrial reality.
"Consider the notion of Probabilistically Checkable Proofs (PCPs)," Tom says. "PCPs provide means to encode proofs such that verification can be done, seeminly magically, without reading the entire proof — in fact, by only reading 3 bits."
This idea is now being used in industry to significant effect. "Several start-up companies have recently had great success with this, including StarkWare Industries, a software company specialising in cryptography. StarkWare uses probabilistically checkable proofs to prove that certain transactions in the blockchain were carried out.
In May 2022, the company's estimated value rose to 8 billion dollars, up from 2 billion dollars just six months earlier. So this utterly theoretical notion studied as a part of blue skies research is now having a significant impact on industry."
