
The concept of open weak CAD is introduced. Every open CAD is an open weak
CAD. On the contrary, an open weak CAD is not necessarily an open CAD. An
algorithm for computing projection polynomials of open weak CADs is proposed.
The key idea is to compute the intersection of projection factor sets produced
by different projection orders. The resulting open weak CAD often has smaller
number of sample points than open CADs. The algorithm can be used for computing
sample points for all open connected components of $ f\neq0$ for a given
polynomial $f$. It can also be used for many other applications, such as
testing semidefiniteness of polynomials and copositive problems. In fact, we
solved several difficult semidefiniteness problems efficiently by using the
algorithm. Furthermore, applying the algorithm to copositive problems, we find
an explicit expression of the polynomials producing open weak CADs under some
conditions, which significantly improves the efficiency of solving copositive
problems.

Given a zerodimensional ideal I in a polynomial ring, many computations
start by finding univariate polynomials in I. Searching for a univariate
polynomial in I is a particular case of considering the minimal polynomial of
an element in P/I. It is well known that minimal polynomials may be computed
via elimination, therefore this is considered to be a "resolved problem". But
being the key of so many computations, it is worth investigating its meaning,
its optimization, its applications (e.g. testing if a zerodimensional ideal is
radical, primary or maximal). We present efficient algorithms for computing the
minimal polynomial of an element of P/I. For the specific case where the
coefficients are in Q, we show how to use modular methods to obtain a
guaranteed result. We also present some applications of minimal polynomials,
namely algorithms for computing radicals and primary decompositions of
zerodimensional ideals, and also for testing radicality and maximality.

The main purpose of this paper is pedagogical.
Despite its importance, all proofs of the correctness of Strassen's famous
1969 algorithm to multiply two 2x2 matrices with only seven multiplications
involve some basisdependent calculations such as explicitly multiplying
specific 2x2 matrices, expanding expressions to cancel terms with opposing
signs, or expanding tensors over the standard basis. This makes the proof
nontrivial to memorize and many presentations of the proof avoid showing all
the details and leave a significant amount of verifications to the reader.
In this note we give a short, selfcontained, basisindependent proof of the
existence of Strassen's algorithm that avoids these types of calculations. We
achieve this by focusing on symmetries and algebraic properties.
Our proof can be seen as a coordinatefree version of the construction of
Clausen from 1988, combined with recent work on the geometry of Strassen's
algorithm by Chiantini, Ikenmeyer, Landsberg, and Ottaviani from 2016.

Galois field (GF) arithmetic is used to implement critical arithmetic
components in communication and securityrelated hardware, and verification of
such components is of prime importance. Current techniques for formally
verifying such components are based on computer algebra methods that proved
successful in verification of integer arithmetic circuits. However, these
methods are sequential in nature and do not offer any parallelism. This paper
presents an algebraic functional verification technique of gatelevel GF (2m )
multipliers, in which verification is performed in bitparallel fashion. The
method is based on extracting a unique polynomial in Galois field of each
output bit independently. We demonstrate that this method is able to verify an
nbit GF multiplier in n threads. Experiments performed on pre and
postsynthesized Mastrovito and Montgomery multipliers show high efficiency up
to 571 bits.

In this paper we investigate the complexity of model selection and model
testing for dynamical systems with toric steady states. Such systems frequently
arise in the study of chemical reaction networks. We do this by formulating
these tasks as a constrained optimization problem in Euclidean space. This
optimization problem is known as a Euclidean distance problem; the complexity
of solving this problem is measured by an invariant called the Euclidean
distance (ED) degree. We determine closedform expressions for the ED degree of
the steady states of several families of chemical reaction networks with toric
steady states and arbitrarily many reactions. To illustrate the utility of this
work we show how the ED degree can be used as a tool for estimating the
computational cost of solving the model testing and model selection problems.

In 2012, Barbulescu, Detrey, Estibals and Zimmermann proposed a new framework
to exhaustively search for optimal formulae for evaluating bilinear maps, such
as Strassen or Karatsuba formulae. The main contribution of this work is a new
criterion to aggressively prune useless branches in the exhaustive search, thus
leading to the computation of new optimal formulae, in particular for the short
product modulo X 5 and the circulant product modulo (X 5  1). Moreover , we
are able to prove that there is essentially only one optimal decomposition of
the product of 3 x 2 by 2 x 3 matrices up to the action of some group of
automorphisms.

