2023 - T3 - WS1 - Fundamental algorithms and algorithmic complexity

Collection 2023 - T3 - WS1 - Fundamental algorithms and algorithmic complexity

Organizer(s) van der Hoeven, Joris ; Giesbrecht, Mark ; Koiran, Pascal ; Villard, Gilles

Date(s) 25/09/2023 - 29/09/2023

linked URL https://indico.math.cnrs.fr/event/8113/

5 17

Coppersmith’s algorithm and polynomial equations

By Éric Schost

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.

Information about the video

Date of recording 25/09/2023
Date of publication 25/09/2023
Institution IHP
Language English
Director(s) Alexandre Duplessis
Format MP4
Venue IHP - Hermite Amphitheater

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow

All the collection videos

published on September 25, 2023

A recent trend in Computer Algebra? Let's chat!

By Joachim von zur Gathen

published on September 25, 2023

Recent progress on deterministic integer factorisation

By David Harvey

published on September 25, 2023

Efficient approximation of polynomials

By Guillaume Moroz

published on September 25, 2023

First-order factors of linear Mahler operators

By Frédéric Chyzak

published on September 25, 2023

Coppersmith’s algorithm and polynomial equations

By Éric Schost

published on September 26, 2023

Matrix multiplication via Lie groups

By Chris Umans

published on September 26, 2023

Superpolynomial lower bounds against low-depth algebraic circuits

By Sébastien Tavenas

published on September 26, 2023

Border rank, homogeneity and de-bordering paradigms in GCT

By Pranjal Dutta

published on September 26, 2023

Efficient algorithms for Riemann-Roch spaces

By Grégoire Lecerf

published on September 27, 2023

Computing the non-commutative rank of linear matrices

By Gábor Ivanyos

published on September 27, 2023

Closure of algebraic complexity classes under factoring

By Nitin Saxena

published on September 28, 2023

Interpolating isogenies

By Benjamin Wesolowski

published on September 28, 2023

On the complexity of computing characteristic polynomials

By Clément Pernet

published on September 28, 2023

The practical complexity of arbitrary-precision functions

By Fredrik Johansson

published on September 28, 2023

Computing Sparse Fourier Sum of Squares on Finite Abelian Groups

By Lihong Zhi

published on September 29, 2023

Sparse interpolation and Exponential analysis going hand in hand

By Annie Cuyt

published on September 29, 2023

Modulus tricks for integer sparse polynomials

By Daniel Roche

Copyright Carmin.tv 2024

Give feedback