Impagliazzo: A Personal View of Average-case Complexity

30.01.2018, 10:00 – 11:00

30.01.2018 10:00-11:00

Organizer: Felix Günther and Christian Janson, TU Darmstadt


This talk is the fourth edition in the seminar series „Reading the Crypto Classics“. The idea of this seminar is to jointly read classical milestone papers in the area of cryptography, to discuss their impact and understand their relevance for current research areas. The seminar is running as an Oberseminar, but at the same time meant to be a joint reading group seminar of the CROSSING Special Interest Group on Advanced Cryptography with all interested CROSSING members being invited to participate.

This issue will cover the paper

Impagliazzo: „A Personal View of Average-case Complexity“ (Structure in Complexity Theory Conference, 1995), DOI: 10.1109/SCT.1995.514853

with the following abstract:

„The structural theory of average-case complexity, introduced by Levin (1986), gives a formal setting for discussing the types of inputs for which a problem is difficult. This is vital to understanding both when a seemingly difficult (e.g. NP-complete) problem is actually easy on almost all instances, and to determining which problems might be suitable for applications requiring hard problems, such as cryptography. The paper attempts to summarize the state of knowledge in this area, including some “folklore„ results that have not explicitly appeared in print. We also try to standardize and unify definitions. Finally, we indicate what we feel are interesting research directions. We hope that the paper motivates more research in this area and provide an introduction to the area for people new to it.“