Abstract. Does the recent craze about chatbots affect Computer Algebra? If so, in which way? As a non-expert, I will share some observations.

Abstract. There are several deterministic factoring algorithms of complexity $N^{1/4+o(1)}$ going back to the 1970s. A few years ago Hittmeir lowered the exponent to $2/9$, and I subsequently improved it further to $1/5$. In this talk I will explain the key ideas behind these new algorithms.

Abstract. In modern numerical computations, real numbers are approximated with floating-point numbers, of the form $s 2^e$, where $s$ and $e$ are integers with a fixed precision. This representation is compact and can represent numbers with small and large magnitudes. In this talk, we will generalize this idea to approximate univariate polynomial functions with piecewise polynomials of the form $s(X) X^e$ where $s$ is a polynomial of fixed degree and $e$ is an integer. Using tools such as the Newton polygon, this representation can be computed efficiently both in theory and in practice. Moreover, it can be used to efficiently evaluate and find roots approximations of a high-degree polynomial.

Abstract. We develop and compare two algorithms for computing first-order right-hand factors in the ring of linear Mahler operators $\ell_r M^r + \dots + \ell_1 M + \ell_0$ where $\ell_0, \dots, \ell_r$ are polynomials in $x$ and $Mx = x^b M$ for some integer $b \geq 2$. In other words, we give algorithms for finding all formal infinite product solutions of linear functional equations $\ell_r(x) f(x^{b^r}) + \dots + \ell_1(x) f(x^b) + \ell_0(x) f(x) = 0$.
The first of our algorithms is adapted from Petkovšek's classical algorithm for the analogous problem in the case of linear recurrences. The second one proceeds by computing a basis of generalized power series solutions of the functional equation and by using Hermite-Padé approximants to detect those linear combinations of the solutions that correspond to first-order factors.
We present implementations of both algorithms and discuss their use in combination with criteria from the literature to prove the differential transcendance of power series solutions of Mahler equations.

Abstract. Coppersmith's generalization of Wiedemann's algorithm is a key ingredient in algorithms for integer factorization or discrete logarithms. I will describe how, in recent years, it has also successfully been applied in contexts arising from algorithms for polynomial equations, such as sparse FGLM algorithms, or modular composition.

Abstract. Cohn and Umans proposed a group-theoretic approach to bounding the exponent of matrix multiplication. Previous work within this approach ruled out certain families of groups as a route to obtaining $\omega=2$, while other families of groups remain potentially viable. In this work we turn our attention to matrix groups, whose usefulness within this framework was relatively unexplored.
To study these groups, we propose working in the continuous setting of Lie groups, in which we develop an analogous theory. Obtaining the analogue of exponent $2$ in this potentially easier setting is a key challenge that represents an intermediate goal short of actually proving $\omega = 2$. We give constructions in the continuous setting which are indeed best-possible in a precise sense.
We then describe a new ingredient -- "separating polynomials" -- which allow us to recover a full-fledged framework yielding actual (finite) algorithms in the Lie group setting, rather than constructions whose interest is only by analogy. This framework has some mathematically pleasing features: the notion of border rank arises naturally from the Lie algebra, and we have machinery that points to the main open question being that of finding a separating polynomial of appropriate degree in a certain ring of invariant polynomials.
This is based on joint work with Jonah Blasiak, Henry Cohn, Josh Grochow, and Kevin Pratt.

Abstract. An algebraic circuit computes a polynomial using addition and multiplication operators. Understanding the power of algebraic circuits has close connections to understanding general computation. Despite this, not many lower bounds are known for even simple Sigma Pi Sigma (product-depth 1) circuits. Before our work, the best known lower bound for product-depth 1 circuit was (slightly less than) cubic. No lower bounds were known for general product-depth 2 circuits.
In this work, we show the first superpolynomial lower bound for low-product-depth algebraic circuits. In the talk, we discuss the main results and present the proof ideas used in the proof of the superpolynomial lower bound for product-depth 1 circuits.
This talk is based on joint work with Nutan Limaye and Srikanth Srinivasan.

Abstract. Border (or approximative) complexity of polynomials plays an integral role in GCT (Geometric Complexity Theory) approach to P!=NP. This raises an important basic question: can arbitrary approximations of simple polynomials involve exponential-precision which may not be efficiently simulable? Circuits of depth 3 or 4, are a good testing ground for this question. Recently, Kumar proved that *any* polynomial f can be approximated arbitrarily well by restrictions of the polynomial x1 ... xn - 1 for n large enough. In this talk, we will see a stronger connection (& reverse) of this result with the border rank of f, and how homogeneity can play an important role in border complexity.
Furthermore, we will see the border of constant top-fanin depth-3 circuits (which is far more general than x1...xn -1) is relatively easy & hierarchical - it can be computed by a polynomial-size algebraic branching program (ABP).
This is based on the joint works with -- 1) Prateek Dwivedi & Nitin Saxena (FOCS'21) 2) Nitin Saxena (FOCS'22) 3) Fulvio Gesmundo, Christian Ikenmeyer, Gorav Jindal and Vladimir Lysikov (submitted).