We give an efficient algorithm to enumerate all sets of $r\ge 1$ quadratic
polynomials over a finite field, which remain irreducible under iterations and
compositions.

In this article we determine a generating set of rational invariants of
minimal cardinality for the action of the orthogonal group $\mathrm{O}_3$ on
the space $\mathbb{R}[x,y,z]_{2d}$ of ternary forms of even degree $2d$. The
construction relies on two key ingredients: On one hand, the Slice Lemma allows
us to reduce the problem to dermining the invariants for the action on a
subspace of the finite subgroup $\mathrm{B}_3$ of signed permutations. On the
other hand, our construction relies in a fundamental way on specific bases of
harmonic polynomials. These bases provide maps with prescribed
$\mathrm{B}_3$equivariance properties. Our explicit construction of these
bases should be relevant well beyond the scope of this paper. The expression of
the $\mathrm{B}_3$invariants can then be given in a compact form as the
composition of two equivariant maps. Instead of providing (cumbersome) explicit
expressions for the $\mathrm{O}_3$invariants, we provide efficient algorithms
for their evaluation and rewriting. We also use the constructed
$\mathrm{B}_3$invariants to determine the $\mathrm{O}_3$orbit locus and
provide an algorithm for the inverse problem of finding an element in
$\mathbb{R}[x,y,z]_{2d}$ with prescribed values for its invariants. These are
the computational issues relevant in brain imaging.

The \texttt{StronglyStableIdeals} package for \textit{Macaulay2} provides a
method to compute all saturated strongly stable ideals in a given polynomial
ring with a fixed Hilbert polynomial. A description of the main method and
auxiliary tools is given.

We give a separation bound for the complex roots of a trinomial $f \in
\mathbb{Z}[X]$. The logarithm of the inverse of our separation bound is
polynomial in the size of the sparse encoding of $f$; in particular, it is
polynomial in $\log (\deg f)$. It is known that no such bound is possible for
4nomials (polynomials with 4 monomials). For trinomials, the classical results
(which are based on the degree of $f$ rather than the number of monomials) give
separation bounds that are exponentially worse.As an algorithmic application,
we show that the number of real roots of a trinomial $f$ can be computed in
time polynomial in the size of the sparse encoding of~$f$. The same problem is
open for 4nomials.

ChvatalGomory (CG) cuts and the BienstockZuckerberg hierarchy capture
useful linear programs that the standard bounded degree Lasserre/SumofSquares
SOS hierarchy fails to capture.
In this paper we present a novel polynomial time SOS hierarchy for 0/1
problems with a custom subspace of high degree polynomials (not the standard
subspace of lowdegree polynomials). We show that the new SOS hierarchy
recovers the BienstockZuckerberg hierarchy. Our result implies a linear
program that reproduces the BienstockZuckerberg hierarchy as a polynomial
sized, efficiently constructive extended formulation that satisfies all
constant pitch inequalities. The construction is also very simple, and it is
fully defined by giving the supporting polynomials. Moreover, for a class of
polytopes (e.g. set covering and packing problems), the resulting SOS hierarchy
optimizes in polynomial time over the polytope resulting from any constant
rounds of CGcuts, up to an arbitrarily small error.
Arguably, this is the first example where different basis functions can be
useful in asymmetric situations to obtain a hierarchy of relaxations.

We propose a randomized polynomial time algorithm for computing nontrivial
zeros of quadratic forms in 4 or more variables over $\mathbb{F}_q(t)$, where
$\mathbb{F}_q$ is a finite field of odd characteristic. The algorithm is based
on a suitable splitting of the form into two forms and finding a common value
they both represent. We make use of an effective formula for the number of
fixed degree irreducible polynomials in a given residue class. We apply our
algorithms for computing a Witt decomposition of a quadratic form, for
computing an explicit isometry between quadratic forms and finding zero
divisors in quaternion algebras over quadratic extensions of $\mathbb{F}_q(t)$.

