Advances in Relational Programming and Polynomial Optimization

The field of relational programming and polynomial optimization is witnessing significant developments, with a focus on improving the efficiency and scalability of existing methods. Researchers are exploring new approaches to synthesize loops with branches via algebraic geometry, and to represent positive semi-definite polynomials as sums of squares with rational coefficients. These advancements have the potential to impact various areas, including formal program verification and symbolic computation. Noteworthy papers in this area include:

  • A paper that proposes a novel algorithm for constructing a sum-of-squares decomposition for positive semi-definite polynomials with rational coefficients, ensuring exact arithmetic in formal verification and symbolic computation.
  • A paper that investigates the class of Boolean Promise Constraint Satisfaction Problems with polynomial threshold polymorphisms, obtaining complexity characterization results and hardness conditions.
  • A paper that studies certificates of positivity for univariate polynomials with rational coefficients, improving the best-known bounds for computing rational weighted SOS representations and introducing perturbed SOS certificates.

Sources

Committing to the bit: Relational programming with semiring arrays and SAT solving

From Affine to Polynomial: Synthesizing Loops with Branches via Algebraic Geometry

Logical Approaches to Non-deterministic Polynomial Time over Semirings

On Boolean PCSPs with Polynomial Threshold Polymorphisms

A Novel Algorithm for Representing Positive Semi-Definite Polynomials as Sums of Squares with Rational Coefficients

Positive Univariate Polynomials: SOS certificates, algorithms, bit complexity, and T-systems

Foremost, Fastest, Shortest: Temporal Graph Realization under Various Path Metrics

Built with on top of