Fundamental Algorithms and Algorithmic Complexity

Liste des contributions

1. Efficient Algorithms for Integer and Polynomial Matrices by G. Labahn and A. Storjohann. University of Waterloo, Canada. 9:30-12:00. Amphitheater Darboux, IHP

18/09/2023 09:30

2. Efficient Algorithms for Integer and Polynomial Matrices by G. Labahn and A. Storjohann. University of Waterloo, Canada. 9:30-12:00. Amphitheater Darboux, IHP

19/09/2023 09:30

5. Euclidean Lattices by D. Stehlé. CryptoLab Inc., Lyon. 14:00-16:00. Amphitheater Darboux, IHP

19/09/2023 14:00

6. Euclidean Lattices by D. Stehlé. CryptoLab Inc., Lyon. 10:00-12:00. Amphitheater Hermite, IHP

20/09/2023 10:00

7. General audience presentation by J. van der Hoeven, CNRS, LIX, Palaiseau. 16:00-17:00. Amphitheater Hermite, IHP

20/09/2023 16:00

3. Efficient Algorithms for Integer and Polynomial Matrices by G. Labahn and A. Storjohann. University of Waterloo, Canada. 9:30-12:00. Amphitheater Darboux, IHP

21/09/2023 09:30

4. Efficient Algorithms for Integer and Polynomial Matrices by G. Labahn and A. Storjohann. University of Waterloo, Canada. 9:30-12:00. Amphitheater Darboux, IHP

22/09/2023 09:30

8. Welcome coffee

25/09/2023 08:45

9. Opening by Dominique Mouhanna, IHP Deputy Director

25/09/2023 09:15

10. A recent trend in Computer Algebra? Let's chat! by Joachim von zur Gathen

25/09/2023 09:30

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

11. Coffee break

25/09/2023 10:30

12. Recent progress on deterministic integer factorisation by David Harvey

25/09/2023 11:00

Abstract. There are several deterministic factoring algorithms of complexity N1/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.

14. Efficient approximation of polynomials by Guillaume Moroz

25/09/2023 14:00

Abstract. In modern numerical computations, real numbers are approximated with floating-point numbers, of the form s2e, 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)Xe...

15. First-order factors of linear Mahler operators by Frédéric Chyzak

25/09/2023 15:00

Abstract. We develop and compare two algorithms for computing first-order right-hand factors in the ring of linear Mahler operators ℓrMr+⋯+ℓ1M+ℓ0 where ℓ0,…,ℓr are polynomials in x and Mx=xbM for some integer b≥2. In other words, we give algorithms for finding all formal infinite product solutions of linear functional equations ℓr(x)f(xbr)+⋯+ℓ1(x)f(xb)+ℓ0(x)f(x)=0.
The first of our algorithms...

16. Coffee break

25/09/2023 16:00

17. The block Wiedemann algorithm and polynomial equations by Éric Schost

25/09/2023 16:30

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.

18. Matrix multiplication via Lie groups by Chris Umans

26/09/2023 09:30

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 ω=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...

19. Coffee break

26/09/2023 10:30

20. Superpolynomial lower bounds against low-depth algebraic circuits by Sébastien Tavenas

26/09/2023 11:00

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...

27. Border rank, homogeneity and de-bordering paradigms in GCT by Pranjal Dutta

26/09/2023 14:00

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...

28. Efficient algorithms for Riemann—Roch spaces by Grégoire Lecerf

26/09/2023 15:00

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...

29. Coffee break

26/09/2023 16:00

23. Computing the non-commutative rank of linear matrices by Gábor Ivanyos

27/09/2023 09:30

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...

24. Coffee break

27/09/2023 10:30

25. Closure of algebraic complexity classes under factoring by Nitin Saxena

27/09/2023 11:00

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...

30. Cocktail

27/09/2023 18:30

31. Applications of fast integer and polynomial lattice reduction in cryptography by Nadia Heninger

28/09/2023 09:30

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.

32. Coffee break

28/09/2023 10:30

33. Interpolating isogenies by Benjamin Wesolowski

28/09/2023 11:00

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...

34. On the complexity of computing characteristic polynomials by Clément Pernet

28/09/2023 14:00

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...

35. The practical complexity of arbitrary-precision functions by Fredrik Johansson

28/09/2023 15:00

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...

36. Coffee break

28/09/2023 16:00

37. Computing Sparse Fourier Sum of Squares on Finite Abelian Groups by Lihong Zhi

28/09/2023 16:30

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...

38. Sparse interpolation and Exponential analysis going hand in hand by Annie Cuyt

29/09/2023 09:30

We discuss how sparse interpolation in computer algebra and exponential analysis in digital signal processing can cross-fertilize and lead to new results. The Nyquist constraint [11] is the digital signal processing equivalent of stating that the argument of a complex exponential exp(φ∆) with φ ∈ C and ∆ ∈ R+ can only be retrieved uniquely under the condition that |=(φ)|∆ < π. It governs...

39. Coffee break

29/09/2023 10:30

40. Modulus tricks for integer sparse polynomials by Daniel Roche

29/09/2023 11:00

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...

26. Clément Pernet

21. Free afternoon

41. Group Photo

13. Lunch break

22. Reception