University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Tutte Colloquium - Léo DucasExport this event to calendar

Friday, August 21, 2020 — 3:30 PM EDT

Title: An Algorithmic Reduction Theory for Binary Codes: LLL and more

Joint work with Thomas Debris-Alazard and Wessel van Woerden

Speaker: Léo Ducas
Affiliation: Centrum Wiskunde & Informatica (CWI)
Zoom: Please email Emma Watson

Abstract:

Lattice reduction is the task of finding a basis of short and somewhat orthogonal vectors of a given lattice. In 1985 Lenstra, Lenstra and Lovasz proposed a polynomial time algorithm for this task, with an application to factoring rational polynomials. Since then, the LLL algorithm has found countless application in algorithmic number theory and in cryptanalysis.

There are many analogies to be drawn between Euclidean lattices and linear codes over finite fields. In this work, we propose to extend the range of these analogies by considering the task of reducing the basis of a binary code. In fact, all it takes is to choose the adequate notion mimicking Euclidean orthogonality (namely orthopodality), after which, all the required notions, arguments, and algorithms unfold before us, in quasi-perfect analogy with lattices.

S M T W T F S
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
  1. 2020 (102)
    1. November (1)
    2. October (11)
    3. September (12)
    4. August (11)
    5. July (17)
    6. June (11)
    7. May (6)
    8. March (11)
    9. February (11)
    10. January (11)
  2. 2019 (167)
    1. December (5)
    2. November (15)
    3. October (18)
    4. September (15)
    5. August (9)
    6. July (17)
    7. June (18)
    8. May (16)
    9. April (9)
    10. March (24)
    11. February (13)
    12. January (8)
  3. 2018 (136)
  4. 2017 (103)
  5. 2016 (137)
  6. 2015 (136)
  7. 2014 (88)
  8. 2013 (48)
  9. 2012 (39)
  10. 2011 (36)
  11. 2010 (40)
  12. 2009 (40)
  13. 2008 (39)
  14. 2007 (15)