Daniele Micciancio is Professor of Computer Science at the University of California, San Diego. His main areas of expertise are the complexity of lattice problems and lattice based cryptography. He is interested in theoretical computer science at large, with a focus on problems related to cryptography, including the computationally sound symbolic analysis of cryptographic protocols. He is the recepient of several awards, including an IEEE Machtey award, an NSF CAREER award and a Sloan Research Fellowship. Complexity of lattice and coding problems (and their applications to cryptography).
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.
