Project acronym FEALORA
Project "Feasibility, logic and randomness in computational complexity"
Researcher (PI) Pavel Pudlák
Host Institution (HI) MATEMATICKY USTAV AV CR V.V.I.
Call Details Advanced Grant (AdG), PE6, ERC-2013-ADG
Summary "We will study fundamental problems in complexity theory using means developed in logic, specifically, in the filed of proof complexity. Since these problems seem extremely difficult and little progress has been achieved in solving them, we will prove results that will explain why they are so difficult and in which direction theory should be developed.
Our aim is to develop a system of conjectures based on the concepts of feasible incompleteness and pseudorandomness. Feasible incompleteness refers to conjectures about unprovability of statements concerning low complexity computations and about lengths of proofs of finite consistency statements. Essentially, they say that incompleteness in the finite domain behaves in a similar way as in the infinite. Several conjectures of this kind have been already stated. They have strong consequences concerning separation of complexity classes, but only a few special cases have been proved. We want to develop a unified system which will also include conjectures connecting feasible incompleteness with pseudorandomness. A major part of our work will concern proving special cases and relativized versions of these conjectures in order to provide evidence for their truth. We believe that the essence of the fundamental problems in complexity theory is logical, and thus developing theory in the way described above will eventually lead to their solution."
Summary
"We will study fundamental problems in complexity theory using means developed in logic, specifically, in the filed of proof complexity. Since these problems seem extremely difficult and little progress has been achieved in solving them, we will prove results that will explain why they are so difficult and in which direction theory should be developed.
Our aim is to develop a system of conjectures based on the concepts of feasible incompleteness and pseudorandomness. Feasible incompleteness refers to conjectures about unprovability of statements concerning low complexity computations and about lengths of proofs of finite consistency statements. Essentially, they say that incompleteness in the finite domain behaves in a similar way as in the infinite. Several conjectures of this kind have been already stated. They have strong consequences concerning separation of complexity classes, but only a few special cases have been proved. We want to develop a unified system which will also include conjectures connecting feasible incompleteness with pseudorandomness. A major part of our work will concern proving special cases and relativized versions of these conjectures in order to provide evidence for their truth. We believe that the essence of the fundamental problems in complexity theory is logical, and thus developing theory in the way described above will eventually lead to their solution."
Max ERC Funding
1 259 596 €
Duration
Start date: 2014-01-01, End date: 2018-12-31
Project acronym LBCAD
Project Lower bounds for combinatorial algorithms and dynamic problems
Researcher (PI) Michal Koucky
Host Institution (HI) UNIVERZITA KARLOVA
Call Details Consolidator Grant (CoG), PE6, ERC-2013-CoG
Summary This project aims to establish the time complexity of algorithms for two classes of problems. The first class consists of problems related to Boolean matrix multiplication and matrix multiplication over various semirings. This class contains problems such as computing transitive closure of a graph and determining the minimum distance between all-pairs of nodes in a graph. Known combinatorial algorithms for these problems run in slightly sub-cubic time. By combinatorial algorithms we mean algorithms that do not rely on the fast matrix multiplication over rings. Our goal is to show that the known combinatorial algorithms for these problems are essentially optimal. This requires designing a model of combinatorial algorithms and proving almost cubic lower bounds in it.
The other class of problems that we will focus on contains dynamic data structure problems such as dynamic graph reachability and related problems. Known algorithms for these problems exhibit trade-off between the query time and the update time, where at least one of them is always polynomial. Our goal is to show that indeed any algorithm for these problems must have update time or query time at least polynomial.
The two classes of problems are closely associated with so called 3SUM problem which serves as a benchmark for uncomputability in sub-quadratic time. Our goal is to deepen and extend the known connections between 3SUM, the other two classes and problems like formula satisfiability (SAT).
Summary
This project aims to establish the time complexity of algorithms for two classes of problems. The first class consists of problems related to Boolean matrix multiplication and matrix multiplication over various semirings. This class contains problems such as computing transitive closure of a graph and determining the minimum distance between all-pairs of nodes in a graph. Known combinatorial algorithms for these problems run in slightly sub-cubic time. By combinatorial algorithms we mean algorithms that do not rely on the fast matrix multiplication over rings. Our goal is to show that the known combinatorial algorithms for these problems are essentially optimal. This requires designing a model of combinatorial algorithms and proving almost cubic lower bounds in it.
The other class of problems that we will focus on contains dynamic data structure problems such as dynamic graph reachability and related problems. Known algorithms for these problems exhibit trade-off between the query time and the update time, where at least one of them is always polynomial. Our goal is to show that indeed any algorithm for these problems must have update time or query time at least polynomial.
The two classes of problems are closely associated with so called 3SUM problem which serves as a benchmark for uncomputability in sub-quadratic time. Our goal is to deepen and extend the known connections between 3SUM, the other two classes and problems like formula satisfiability (SAT).
Max ERC Funding
900 200 €
Duration
Start date: 2014-02-01, End date: 2019-01-31
Project acronym THEMODS
Project Theories and Models of the Dark Sector: Dark Matter, Dark Energy and Gravity
Researcher (PI) Constantinos Skordis
Host Institution (HI) FYZIKALNI USTAV AV CR V.V.I
Call Details Consolidator Grant (CoG), PE9, ERC-2013-CoG
Summary Modern cosmology assumes that General Relativity (GR) is the correct description of gravity on large scales. With this assumption and according to current data, the cosmological model needs in addition the existence of a Dark Sector: Dark Matter (DM) and Dark Energy (DE). We know very little about the nature of DM and it is yet to be detected experimentally. The simplest form of DE compatible with the data, a cosmological constant, has a value incompatible with our understanding of Quantum Field Theory. Given that the extrapolation of GR to cosmological scales has not been tested it is possible that the inference of the Dark Sector also needs to be revised.
I propose to (i) determine the nature of DM and DE to a level not achieved before, (ii) test gravity on cosmological scales and (iii) test the screening of new gravitational degrees of freedom in the solar system. The first two goals will require the use of my general framework to parameterize field equations [Skordis, PRD 79, 123527 (2008); Baker, Ferreira & Skordis, PRD 87, 024015 (2013)]. My team will use this framework to construct simple models and observations to place limits on their parameters. We will employ the Cosmic Microwave Background (CMB) observations from ESA's Planck Surveyor and the Atacama Cosmology Telescope. We will determine the sensitivity of the CMB lensing to the properties of DM and theories of gravity. To break possible degeneracies these data will be supplemented with large-scale structure data, weak lensing and red-shift space distortions. We will also perform forecasting for ESA's EUCLID mission which will give us a handle on how well we will constrain GR with cosmology in the future. For the final goal (iii) we will employ the method of [Padilla & Saffin, JHEP 1207, 122 (2012)] to construct a perturbative expansion of theories that exhibit screening, inside the screening radius. We will determine the compatibility of such theories with solar system and other strong-field data.
Summary
Modern cosmology assumes that General Relativity (GR) is the correct description of gravity on large scales. With this assumption and according to current data, the cosmological model needs in addition the existence of a Dark Sector: Dark Matter (DM) and Dark Energy (DE). We know very little about the nature of DM and it is yet to be detected experimentally. The simplest form of DE compatible with the data, a cosmological constant, has a value incompatible with our understanding of Quantum Field Theory. Given that the extrapolation of GR to cosmological scales has not been tested it is possible that the inference of the Dark Sector also needs to be revised.
I propose to (i) determine the nature of DM and DE to a level not achieved before, (ii) test gravity on cosmological scales and (iii) test the screening of new gravitational degrees of freedom in the solar system. The first two goals will require the use of my general framework to parameterize field equations [Skordis, PRD 79, 123527 (2008); Baker, Ferreira & Skordis, PRD 87, 024015 (2013)]. My team will use this framework to construct simple models and observations to place limits on their parameters. We will employ the Cosmic Microwave Background (CMB) observations from ESA's Planck Surveyor and the Atacama Cosmology Telescope. We will determine the sensitivity of the CMB lensing to the properties of DM and theories of gravity. To break possible degeneracies these data will be supplemented with large-scale structure data, weak lensing and red-shift space distortions. We will also perform forecasting for ESA's EUCLID mission which will give us a handle on how well we will constrain GR with cosmology in the future. For the final goal (iii) we will employ the method of [Padilla & Saffin, JHEP 1207, 122 (2012)] to construct a perturbative expansion of theories that exhibit screening, inside the screening radius. We will determine the compatibility of such theories with solar system and other strong-field data.
Max ERC Funding
1 150 691 €
Duration
Start date: 2014-08-01, End date: 2019-07-31
