Properties of Algebraic Systems

Three issues in algebraic complexity.

The first is to prove any non-trivial lower bound on the number and degree of a set Q of polynomials needed to characterize a simple, discrete set S as an intersection of the real algebraic variety Q defines, with a finite precision lattice. This problem enchants me most, but I have made the least progress on it. In particular, I am considering discrete sets S defined as intersection of the integer lattice with special convex polyhedra (in several dimensions).

Find natural (complete) problems in the class referred to as "digital NP^R" of real sets (resp. its "Boolean or discrete part"). This class, intuitively, consists of sets of polynomial systems with n real (resp. small integer) coefficients, which can be recognized as having a real zero, by a prover capable only of digital or Boolean proofs of length polynomial in n, and a verifier capable of unit real arithmetic steps, which runs in polynomial time. One related aim is to give lower bounds on lengths or other parameters of discrete proofs for specific proof systems. (See under a different project for my work on proof complexity lower bounds). Some candidate problems are the following:

• testing if a given multivariate real polynomial is surjective over the reals,
• some geometric constraint questions, such as the question of whether a set of distance constraints between pairs of points can be realized on a plane; and
• constructivizing theorems (such as Fourier-Budan) about real-zero distributions of univariate polynomials (reported in recent paper), by transforming them into a multivariate polynomial system.

The third isssue is of use in both of the above problems, namely to relate models of algebraic computation, including proof systems.