Download slides (PDF)

By Bernardo Portela, HASLab/INESC TEC & University of Minho.

Abstract. ``There is a large gap between a problem not being easy and the same problem being difficult'' - A Personal View of Average-Case Complexity represents a classic work by Russel Impagliazzo in the fields of computational complexity and cryptography, and serves as introductory and motivational material for promoting research in these subjects. To do this, Impagliazzo proposes five worlds, existing as a direct consequence of solving the "big" questions of computational complexity: Algorithmica, Heuristica, Pessiland, Minicrypt and Cryptomania. In each world, he analyzes (at a very high-level) the influence of solving these questions on algorithm design, artificial intelligence, cryptography and computer security. Our world is one of the above.

This work is particularly interesting for researchers outside these areas of complexity and cryptography, as they are exactly the intended audience. The challenges presented are fairly well-known by everyone in the computer sciences community, and the consequences of their solutions are a powerful way to contextualize their importance. Furthermore, it is interesting to realize that these questions were not recent by the time the paper was published (1995), and they remain relevant and unanswered by 2016.

Keywords. Security and Cryptography, Computational Complexity, Randomness.

About the speaker. Bernardo is a third-year MAPi PhD student, affiliated with HASLab/INESC TEC & Univ. of Minho, and working under supervision of Manuel Barbosa. His areas of interest are Cryptography, Formal methods and Distributed systems. In particular, his thesis "High-Assurance Multiparty Computation" is focused on the challenge of bridging theoretical and practical approaches towards multiparty computation. Bernardo has been actively contributing in two projects: PRACTICE and SafeCloud. In the context of PRACTICE, he has researched the theoretical implications of the new Intel instruction set architecture "SGX", towards enabling multiparty computation. In the context of SafeCloud, he has explored the feasibility of different trust models and special encryption techniques towards real-world cloud deployments. Bernardo's cooperation with researchers from the University of Bristol has resulted in a contribution to be presented at EuroS&P: "Foundations of Hardware-Based Attested Computation and Application to SGX".

LOCATION AND TIME

Address:  University of Minho, Gualtar campus, Braga, Portugal.

Building. Departamento de Informatica, Building 07.

Coffee session: at 1:30PM-2PM, Sala de Estar, 4th floor.

Talks session: at 2PM-2:30PM, Sala de Estar, 4th floor.