Registration / How to come to IHP / Some restaurants close to IHP
Program of the workshop, September 25 to 29, 2023  All talks in amphitheater Hermite / Live stream Hermite
Monday September 25th, 2023  

8:45  Welcome coffee  
9:159:30  Opening
Dominique Mouhanna, IHP Deputy Director 

9:3010:30  Joachim von zur Gathen  A recent trend in Computer Algebra? Let's chat!Abstract. Does the recent craze about chatbots affect Computer Algebra? If so, in which way? As a nonexpert, I will share some observations. 
10:3011:00  Coffee break  
11:0012:00  David Harvey  Recent progress on deterministic integer factorisationAbstract. 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. 
12:0014:00  Lunch break  
14:0015:00  Guillaume Moroz  Efficient approximation of polynomialsAbstract. In modern numerical computations, real numbers are approximated with floatingpoint 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 highdegree polynomial. 
15:0016:00  Frédéric Chyzak  Firstorder factors of linear Mahler operatorsAbstract. We develop and compare two algorithms for computing firstorder righthand 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$. 
16:0016:30  Coffee break  
16:3017:30  Éric Schost  Coppersmith’s algorithm and polynomial equationsAbstract. 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. 
Tuesday September 26th, 2023  
9:3010:30  Chris Umans  Matrix multiplication via Lie groupsAbstract. Cohn and Umans proposed a grouptheoretic 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. 
10:3011:00  Coffee break  
11:0012:00  Sébastien Tavenas  Superpolynomial lower bounds against lowdepth algebraic circuitsAbstract. 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 (productdepth 1) circuits. Before our work, the best known lower bound for productdepth 1 circuit was (slightly less than) cubic. No lower bounds were known for general productdepth 2 circuits. 
12:00  Group photo  
12:0014:00  Lunch break  
14:0015:00  Pranjal Dutta  Border rank, homogeneity and debordering paradigms in GCTAbstract. 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 exponentialprecision 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. 
15:0016:00  Grégoire Lecerf  Efficient algorithms for Riemann—Roch spacesAbstract. Riemann—Roch spaces are a cornerstone of modern applications of algebra to various areas of computer science: error correcting codes, secret sharing, multiparty computations, zeroknowledge proofs, resilience in distributed storage systems, interactive oracle proofs... Best performances are achieved for specific families of spaces known to be difficult to compute. 
16:00  Coffee  
Wednesday September 27th, 2023  
9:3010:30  Gábor Ivanyos  Computing the noncommutative rank of linear matricesAbstract. The topic of the talk connects skewfields, polynomial identity testing, invariant theory and optimization. By a linear matrix we mean a matrix having homogeneous linear entries and the noncommutative rank is the rank when we consider the variables as elements of the appropriate free skewfield. 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 noncommutative 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 submatrix while the upper witness is given by a common zero block. We will also discuss some applications of the algorithm. 
10:3011:00  Coffee break  
11:0012:00  Nitin Saxena  Closure of algebraic complexity classes under factoringAbstract. 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 halfacentury. 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? 
Free afternoon  
18:30 (welcome from 18:00)  Reception. Tour Zamansky, campus Pierre et Marie Curie, place Jussieu, 75005 Paris. We'll need to have a precise list of participants at the entrance to the building. If you were not yet registered before September or have any doubts, for a partner for example, please contact the organizers (and possibly register).  
Thursday September 28th, 2023  
9:3010:30  Nadia Heninger  Applications of fast integer and polynomial lattice reduction in cryptographyAbstract. 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. 
10:3011:00  Coffee break  
11:0012:00  Benjamin Wesolowski  Interpolating isogeniesAbstract. 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. 
12:0014:00  Lunch break  
14:0015:00  Clément Pernet  On the complexity of computing characteristic polynomialsAbstract. : 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 inbetween scalar linear algebra and modules of polynomial matrices. For instance, finding a deterministic reduction to dense matrix multiplication was an openproblem 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 subquadratic time cost. 
15:0016:00  Fredrik Johansson  The practical complexity of arbitraryprecision functionsAbstract. 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 arbitraryprecision algorithms, with a detailed look at stateoftheart methods for transcendental functions. 
16:0016:30  Coffee break  
16:3017:30  Lihong Zhi  Computing Sparse Fourier Sum of Squares on Finite Abelian GroupsAbstract. The nonnegativity 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 (MAXSAT) and maximum kcolorable subgraph (MkCS) and demonstrate our theoretical results and algorithm by numerical experiments. 
Friday September 29th, 2023  
9:3010:30  Annie Cuyt  Sparse interpolation and Exponential analysis going hand in handabstractCuytLee.pdf 
10:3011:00  Coffee break  
11:0012:00  Daniel Roche  Modulus tricks for integer sparse polynomialsAbstract. 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 moduluschoosing 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. 
End of the workshop 
Special week
September 18 to 22, 2023

