Seminal
The magazine and atlas of EU-funded researchA new publication from the web and AI team at Scott Charnley

Atlas / Portugal

European Research Council grant · Running

HOFGA The Hardness of Finding Good Algorithms

Coordinator
Faculdade De Ciencias Da Universidade De Lisboa, Portugal
Runs
1 March 2023 to 29 February 2028
Status
Running
EU funding
€1.5m
Total cost
€1.5m
Partners
3 organisations in 1 countries
Type
European Research Council grant
Grant agreement
101041696

What the project is doing

In the project's own words, from its summary on CORDIS.

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 to prove lower-bounds, or obtaining the answer required the development of new lower-bound methods. It is also known that several variants of the above question are equivalent to fundamental open questions in cryptography, pseudorandomness, and learning theory.

The goal of this project is to answer this question in various settings where the answer is unknown: in circuit complexity, communication complexity, data structures, and algebraic models of computation. For each of these settings, we will either provide explicit methods for finding efficient algorithms, or show that the problem of finding such efficient algorithms is NP-hard.""

Topics

Who is involved

OrganisationCityCountryRole
Faculdade De Ciencias Da Universidade De LisboaLisboaPortugalCoordinator
Fciencias.id - Associacao Para a Investigacao E Desenvolvimento De CienciasLisbonPortugalThird party
Universidade Do PortoPortoPortugalParticipant

Source: CORDIS, European Commission. Data of 5 Nov 2026, reused under the Commission's reuse policy. View on CORDIS · Grant DOI