{"id":536,"date":"2016-06-21T18:21:39","date_gmt":"2016-06-21T16:21:39","guid":{"rendered":"http:\/\/www.ens-lyon.fr\/LIP\/AriC\/?page_id=536"},"modified":"2019-09-03T17:24:35","modified_gmt":"2019-09-03T15:24:35","slug":"seminars-in-the-past-years","status":"publish","type":"page","link":"https:\/\/www.ens-lyon.fr\/LIP\/AriC\/seminar\/seminars-in-the-past-years","title":{"rendered":"AriC seminars in the past years"},"content":{"rendered":"
\n

2017-2018<\/span><\/h1>\n<\/div>\n
\n

Nicolas Louvet (AriC)<\/p>\n

July 12, 2018 at 10h15, room M7-315 (3rd floor, Monod)<\/p>\n

A compensated dot product for vectors of floating-point expansions<\/p>\n

\n

Some computations require more precision than the 53 bits provided by the IEEE 754 double precision arithmetic (binary64), widely available in hardware. When an arbitrarily large precision is required, multi-precision floating point libraries, such as MPFR, are particularly useful. However, MPFR is implemented using only integer arithmetic, which is not as much optimized as floating point arithmetic on modern processors. If only a few hundreds bits are needed, faster alternatives using only floating point arithmetic exist, such as the well known qd library developed by Bailey and his co-authors. This library provides both double-double and quad-double arithmetics that roughly simulate twice (106 bits) and four times (212 bits) the IEEE 754 double precision, respectively. Double-double and quad-double numbers are a special case of floating point expansions, which consists in representing a rational number as an unevaluated sum of floating point numbers. Another alternative is the use of error-free transformations and compensation techniques to simulate an increased working precision, and we used this approach in this work.<\/p>\n

In this talk, we focus on the computation of dot products between vectors of floating point expansions. We present alternatives to the algorithms obtained using directly double-double and quad-double arithmetics from the qd library: our aim is to trade off speed against a moderate loss of accuracy. Of course, we always keep the loss of accuracy under control by providing forward error bounds for our algorithms. The algorithm we present provides a speedup of 2 compared to the qd library, while maintaining roughly the same accuracy. This speedup is obtained using only basic programming techniques, and even higher speedups can be obtained by using vector instruction sets (AVX2 or AVX512 in particular) available on modern computers.<\/p>\n<\/div>\n<\/div>\n

\n

Nicolas Brisebarre (AriC)<\/p>\n

June 14, 2018 at 10h15, room M7-315 (3rd floor, Monod)<\/p>\n

New results on the table maker’s dilemma for transcendental functions<\/p>\n

\n

On a computer, real numbers are usually represented by a finite set of numbers called floating-point numbers. When one performs an operation on these numbers, such as an evaluation by a function, one returns a floating-point number, hopefully close to the mathematical result of the operation. Ideally, the returned result should be the exact rounding of this mathematical value. If we’re only allowed a unique and fast evaluation (a constraint often met in practice), one knows how to guarantee such a quality of results for arithmetical operations like \\(+, -, x, \/\\) and square root but, as of today, it is still an issue when it comes to evaluate an elementary function such as cos, exp, cube root for instance. This problem, called Table Maker’s Dilemma, is actually a diophantine approximation problem. It was tackled, over the last fifteen years, by V. Lef\u00e8vre, J.M. Muller, D. Stehl\u00e9, A. Tisserand and P. Zimmermann (LIP, \u00c9NS Lyon and LORIA, Nancy), using tools from algorithmic number theory. Their work made it possible to partially solve this question but it remains an open problem. In this talk, I will present an ongoing joint work with Guillaume Hanrot (\u00c9NS Lyon, LIP, AriC) that improve on a part of the existing results.<\/p>\n<\/div>\n<\/div>\n

\n

Alice Pellet-Mary (AriC)<\/p>\n

June 7, 2018 at 10h30, room M7-315 (3rd floor, Monod)<\/p>\n

Approx-SVP in Ideal Lattices with Pre-processing<\/p>\n

\n

Finding a short non zero vector in an Euclidean lattice is a well-studied problem which has proven useful to construct many cryptographic primitives. The current best asymptotic algorithm to find a relatively short vector in an arbitrary lattice is the BKZ algorithm. This algorithm recovers a vector which is at most \\(2^{n^{\\alpha}}\\) times larger than the shortest non zero vector in time \\(2^{n^{1-\\alpha}}\\) for any \\(\\alpha\\) between 0 and 1.<\/p>\n

In order to gain in efficiency, it is sometimes interesting to use structured lattices instead of general lattices. An example of such structured lattices are principal ideal lattices. One may then wonder whether, on the security front, it is easier to find short vectors in a structured lattice or not. Until 2016, there was no known algorithm which would perform better on principal ideal lattices than the BKZ algorithm (either classically or quantumly). In 2016, Cramer et al. proposed a quantum algorithm that finds a \\(2^{\\sqrt n}\\) approximation of the shortest non zero vector in polynomial time. However, the BKZ algorithm remained the best algorithm in the classical setting or for approximation factor smaller than \\(2^{\\sqrt n}\\) in the quantum setting.<\/p>\n

In this talk, I will present an algorithm that generalizes the one of Cramer et al. and improves upon the BKZ algorithm for principal ideal lattices, both quantumly and classically. This algorithm is heuristic and non uniform (or equivalently it needs an exponential pre-processing time).<\/p>\n<\/div>\n<\/div>\n

\n

Laurent Gr\u00e9my (AriC)<\/p>\n

May 24, 2018 at 10h15, room M7-315 (3rd floor, Monod)<\/p>\n

Assessing the security of discrete-logarithm-based cryptography<\/p>\n

\n

The security of most public-key cryptography relies on the difficulty of mathematical problems, among which the discrete logarithm problem in finite fields. The number field sieve (NFS) is the most efficient known algorithm for this problem for a large range of finite fields. Since its introduction in the 90’s, NFS has evolved, both theoretically and practically. These improvements force cryptographers to reassess key-sizes of cryptosystems.<\/p>\n

In this talk, we will first introduce the key notions of the index-calculus algorithms, the family of algorithms to which NFS belongs. Then, we will describe recent progress related to NFS. Finally, we will conclude by giving ideas of how pairing-based cryptography is assessed, based on the works of Menezes\u2014Sarkar\u2014Singh and Barbulescu\u2014Duquesne.<\/p>\n<\/div>\n<\/div>\n

\n

Dan Roche (US Naval Academy and LJK, Grenoble)<\/p>\n

May 17, 2018 at 10h15, room M7-315 (3rd floor, Monod)<\/p>\n

Matrix multiplication and inverse with error correction<\/p>\n

\n

In some situations the result of a linear algebra computation may be known to be almost correct – that is, correct except in a few positions of the output matrix. One example is in distributed computing, where some nodes in a cluster may return incorrect results; another is in integer computations where only a few entries may be large enough to require an additional prime’s worth of Chinese remaindering. We present new algorithms to use the almost-correct result of a matrix product or inverse to recover the completely-correct result, whose running time is softly-linear in the size of the matrix when the number of errors is sufficiently small. Our algorithms build on the prior work by Gasieniec et al (Algorithmica 2017) for error-correcting matrix multiplication, and we are now able to effectively handle sparsity in the inputs and outputs, as well as incorporate fast matrix multiplication so that the cost scales well even with a large number of errors. The key underlying tools come from sparse polynomial interpolation and sparse low-rank linear algebra.<\/p>\n<\/div>\n<\/div>\n

\n

Eva Darulova (MPI, Saarbr\u00fccken)<\/p>\n

May 3, 2018 at 10h15, room M7-315 (3rd floor, Monod)<\/p>\n

Daisy – a framework for sound accuracy analysis and optimization of numerical programs<\/p>\n

\n

Floating-point or fixed-point computations are an integral part of many embedded and scientific computing applications, as are the roundoff errors they introduce. They expose an interesting tradeoff between efficiency and accuracy: the more precision we choose, the closer the results will be to the ideal real arithmetic, but the more costly the computation becomes. Unfortunately, the unintuitive and complex nature of finite-precision arithmetic makes manual optimization infeasible such that automated tool support is indispensable.<\/p>\n

This talk presents an overview of Daisy, a framework for sound accuracy analysis and optimization of finite-precision programs. We will provide a high-level view of its main features: roundoff error analysis as well as rewriting and mixed-precision optimization.<\/p>\n<\/div>\n<\/div>\n

\n

AriC members<\/p>\n

April 26, 2018 at 10h45, room M7-315 (3rd floor, Monod)<\/p>\n

Back from conferences<\/p>\n

\n

Short talks (10\u2019 + 5\u2019 for questions) when people are back from a conference, on talks they attended and found interesting. We will have, by alphabetical order :<\/p>\n