Daniele Micciancio

Daniele Micciano est professeur au département Computer Science & Engineering de l’Université de Californie à San Diego. Ses domaines d’expertise sont la complexité pour des problèmes de réseaux euclidiens et la cryptographie basée sur les réseaux. Ses centres d’intérêt concerne l’informatique théorique de manière générale et plus spécifiquement la cryptographie ainsi que l’analyse symbolique de protocoles cryptographiques. Il a reçu plusieurs récompenses dont un IEEE Machtey award, un NSF CAREER award et une Sloan Research Fellowship.

On the hardness of computing the minimum distance of lattices and codes

The computation the minimum distance of linear codes and point lattices is a fundamental problem of both great theoretical and practical importance that arises in several areas of science and engineering, including communication theory, post-quantum cryptography, and the study of quadratic forms in mathematics. Both in the case of point lattices and linear codes, computing the minimum distance is a hard combinatorial problem: no efficient algorithm is known even to find approximate solutions, except for very large approximation factors, and the conjectured hardness of the problem provides a foundation to the fast developing area of lattice based cryptography.


In this talk, I will describe the research efforts that took place in the last 15 years aimed at proving NP-hardness results for the minimum distance problem, the current state of the art in the area, and the most important open problems still waiting to be solved. In the process I will touch upon several other important problems in theoretical computer science of independent interest, including derandomization and the list decoding problem.


No prior knowledge of the area is assumed, and the talk should be accessible to a  general computer science audience.

This entry was posted in Conférenciers invités. Bookmark the permalink.

Comments are closed.