Abstract. Riemann—Roch spaces are a cornerstone of modern applications of algebra to various areas of computer science: error correcting codes, secret sharing, multi-party computations, zero-knowledge proofs, resilience in distributed storage systems, interactive oracle proofs... Best performances are achieved for specific families of spaces known to be difficult to compute.
We will present a new probabilistic algorithm of Las Vegas type that computes Riemann—Roch spaces of plane projective curves in expected sub-quadratic time whenever the characteristic is zero or positive but sufficiently large. The method relies on the Brill—Noether theory (1874), bivariate polynomial elimination, Puiseux series expansions, and structured polynomial matrices. In case of curves with only ordinary singularities, we will present a faster variant that even supports any characteristic.
This is joint work with Simon Abelard (Thales SIX GTS, France), Elena Berardini (CNRS, University of Bordeaux, France), Alain Couvreur (Inria Saclay, France).

Abstract. The topic of the talk connects skew-fields, polynomial identity testing, invariant theory and optimization. By a linear matrix we mean a matrix having homogeneous linear entries and the non-commutative rank is the rank when we consider the variables as elements of the appropriate free skew-field. Computing it is a relaxation of determining the maximal rank of a matrix in a given linear space of matrices. A remarkable characterization can be given in terms of a large common zero block of the coefficient matrices after a change of basis. We will present the main ideas of a deterministic polynomial time algorithm that computes the noncom-mutative rank. Note that existence of an efficient deterministic method computing the ordinary rank is a famous open problem in polynomial identity testing. The algorithm gives lower and upper witnesses for the rank. The lower witness is a polynomial invariant of a sub-matrix while the upper witness is given by a common zero block. We will also discuss some applications of the algorithm.
The talk is based on joint works with Youming Qiao and K. V. Subrahmanyam.

Abstract. Polynomial factoring is one of the most fundamental problems in the area of computational algebra. Its variants have attracted a huge amount of attention in the last half-a-century. On the other hand, algebraic complexity theory classifies polynomials, into complexity classes, according to computational resources. Could we show that these classes afford polynomial factoring algorithms?
In this talk we will focus on four algebraic complexity classes--- size-s circuits VP$_{nb}$, size-s degree-s circuits VP, size-s degree-s verifier circuits VNP, and size-s algebraic branching programs VBP. We will discuss the algebraic methods, inspired from analysis, that have been developed to do factoring in these complexity classes. We will list the open questions and make some related conjectures.
[This is based on the joint work with Pranjal Dutta, Amit Sinhababu (J. ACM'22, STOC'18), and the follow-up papers by others.] [https://www.cse.iitk.ac.in/users/nitin/research.html]

Abstract. I will survey some concrete lattice computations that have appeared in the context of some recent papers in applied cryptography that I have been involved with, and pose some open problems and speculative improvements that arose in these contexts.

Abstract. In 2011, Jao and De Feo proposed a key exchange based on the presumed hardness of the following problem: given two elliptic curves, and the images of a few points through a secret isogeny, compute this isogeny.
In 2022, a polynomial-time algorithm was discovered. This powerful new tool has broken many cryptosystems, but has also lead to new constructions, and other applications in algorithmic number theory. We will present this algorithm and some of its applications.

Abstract. : Among the classical problems in computational linear algebra, the computation of the characteristic polynomial is of great relevance for applications as it reflects most invariants of the input matrix. It is a key component in the solution of many other related problems, such as computing eigenvalues, invariant factors and invariant subspace decomposition, testing matrices for similarity, Krylov methods etc. Computing characteristic polynomials efficiently is surprisingly challenging and has lead to a very diverse algorithmic landscape, as it lies in-between scalar linear algebra and modules of polynomial matrices. For instance, finding a deterministic reduction to dense matrix multiplication was an open-problem until recently. We will introduce some of these algorithmic techniques to present recent complexity improvements for the computation of characteristic polynomials: with dense matrices, first, we will present a recent work achieving the first reduction to matrix multiplication, based on polynomial matrix arithmetic. Then, in the context of matrices with a displacement rank structure, we will present algorithms, leading to the first sub-quadratic time cost.
This talk is based on joint work with P. Karpman, V. Neiger, H. Signargout and G. Villard.

Abstract. Most familiar operations on $N$-digit real numbers (sum, product, square root, exponential, logarithm, etc.) can be computed in time quasilinear in $N$. However, this kind of asymptotic statement hides details which can add up to huge differences in practical running times. We will discuss how to think about optimizing arbitrary-precision algorithms, with a detailed look at state-of-the-art methods for transcendental functions.

Abstract. The non-negativity of a function on a finite abelian group can be certified by its Fourier sum of squares (FSOS). We propose a method of certifying the nonnegativity of an integer valued function by an FSOS certificate, which is defined to be an FSOS with a small error. We prove the existence of exponentially sparse polynomial and rational FSOS certificates and provide two methods to validate them. As a consequence of the aforementioned existence theorems, we propose a semidefinite programming (SDP)-based algorithm to efficiently compute a sparse FSOS certificate. For applications, we consider certificate problems for maximum satisfiability (MAX-SAT) and maximum k-colorable subgraph (MkCS) and demonstrate our theoretical results and algorithm by numerical experiments.
Jointed work with Jianting Yang and Ke Ye.

abstractCuytLee.pdf

Abstract. Sparse polynomials with integer coefficients are a basic building block in computer algebra systems, as well as an important fundamental object for algorithmic study. Since at least the 1980s, efficient algorithms have been constructed based on the flexibility afforded by changing the integer modulus repeatedly during the computation. This talk will attempt to briefly survey some of the modulus-choosing techniques employed in recent results to achieve faster algorithms. We will also briefly examine when these techniques (fail to) extend to the case of floating point computations and field extensions.