ERC Advanced Grant · 2023
Exact and Approximate Computation of Tensors and Polynomials
This research proposal will address fundamental problems concerning the complexity of computing and manipulating polynomials. For example, consider the following questions: 1. What is the complexity of computing the total weight of perfect matchings of a weighted graph? 2. Is there an efficient deterministic parallel algorithm that determines whether a graph has a perfect matching? 3. Is approximation much easier than exact computation? 4. How many EPR pairs can we distill from a given quantum state? 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…
From the public funding record at EU CORDIS. Describes the funded project, not the reviews below.