Fundamental Algorithms and Algorithmic Complexity

Contribution List

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

9/18/23, 9:30 AM

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

9/19/23, 9:30 AM

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

9/19/23, 2:00 PM

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

9/20/23, 10:00 AM

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

9/20/23, 4:00 PM

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

9/21/23, 9:30 AM

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

9/22/23, 9:30 AM

8. Welcome coffee

9/25/23, 8:45 AM

9. Opening by Dominique Mouhanna, IHP Deputy Director

9/25/23, 9:15 AM

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

9/25/23, 9:30 AM

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

9/25/23, 10:30 AM

12. Recent progress on deterministic integer factorisation by David Harvey

9/25/23, 11:00 AM

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

9/25/23, 2:00 PM

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

9/25/23, 3:00 PM

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

9/25/23, 4:00 PM

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

9/25/23, 4:30 PM

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

9/26/23, 9:30 AM

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

9/26/23, 10:30 AM

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

9/26/23, 11:00 AM

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

9/26/23, 2:00 PM

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

9/26/23, 3:00 PM

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

9/26/23, 4:00 PM

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

9/27/23, 9:30 AM

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

9/27/23, 10:30 AM

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

9/27/23, 11:00 AM

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

9/27/23, 6:30 PM

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

9/28/23, 9:30 AM

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

9/28/23, 10:30 AM

33. Interpolating isogenies by Benjamin Wesolowski

9/28/23, 11:00 AM

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

9/28/23, 2:00 PM

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

9/28/23, 3:00 PM

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

9/28/23, 4:00 PM

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

9/28/23, 4:30 PM

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

9/29/23, 9:30 AM

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

9/29/23, 10:30 AM

40. Modulus tricks for integer sparse polynomials by Daniel Roche

9/29/23, 11:00 AM

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