Algebraic Hardness and Applications

This project (AHA) explores the limits of computation: which problems can be solved efficiently and which resist efficient solutions. As many problems such as navigation on networks and training large learning models can be expressed in algebraic terms, AHA adapts this algebraic lens to understand computational limits and finds applications to improve algorithms that rely on random numbers.

Computation underpins daily life, from cryptography to machine learning. Yet we lack a deep understanding of its true power and limits. Uncovering these limits is one of the great scientific challenges of our time. AHA advances foundational knowledge with broad implications for efficient algorithms in the context of secure communication, data handling, and future technologies.

AHA combines mathematics and computer science to develop new theory on limits of algorithms. Given a computational task, I analyse whether it can be solved efficiently using several processors in parallel. This is done by modelling the problem using mathematical tools. The insights from this exploration are further used to design fast and reliable algorithms that do not rely on random numbers.