Efficient Algorithms for Integer and Polynomial Matrices (long course), Slides
George Labahn and Arne Storjohann, University of Waterloo
Monday 18th, Tuesday 19th, Thursday 21rst, and Friday 22nd, 9:3012:00, Amphitheater Darboux – Live stream D 
Short course  Damien Stehlé, CryptoLab Inc., Lyon
Latticebased encryption
Abstract. In this lecture, I will first describe how to obtain publickey encryption from lattices. I will then focus on the CKKS fully homorphic encryption scheme.
Tuesday 19th, 14:0016:00, Amphitheater Darboux – Live stream D, and Wednesday 20th,10:0012:00, Amphitheater Hermite – Live stream H
 General audience presentation 
Wednesday 20th, 16:0017:00, Amphitheater Hermite – Live stream H
Integer multiplication in time $O(n \log n)$ Joris van der Hoeven, CNRS, LIX, Palaiseau
SlidesAbstract. Integer multiplication is one of the oldest mathematical operations and still a central problem for computer arithmetic. The complexities of many other basic operations such as division, base conversion, gcds, computing $e$ and $\pi$, FFTs, etc. can be expressed in terms of the complexity of integer multiplication. In our talk, we will survey a new algorithm for multiplying two $n$digit integers in time $O(n \log n)$.
Related event: Jérémy Berthomieu’s Habilitation defense,
Contributions to polynomial system solving: Recurrences and Gröbner bases
.
Thursday 21rst, 14:00,
at LIP6, Campus PierreetMarie Curie, 4 place Jussieu, 75005 Paris,
room 2526, 105
Workshop: Fundamental Algorithms and Algorithmic Complexity
Organizers: J. van der Hoeven, M. Giesbrecht, P. Koiran, G. Villard
September 25 to 29, 2023
The field of computational complexity aims at understanding the capabilities of computational devices and especially how fast various problems can be solved. A lot of research focuses on isolating and studying complexity classes of those problems that can be solved using a certain amount of resources. One of the most interesting and challenging problem in the area of computer algebra, is to develop tools and methods in complexity theory that also reflects running times that are observed in practice, for a wide selection of data types. The computer algebra research community indeed produces software that proceed on various mathematical objects and having high impact. This requires expertise from many areas of computer science and of mathematics.
This workshop aims at bringing together experts from both the theoretical and more practical sides, while covering a wide spectrum of problems from algebra, geometry, symbolic computation, arithmetic, and numerical computation. Specific challenges that the workshop will focus on include the following: polynomials in complexity, structured problems, tensors, complexity and specification, certificates and their links with delegated computation, efficiency in cryptoalgebro algorithms, HPC implementation of core algorithms, complexity in numerical analysis.
Invited speakers
 Frédéric Chyzak, Inria, Palaiseau, France.
 Annie Cuyt, University of Antwerp, Belgium.
 Pranjal Dutta, School of Computing, National University of Singapore.
 Joachim von zur Gathen, Professor emeritus, Universtität Bonn, Germany.
 (Laura Grigori, Inria, LJLL, Paris, France. Cancelled.)
 David Harvey, University of New South Wales, Sydney, Australia.
 Nadia Heninger, University of California, San Diego, USA.
 Gábor Ivanyos, HUNREN Research Institute for Computer Science and Control, Budapest, Hungary.
 Fredrik Johansson, Inria, IMB, Bordeaux, France.
 Grégoire Lecerf, CNRS, LIX, Palaiseau, France.
 Guillaume Moroz, Inria, LORIA, Nancy, France.
 Clément Pernet, Université Grenoble Alpes, LJK, France.
 Daniel Roche, United States Naval Academy, Annapolis, USA.
 Chris Umans, California Institute of Technology, USA.
 Nitin Saxena, Indian Institute of Technology, Kanpur, India.
 Éric Schost, University of Waterloo, Ontario, Canada.
 Sébastien Tavenas, CNRS, LAMA, Le BourgetduLac, France.
 Benjamin Wesolowski, CNRS, UMPA, ENS de Lyon, France.
 Lihong Zhi, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China.