SubsidieMeestersExact and Approximate Computation of Tensors and Polynomials
This project aims to tackle fundamental challenges in polynomial computation and manipulation, seeking breakthroughs in complexity, algorithms, and quantum information theory.
Projectdetails
Introduction
This research proposal will address fundamental problems concerning the complexity of computing and manipulating polynomials.
Key Questions
For example, consider the following questions:
- What is the complexity of computing the total weight of perfect matchings of a weighted graph?
- Is there an efficient deterministic parallel algorithm that determines whether a graph has a perfect matching?
- Is approximation much easier than exact computation?
- How many EPR pairs can we distill from a given quantum state?
Importance of the Questions
These seemingly unrelated questions represent some of the most important and challenging open problems in theoretical computer science:
- The first is the algebraic analog of the famous P vs. NP problem.
- The second question amounts to asking whether a symbolic matrix associated with the graph has full rank.
- Parallel randomized algorithms for computing this rank are known, but not deterministic ones. This is an instance of the polynomial identity testing (PIT) problem, the most fundamental algebraic derandomization problem.
- The third question asks about the relation between a complexity class and its closure, which lies at the heart of the Geometric Complexity Theory (GCT) program.
- The last question concerns the subrank of a tensor representing the given quantum state. Problems related to the rank of tensors are at the heart of both algebraic complexity and quantum information theory.
Recent Advances
Recent years have seen tremendous advances in our understanding of algebraic computations with new lower bounds, new PIT algorithms, and increasing connections to other branches of computer science and mathematics discovered. Results proved by the PI play an important role in all of these advances.
Project Goals
This project aims to study these and related problems and to develop new methods for solving them. Making progress on any of these problems will constitute a significant breakthrough.
Financiële details & Tijdlijn
Financiële details
| Subsidiebedrag | € 2.335.000 |
| Totale projectbegroting | € 2.335.000 |
Tijdlijn
| Startdatum | 1-5-2024 |
| Einddatum | 30-4-2029 |
| Subsidiejaar | 2024 |
Partners & Locaties
Projectpartners
- TEL AVIV UNIVERSITYpenvoerder
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 |
Algorithms, Security and Complexity for Quantum ComputersThis project aims to develop general techniques for designing quantum algorithms that accommodate early quantum computers' limitations and security needs, enhancing practical applications across various fields. | ERC STG | € 1.499.798 | 2022 | Details |
Signs, polynomials, and reaction networksThis project aims to develop novel mathematical theories in applied algebra to enhance the analysis of biochemical reaction networks through parametrized polynomial equations. | ERC COG | € 1.782.649 | 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.
Algorithms, Security and Complexity for Quantum Computers
This project aims to develop general techniques for designing quantum algorithms that accommodate early quantum computers' limitations and security needs, enhancing practical applications across various fields.
Signs, polynomials, and reaction networks
This project aims to develop novel mathematical theories in applied algebra to enhance the analysis of biochemical reaction networks through parametrized polynomial equations.
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.