2014
2015
2016
2017
2018
2019
2020
2022
2023
2024

The forty-third meeting of the Prague computer science seminar

Radomír Černoch

Master-key system design: From NP-completeness to a start-up

Master-key system designs also known as the lock-chart problem is a very old combinatorial problem that emerged in the 19th century but remained almost unnoticed by theoreticians until the 21st century.

May 23, 2019

4:15pm

Auditorium S5, MFF UK
Malostranské nám. 25, Praha 1
Show on the map

Lecture annotation

Master-key system designs also known as the lock-chart problem is a very old combinatorial problem that emerged in the 19th century but remained almost unnoticed by theoreticians until the 21st century. The objective is to design mechanical keys and cylinder locks so that the desired access rights are respected. The problem is attractive due to its practical motivation, a simple formalization, a range of practical algorithms and its complexity on the edge between tractable and intractable. Such properties make it also a perfect inspiration for student assignments.

In the lecture, I will introduce the lock-chart problem, existing theoretical results and promising practical algorithms. Among them, the reduction to the boolean satisfiability problem serves as an excellent opportunity to highlight the advantages of modern SAT solvers.

Lecturer

Radomír Černoch

Radomír Černoch works in the start-up company Locksley.cz and also at the Faculty of Electrical Engineering of the CTU, where he received his Ph.D. under the supervision of Filip Železný. Previously, he studied at the University of Edinburgh and RWTH Aachen. Lately, he has been researching the combinatorics of mechanical locks, which led to the 2015 Werner von Siemens award for the innovation of the year.

ABOUT THE PRAGUE COMPUTER SCIENCE SEMINAR

The seminar typically takes place on Thursdays at 4:15pm in lecture rooms of the Czech Technical University in Prague or the Charles University.

Its program consists of a one-hour lecture followed by a discussion. The lecture is based on an (internationally) exceptional or remarkable achievement of the lecturer, presented in a way which is comprehensible and interesting to a broad computer science community. The lectures are in English.

The seminar is organized by the organizational committee consisting of Roman Barták (Charles University, Faculty of Mathematics and Physics), Jaroslav Hlinka (Czech Academy of Sciences, Computer Science Institute), Michal Chytil, Pavel Kordík (CTU in Prague, Faculty of Information Technologies), Michal Koucký (Charles University, Faculty of Mathematics and Physics), Jan Kybic (CTU in Prague, Faculty of Electrical Engineering), Michal Pěchouček (CTU in Prague, Faculty of Electrical Engineering), Jiří Sgall (Charles University, Faculty of Mathematics and Physics), Vojtěch Svátek (University of Economics, Faculty of Informatics and Statistics), Michal Šorel (Czech Academy of Sciences, Institute of Information Theory and Automation), Tomáš Werner (CTU in Prague, Faculty of Electrical Engineering), and Filip Železný (CTU in Prague, Faculty of Electrical Engineering)

The idea to organize this seminar emerged in discussions of the representatives of several research institutes on how to avoid the undesired fragmentation of the Czech computer science community.

Supporters

Contact

Prague computer science seminar is suspended until further notice to prevent spread of the new coronavirus.