SubsidieMeestersAlgebraic Formula Lower Bounds and Applications
This project aims to establish lower bounds for algebraic formulas and improve Polynomial Identity Testing algorithms by leveraging structural and algebraic techniques in theoretical computer science.
Projectdetails
Introduction
Does efficient verification imply efficient search? Can randomness provide massive speed-ups in computation? These are fundamental questions in theoretical computer science, known as P vs. NP and P vs. BPP respectively. Progress on these questions requires us to show that certain computational problems are inherently intractable, i.e., do not admit efficient solutions. An important, and concrete, approach to such questions is to understand the complexity of algebraic problems such as the Determinant and the Permanent, in algebraic models of computation. The aim of this project is to tackle these questions head-on.
Recent Progress
Recent results of the PI and his collaborators have made progress on these problems by resolving a three-decade-old open question. These results show intractability for algebraic models of bounded depth, which is a step towards P vs. NP.
As a consequence, they also imply the first sub-exponential time deterministic algorithms for the important Polynomial Identity Testing (PIT) problem in these settings, which is progress towards P vs. BPP.
Future Goals
However, this barely scratches the surface of what we want to achieve. The aim of this project is to push beyond these state-of-the-art results in many directions. The principal goals include:
- Proving the first lower bounds for algebraic formulas, which would be a huge breakthrough.
- Improving our recently obtained lower bounds in order to devise faster PIT algorithms.
- Showing lower bounds over finite fields.
- Exploring the applications of such work in related areas such as algebraic proof complexity and algorithm design.
Methodology
The recent results point out a new way of exploiting structural and algebraic techniques to prove lower bounds. The aim is to develop and systematically investigate these techniques, incorporating methods from related fields of mathematics such as the theory of symmetric functions and representation theory, to accomplish these goals.
Financiële details & Tijdlijn
Financiële details
| Subsidiebedrag | € 1.869.055 |
| Totale projectbegroting | € 1.869.055 |
Tijdlijn
| Startdatum | 1-6-2024 |
| Einddatum | 31-5-2029 |
| Subsidiejaar | 2024 |
Partners & Locaties
Projectpartners
- KOBENHAVNS UNIVERSITETpenvoerder
Land(en)
Vergelijkbare projecten binnen European Research Council
| Project | Regeling | Bedrag | Jaar | Actie |
|---|---|---|---|---|
MANUNKIND: Determinants and Dynamics of Collaborative ExploitationThis project aims to develop a game theoretic framework to analyze the psychological and strategic dynamics of collaborative exploitation, informing policies to combat modern slavery. | ERC STG | € 1.497.749 | 2022 | Details |
Elucidating the phenotypic convergence of proliferation reduction under growth-induced pressureThe UnderPressure project aims to investigate how mechanical constraints from 3D crowding affect cell proliferation and signaling in various organisms, with potential applications in reducing cancer chemoresistance. | ERC STG | € 1.498.280 | 2022 | Details |
Uncovering the mechanisms of action of an antiviral bacteriumThis project aims to uncover the mechanisms behind Wolbachia's antiviral protection in insects and develop tools for studying symbiont gene function. | ERC STG | € 1.500.000 | 2023 | Details |
The Ethics of Loneliness and SociabilityThis project aims to develop a normative theory of loneliness by analyzing ethical responsibilities of individuals and societies to prevent and alleviate loneliness, establishing a new philosophical sub-field. | ERC STG | € 1.025.860 | 2023 | Details |
MANUNKIND: Determinants and Dynamics of Collaborative Exploitation
This project aims to develop a game theoretic framework to analyze the psychological and strategic dynamics of collaborative exploitation, informing policies to combat modern slavery.
Elucidating the phenotypic convergence of proliferation reduction under growth-induced pressure
The UnderPressure project aims to investigate how mechanical constraints from 3D crowding affect cell proliferation and signaling in various organisms, with potential applications in reducing cancer chemoresistance.
Uncovering the mechanisms of action of an antiviral bacterium
This project aims to uncover the mechanisms behind Wolbachia's antiviral protection in insects and develop tools for studying symbiont gene function.
The Ethics of Loneliness and Sociability
This project aims to develop a normative theory of loneliness by analyzing ethical responsibilities of individuals and societies to prevent and alleviate loneliness, establishing a new philosophical sub-field.
Vergelijkbare projecten uit andere regelingen
| Project | Regeling | Bedrag | Jaar | Actie |
|---|---|---|---|---|
Foundations of transcendental methods in computational nonlinear algebraDevelop new computational methods in nonlinear algebra using algebraic geometry to enhance the precision and reliability of numerical integration and algebraic invariant computation. | ERC STG | € 1.393.312 | 2022 | Details |
Parameterized Complexity Through the Lens of Path ProblemsThis project aims to unify the theory of parameterized path problems by connecting various mathematical fields to develop efficient algorithms and answer longstanding questions in NP-hard problem complexity. | ERC STG | € 1.499.821 | 2022 | Details |
The Hardness of Finding Good AlgorithmsThe project investigates the difficulty of finding efficient algorithms for various computational problems, aiming to establish lower bounds and connections to cryptography and learning theory. | ERC STG | € 1.498.664 | 2023 | Details |
Integrable ProbabilityThis project explores integrable probability by applying advanced mathematical methods to stochastic models, aiming to derive precise limit theorems and enhance understanding of random walks and representations. | ERC STG | € 1.083.750 | 2022 | Details |
Foundations of transcendental methods in computational nonlinear algebra
Develop new computational methods in nonlinear algebra using algebraic geometry to enhance the precision and reliability of numerical integration and algebraic invariant computation.
Parameterized Complexity Through the Lens of Path Problems
This project aims to unify the theory of parameterized path problems by connecting various mathematical fields to develop efficient algorithms and answer longstanding questions in NP-hard problem complexity.
The Hardness of Finding Good Algorithms
The project investigates the difficulty of finding efficient algorithms for various computational problems, aiming to establish lower bounds and connections to cryptography and learning theory.
Integrable Probability
This project explores integrable probability by applying advanced mathematical methods to stochastic models, aiming to derive precise limit theorems and enhance understanding of random walks and representations.