EPSRC Reference: 
EP/V003542/1 
Title: 
Probabilistic and Topological methods in Real Algebraic Geometry and Computational Complexity 
Principal Investigator: 
Natarajan, Mr A 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
Mathematics 
Organisation: 
University of Warwick 
Scheme: 
EPSRC Fellowship 
Starts: 
01 March 2021 
Ends: 
29 February 2024 
Value (£): 
299,943

EPSRC Research Topic Classifications: 
Algebra & Geometry 
Logic & Combinatorics 

EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 

Summary on Grant Application Form 
Algebraic geometry is concerned with the study of the zeros of polynomials (called varieties). Besides being prominent in pure mathematics, it has applications in a plethora of areas such as physics, computational geometry, and machine learning. This proposal aims to study topological properties of certain kinds of varieties, with a view toward applications in incidence combinatorics and computational complexity theory.
Our first direction is the topological study of random polynomials. Studying random polynomials represents a shift in algebraic geometry  instead of worstcase analysis, which, for example, asks for the largest possible number of points in an intersection of curves, randomness gives an averagecase understanding, thus providing a more realistic view. Via Erdos' astonishing 'probabilistic method', one can obtain deterministic results by introducing randomness into a question that apriori had nothing to do with randomness. We focus on a probability distribution on the space of homogeneous polynomials, which is an actively studied probability distribution with strong algebrogeometric significance.
Specifically, we are interested in bounds on the topological complexity, as measured by Betti numbers, of random varieties restricted to sets in ominimal geometry. Ominimal geometry is a framework in which sets (called definable sets) more general than varieties are allowed. The field of ominimal incidence geometry, which involves combinatorial questions about definable sets, is badly in need of a polynomial partitioning theorem  a tool which has been a panacea in traditional incidence geometry. However, it has proved difficult because the worstcase topological complexity of definable sets restricted to varieties can be "bad".
We propose to study the averagecase complexity of definable sets restricted to random varieties instead. By doing so, we hope to demonstrate that topologically "bad" polynomials are unusual (we have already proved this for certain definable sets). Thus, if the measure of polynomials suitable for partitioning is large enough, we will have proved the existence of a partitioning polynomial, with "good" topological complexity, via the probabilistic method. This will provide a tremendous boost to ominimal incidence geometry.
Our second direction is algebrotopological questions with applications in computational complexity theory. Computational complexity theory is a mathematical area that classifies problems according to the resources required to solve them. The most important open question in the field is the exceedingly difficult P vs NP problem. There has been a recent impetus towards the problem, under the Geometric Complexity Theory (GCT) program, which involves casting related problems in algebraic language. The hope is that advanced tools in the fertile areas of algebraic geometry and representation theory will allow us to make progress on the problem.
The central objective of the GCT program is to separate certain spaces called orbit closures. While that is obviously a lofty aim, our goal is to compute the topology of these orbit closures. Computing the topology helps in obtaining a coarse understanding of the geometry of the objects involved. Also, it is well known that obtaining quantitative bounds on the topology of a space helps in understanding the fundamental limitations of computational procedures that operate on the space.
We shall also study the notion of Ulrich complexity, which quantifies the 'complexity' of polynomials in a different way. While it is conveniently defined using commutativealgebraic notions, and is evidently easier to work with, little is understood about it in general. We shall investigate the average Ulrich complexity of Kostlan polynomials. It is known that obtaining lower bounds on the Ulrich complexity of polynomials could potentially have implications on an important conjecture in commutative algebra, as well as the P vs NP problem.

Key Findings 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Potential use in nonacademic contexts 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Impacts 
Description 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk 
Summary 

Date Materialised 


Sectors submitted by the Researcher 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Project URL: 

Further Information: 

Organisation Website: 
http://www.warwick.ac.uk 