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.
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.
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.
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.
© 2013-2022, Prague Computer Science Seminar 
This work is licensed under aCreative Commons Attribution 4.0 International License.
