Computational Algebra Seminar: Stehle, Brisebarre

ALTERATION TO PREVIOUSLY ADVERTISED SEMINAR!
The seminar on Wednesday will be a double-header. Note also change of room.

Speaker: Damien Stehle
Title: Hard Lattice Problems & Strong Reductions
Time & Place: 3pm-3:45pm, Wednesday 9 January, Carslaw 535

Abstract: Continuing talk of Monday 7 January. Topics include
. Lattice point enumeration
. Strong reductions
. Enumeration and strong reductions together
. Hard lattice functions
. Applications of strong reductions in cryptanalysis and computer arithmetic
. New and further developments


Speaker: Nicolas Brisebarre
Title: Machine-efficient polynomial approximants
Time & Place: 4:10pm-4:55pm, Wednesday 9 January, Carslaw 535

Abstract: Polynomial approximations are often used when implementing functions
on a computing system. In most cases, the polynomial that best approximates
(for a given distance and in a given interval) a function has coefficients that
are not exactly representable with a finite number of bits. And yet, the
polynomial approximations that are actually implemented do have coefficients
that are represented with a finite - and sometimes small - number of bits: this
is due to the finiteness of the floating-point representations (for software
implementations), and to the need to have small, hence fast
and/or inexpensive, multipliers (for hardware implementations). We then have to
consider polynomial approximations for which the degree-$i$ coefficient has at
most $m_i$ fractional bits: in other words, it is a rational number with
denominator $2^{m_i}$. We provide one general method, based on linear
programming, for finding the best polynomial approximation under this
constraint and another method, fast and efficient, based on lattice reduction,
that gives a very good approximant under this constraint. Moreover, our methods
also apply if some other constraints (such as requiring some coefficients to be
equal to some predefined constants, or minimizing relative error instead of
absolute error) are required.

This is a joint work with Sylvain Chevillard, Jean-Michel Muller and
Serge Torres.