We propose an algorithm for finding zero divisors in quaternion algebras over
quadratic number fields, or equivalently, solving homogeneous quadratic
equations in three variables over $\mathbb{Q}(\sqrt{d})$ where $d$ is a
squarefree integer. The algorithm is randomized and runs in polynomial time if
one is allowed to call oracles for factoring integers.

In this paper we take a look at Automatic Differentiation through the eyes of
Tensor and Operational Calculus. This work is best consumed as supplementary
material for learning tensor and operational calculus by those already familiar
with automatic differentiation. To that purpose, we provide a simple
implementation of automatic differentiation, where the steps taken are
explained in the language tensor and operational calculus.

We propose to consider ensembles of cycles (quadrics), which are
interconnected through conformalinvariant geometric relations (e.g. "to be
orthogonal", "to be tangent", etc.), as new objects in an extended MoebiusLie
geometry. It was recently demonstrated in several related papers, that such
ensembles of cycles naturally parameterise many other conformallyinvariant
objects, e.g. loxodromes or continued fractions. The paper describes a method,
which reduces a collection of conformally invariant geometric relations to a
system of linear equations, which may be accompanied by one fixed quadratic
relation.
To show its usefulness, the method is implemented as a C++ library. It
operates with numeric and symbolic data of cycles in spaces of arbitrary
dimensionality and metrics with any signatures. Numeric calculations can be
done in exact or approximate arithmetic. In the two and threedimensional
cases illustrations and animations can be produced. An interactive Python
wrapper of the library is provided as well.

In this paper, we propose two new deterministic interpolation algorithms for
a sparse multivariate polynomial given as a standard blackbox by introducing
new Kronecker type substitutions. Let $f\in \RB[x_1,\dots,x_n]$ be a sparse
blackbox polynomial with a degree bound $D$. When $\RB=\C$ or a finite field,
our algorithms either have better bit complexity or better bit complexity in
$D$ than existing deterministic algorithms. In particular, in the case of
deterministic algorithms for standard blackbox models, our second algorithm
has the current best complexity in $D$ which is the dominant factor in the
complexity.

Elimination of unknowns in systems of equations, starting with Gaussian
elimination, is a problem of general interest. The problem of finding an a
priori upper bound for the number of differentiations in elimination of
unknowns in a system of differentialalgebraic equations (DAEs) is an important
challenge, going back to Ritt (1932). The first characterization of this via an
asymptotic analysis is due to Grigoriev's result (1989) on quantifier
elimination in differential fields, but the challenge still remained.
In this paper, we present a new bound, which is a major improvement over the
previously known results. We also present a new lower bound, which shows
asymptotic tightness of our upper bound in low dimensions, which are frequently
occurring in applications. Finally, we discuss applications of our results to
designing new algorithms for elimination of unknowns in systems of DAEs.

In this paper, we propose new deterministic and Monte Carlo interpolation
algorithms for sparse multivariate polynomials represented by straightline
programs. Let $f$ be an $n$variate polynomial given by a straightline
program, which has a degree bound $D$ and a term bound $T$. Our deterministic
algorithm is quadratic in $n,T$ and cubic in $\log D$ in the SoftOh sense,
which has better complexities than existing deterministic interpolation
algorithms in most cases. Our Monte Carlo interpolation algorithms have better
complexities than existing Monte Carlo interpolation algorithms and are the
first algorithms whose complexities are linear in $nT$ in the SoftOh sense.
Since $nT$ is a factor of the size of $f$, our Monte Carlo algorithms are
optimal in $n$ and $T$ in the SoftOh sense.

The computation of Gr\"obner bases is an established hard problem. By
contrast with many other problems, however, there has been little investigation
of whether this hardness is robust. In this paper, we frame and present results
on the problem of approximate computation of Gr\"obner bases. We show that it
is NPhard to construct a Gr\"obner basis of the ideal generated by a set of
polynomials, even when the algorithm is allowed to discard a $(1  \epsilon)$
fraction of the generators, and likewise when the algorithm is allowed to
discard variables (and the generators containing them). Our results shows that
computation of Gr\"obner bases is robustly hard even for simple polynomial
systems (e.g. maximum degree 2, with at most 3 variables per generator). We
conclude by greatly strengthening results for the Strong $c$Partial Gr\"obner
problem posed by De Loera et al. Our proofs also establish interesting
connections between the robust hardness of Gr\"obner bases and that of SAT
variants and graphcoloring.

We evaluate a curious determinant, first mentioned by George Andrews in 1980
in the context of descending plane partitions. Our strategy is to combine the
famous DesnanotJacobiDodgson identity with automated proof techniques. More
precisely, we follow the holonomic ansatz that was proposed by Doron Zeilberger
in 2007. We derive a compact and nice formula for Andrews's determinant, and
use it to solve a challenge problem that we posed in a previous paper. By
noting that Andrews's determinant is a special case of a twoparameter family
of determinants, we find closed forms for several oneparameter subfamilies.
The interest in these determinants arises because they count cyclically
symmetric rhombus tilings of a hexagon with several triangular holes inside.

The celebrated integer relation finding algorithm PSLQ has been successfully
used in many applications. PSLQ was only analyzed theoretically for exact input
data, however, when the input data are irrational numbers, they must be
approximate ones due to the finite precision of the computer. When the
algorithm takes empirical data (inexact data with error bounded) instead of
exact real numbers as its input, how do we theoretically ensure the output of
the algorithm to be an exact integer relation?
In this paper, we investigate the PSLQ algorithm for empirical data as its
input. Firstly, we give a termination condition for this case. Secondly, we
analyze a perturbation on the hyperplane matrix constructed from the input data
and hence disclose a relationship between the accuracy of the input data and
the output quality (an upper bound on the absolute value of the inner product
of the exact data and the computed integer relation), which naturally leads to
an error control strategy for PSLQ. Further, we analyze the complexity bound of
the PSLQ algorithm for empirical data. Examples on transcendental numbers and
algebraic numbers show the meaningfulness of our error control strategy.

Computations with integrodifferential operators are often carried out in an
associative algebra with unit, and they are essentially noncommutative
computations. By adjoining a cocommutative coproduct, one can have those
operators perform act on a bialgebra isomorphic to an enveloping algebra. That
gives an adequate framework for a computeralgebra implementation via monoidal
factorization, (pure) transcendence bases and Poincar\'eBirkhoffWitt bases.
In this paper, we systematically study these deformations, obtaining necessary
and sufficient conditions for the operators to exist, and we give the most
general cocommutative deformations of the shuffle coproduct and an effective
construction of pairs of bases in duality. The paper ends by the combinatorial
setting of local systems of coordinates on the group of grouplike series.

In 1992, Wilf and Zeilberger conjectured that a hypergeometric term in
several discrete and continuous variables is holonomic if and only if it is
proper. Strictly speaking the conjecture does not hold, but it is true when
reformulated properly: Payne proved a piecewise interpretation in 1997, and
independently, Abramov and Petkovsek in 2002 proved a conjugate interpretation.
Both results address the pure discrete case of the conjecture. In this paper we
extend their work to hypergeometric terms in several discrete and continuous
variables and prove the conjugate interpretation of the WilfZeilberger
conjecture in this mixed setting.

We present a probabilistic Las Vegas algorithm for computing the local zeta
function of a hyperelliptic curve of genus $g$ defined over $\mathbb{F}_q$. It
is based on the approaches by Schoof and Pila combined with a modeling of the
$\ell$torsion by structured polynomial systems. Our main result improves on
previously known complexity bounds by showing that there exists a constant
$c>0$ such that, for any fixed $g$, this algorithm has expected time and space
complexity $O((\log q)^{cg})$ as $q$ grows and the characteristic is large
enough.

Dfinite functions and Precursive sequences are defined in terms of linear
differential and recurrence equations with polynomial coefficients. In this
paper, we introduce a class of numbers closely related to Dfinite functions
and Precursive sequences. It consists of the limits of convergent Precursive
sequences. Typically, this class contains many wellknown mathematical
constants in addition to the algebraic numbers. Our definition of the class of
Dfinite numbers depends on two subrings of the field of complex numbers. We
investigate how different choices of these two subrings affect the class.
Moreover, we show that Dfinite numbers are essentially limits of Dfinite
functions at the point one, and evaluating Dfinite functions at nonsingular
algebraic points typically yields Dfinite numbers. This result makes it easier
to recognize certain numbers to be Dfinite.