Constraint-solving-based program invariant synthesis takes a parametric invariant template and encodes the (inductive) invariant conditions into constraints. The problem of characterizing the set of all valid parameter assignments is referred to as the strong invariant synthesis problem , while the problem of finding a concrete valid parameter assignment is called the weak invariant synthesis problem . For both problems, the challenge lies in solving or reducing the encoded constraints, which are generally non-convex and lack efficient solvers. In this article, we propose two novel algorithms for synthesizing invariants of polynomial programs using semidefinite programming (SDP): (1) The Cluster algorithm targets the strong invariant synthesis problem for polynomial invariant templates. Leveraging robust optimization techniques, it solves a series of SDP relaxations and yields a sequence of increasingly precise under-approximations of the set of valid parameter assignments. We prove the algorithm’s soundness, convergence, and weak completeness under a specific robustness assumption on templates. Moreover, the outputs can simplify the weak invariant synthesis problem. (2) The Mask algorithm addresses the weak invariant synthesis problem in scenarios where the aforementioned robustness assumption does not hold, rendering the Cluster algorithm ineffective. It identifies a specific subclass of invariant templates, termed masked templates, involving parameterized polynomial equalities and known inequalities. By applying variable substitution, the algorithm transforms constraints into an equivalent form amenable to SDP relaxations. Both algorithms have been implemented and demonstrated superior performance compared to state-of-the-art methods in our empirical evaluation.

Algebraic boundaries of convex semi-algebraic sets are closely related to polynomial optimization problems. Building upon Rainer Sinn’s work, we refine the stratification of iterated singular loci to a Whitney (a) stratification, which gives a list of candidates of varieties whose dual is an irreducible component of the algebraic boundary of the dual convex body. We also present an algorithm based on Teissier’s criterion to compute Whitney (a) stratifications, which employs conormal spaces and prime decomposition.

In [IEEE Trans. Information Theory, vol. 67, nr. 1 (2021)] we have presented error-correcting algorithms that interpolate sparse univariate polynomials from values at arguments which the algorithms compute. We have assumed that the input polynomials are sparse in terms that are powers of the variable (standard basis) or sparse in Chebyshev basis polynomials. We recover all polynomials of sparsity ≤ B that from our N input points interpolate at least N − E of the points, that is, correct ≤ E errors in the values at the error capacity E/N. Our IEEE Transactions algorithms have, roughly, an error capacity of 0.75/B for power basis and 0.66/B for Chebyshev basis.

Multiplicity code decoders are based on Hermite polynomial interpolation with error correction. In order to have a unique Hermite interpolant one assumes that the field of scalars has characteristic 0 or ≥ 𝓁 +1, where 𝓁 is the maximum order of the derivatives in the list of values of the polynomial and its derivatives which are interpolated. For scalar fields of characteristic 𝓁+1, the minimum number of values for interpolating a polynomial of degree ≤ D is D+1+2E(𝓁+1) when ≤ E of the values are erroneous. Here we give an error-correcting Hermite interpolation algorithm that requires fewer values, that is, that can tolerate more errors, assuming that the characteristic of the scalar field is either 0 or ≥ D+1. Our algorithm requires (𝓁+1)D + 1 - (𝓁+1)𝓁/2 + 2E values.

We present sparse interpolation algorithms for recovering a polynomial with ≤ B terms from N evaluations at distinct values for the variable when ≤ E of the evaluations can be erroneous. Our algorithms perform exact arithmetic in the field of scalars K and the terms can be standard powers of the variable or Chebyshev polynomials, in which case the characteristic of K is ≠ 2. Our algorithms return a list of valid sparse interpolants for the N support points and run in polynomial-time. For standard power basis our algorithms sample at N = ⌊4/3 E + 2⌋B points, which are fewer points than N = 2(E + 1)B - 1 given by Kaltofen and Pernet in 2014. For Chebyshev basis our algorithms sample at N = ⌊3/2E + 2⌋B points, which are also fewer than the number of points required by the algorithm given by Arnold and Kaltofen in 2015, which has N = 74⌊E/13 +1⌋ for B = 3 and E ≥ 222. Our method shows how to correct 2 errors in a block of 4B points for standard basis and how to correct 1 error in a block of 3B points for Chebyshev Basis.

Let f= (f1, ..., fs) be a sequence of polynomials in Q[X1,...,Xn] of maximal degree D and V⊂ Cn be the algebraic set defined by f and r be its dimension. The real radical re < f > associated to f is the largest ideal which defines the real trace of V . When V is smooth, we show that re < f >, has a finite set of generators with degrees bounded by V. Moreover, we present a probabilistic algorithm of complexity (snDn )O(1) to compute the minimal primes of re < f >. When V is not smooth, we give a probabilistic algorithm of complexity sO(1) (nD)O(nr2r) to compute rational parametrizations for all irreducible components of the real algebraic set V ∩ Rn. Experiments are given to show the efficiency of our approaches.