ERC Starting Grant · 2021
The Hardness of Finding Good Algorithms
This is a project in Computational Complexity. The project aims to answer the following question: How hard is it to find a good algorithm for a given computational problem? This question can be asked in several different settings, depending on what one means by "algorithm" (what is the computational model?), "computational problem" (is it a decision problem? a search problem? a communication problem?), and by "good" (do we want an algorithm that uses little time? little memory? few logical gates?). This question has a deep connection with the problem of proving lower-bounds, and in almost every setting where the question has been answered, either the answer was discovered while attempting…
From the public funding record at EU CORDIS. Describes the funded project, not the reviews below.