Special Session 186: Recent Advances in Symbolic Computation and Applications

Vertically parametrized systems, matroids and positive solutions

Carles Checa University of Copenhagen Denmark Co-Author(s):    Elisenda Feliu

Abstract: We study vertically parametrized polynomial systems, a class of parametrized systems arising in contexts such as chemical reaction network theory. We establish an effective criterion for determining whether an augmented vertical system admits multiple positive zeros for some choice of parameter values. The criterion reduces this question to checking the feasibility of a linear system of equalities and inequalities, providing a sufficient condition for the absence of multiple positive zeros that applies to any augmented vertical system. When the kernel of the coefficient matrix displays a certain sparsity structure, this condition becomes also necessary. In this talk, I will show their connection with the criterion for positive real solutions, as well as related features involving matroids and root counts over the complex torus.

Learnability of Algorithms

Kimon Fountoulakis Computer Science, University of Waterloo Canada Co-Author(s):

Abstract: This talk examines when and how machine learning models can learn to execute algorithms. Such reasoning underpins core tasks such as arithmetic and sorting, which are often used as testbeds for algorithmic reasoning. I present both lower and upper bound results. On the negative side, I show that end-to-end training can be inefficient for learning algorithms, while step-by-step supervision enables efficient learnability. On the positive side, I demonstrate that neural networks can be trained to execute algorithms and general computer instructions exactly. Finally, I quantify their ensemble complexity, which provides a lower bound on the number of independent training runs required to achieve zero error. These results indicate when algorithmic behavior is learnable in practice and when structural barriers make it provably hard.

E*-Groebner Bases via Homogenization and Applications to Bivariate Difference Dimension Polynomials

Alexander Levin Catholic University of America USA Co-Author(s):

Abstract: We present a homogeneous Groebner theoretic framework for E*-Groebner bases in difference modules and applications to bivariate difference dimension polynomials. The approach uses graded homogenization in which the homogenizing variable z is taken to be the greatest variable. With this choice homogeneous leading terms encode affine coleaders and homogeneous reduction dehomogenizes naturally to E*-reduction. This yields a Buchberger type algorithm for E*-Groebner bases via homogenization and saturation placing effective order methods into a standard Groebner basis framework. Using these bases we construct bivariate difference dimension polynomials for finitely generated difference modules and difference field extensions. While the classical univariate dimension polynomial measures total order growth the bivariate polynomial describes how growth is distributed across order windows. We prove that certain coefficients are generator independent invariants refining the classical theory. These invariants distinguish nonisomorphic difference modules and detect nonequivalence of systems sharing identical invariants of univariate dimension polynomials.

Groebner bases, Grassmannians, and Low-Rank Matrix Completion

Manolis Tsakiris Chinese Academy of Sciences Peoples Rep of China Co-Author(s):

Abstract: Low-rank matrix completion is an interdisciplinary problem across statistics, machine learning and signal processing, in which the objective is to complete a partially observed m x n matrix of typically small rank r. A fundamental question is which observation patterns admit finitely many completions of rank r, and among them, which ones admit a unique completion. This can be recast as a problem in algebraic geometry, where one aims to determine whether a system of polynomial equations with coefficients rational functions in the observed entries has finitely many solutions (or even a unique solution). We will report families of finitely and uniquely completable patterns for any matrix size and any rank, which we have obtained by 1) interpreting low-rank matrix completion as a linear section problem on the Grassmannian and 2) using families of local coordinates on the Grassmannian that Sturmfels & Zelevinsky desribed in 1993.

Condition-based Low-Degree Approximation of Real Polynomial Systems. I: The Zero-Dimensional Case

Elias Tsigaridas Inria Paris and Sorbonne University France Co-Author(s):    Josue Tonelli-Cueto

Abstract: We provide new bounds on the number of real zeros of a (zero-dimensional) polynomial system in terms of the condition number of the system. In the probabilistic setting, this translates into new estimates on all the moments of the number of the real zeros of random polynomial systems, including Kac and KSS polynomial systems. Moreover, the provided bounds are robust: they do not require the Gaussian assumption.

Integer multiplication is at least as hard as matrix transposition

Joris van der Hoeven CNRS, Ecole polytechnique France Co-Author(s):

Abstract: Working in the multitape Turing model, we show how to reduce the problem of matrix transposition to the problem of integer multiplication. If transposing an $n \times n$ binary matrix requires $\Omega(n^2 \log n)$ steps on a Turing machine, then our reduction implies that multiplying $n$-bit integers requires $\Omega(n \log n)$ steps. In other words, if matrix transposition is as hard as expected, then integer multiplication is also as hard as expected.

ReLU and Softplus neural nets as zero-sum, turn-based, stopping games

Ioannis Vlassopoulos Athena Research Center Greece Co-Author(s):    Stephane Gaubert

Abstract: Neural networks are generally treated as black boxes. In an effort to uncover the mathematical structure underlying them, we explain how ReLU nets can be interpreted as zero-sum turn-based, stopping games. The game runs in the opposite direction to the net and running the net is the same thing as running the Shapley- Bellman backwards recursion for the value of the game. Net weights are used to define state transition probabilities and the biases define rewards. The input to the net is the terminal reward of the game, the output of any neuron is the value of the game at a corresponding game state. We will explain applications of this construction, among which is the calculation of interval bounds for the output of every neuron given interval bounds for the input to the net. Another is the interpretation of a ReLU net classifier as a game between 2 players, one of which is trying to prove the input is in a given class and the other trying to prove the opposite. Adding an entropic regularization to the ReLU net game allows us to interpret Softplus nets as games analogously. This is joint work with St\`ephane Gaubert.

Computable oneway functions on the reals

Zafeirakis Zafeirakopoulos Department of Mathematics, National & Kapodistrian University of Athens Greece Co-Author(s):

Abstract: Central in computational complexity and cryptography is the notion of oneway functions: finite maps that are easy to compute but hard to invert. Levin recently extended this concept to functions on the reals - infinite bit-sequences - using computability and algorithmic randomness. He asked whether computable oneway real functions exist, and whether they can satisfy properties that are desirable in cryptography, such as collision-resistance. In this talk I will present answers to some of these questions and additional results on probabilistic hardness of inversion for real functions. I will then proceed to explore variations of this concept and focus on characterizing the unsolvability of inverting effective real functions. I will conclude with several open questions and connections between this and several topics in computability and algorithmic randomness. This is joint work with Mingyang Wang and Xiaoyan Zhang based on the preprints: http://arxiv.org/abs/2406.15817 http://arxiv.org/abs/2501.02604 https://arxiv.org/abs/2412.07592