CoSP Student Workshop

CoSP student workshop is held July 25 in S6, Charles University, Malostranske nam 25, Prague 1. 

The students contacted several researchers and decided on the following programme of invited lectures:

9:30 - 10:30 - Irena Penev:

An introduction to perfect graphs

A graph is perfect if all its induced subgraphs H satisfy the property that the chromatic number of H is equal to the size of a maximum clique in H. Perfect graphs were introduced by Berge in the 1960s and have been an active area of research ever since. In particular, Berge's Strong Perfect Graph Conjecture, which states that a graph is perfect if and only if neither it nor its complement contains an induced odd cycle of length at least five, attracted a great deal of attention. This conjecture was finally proven in the early 2000s, and it is now known as the Strong Perfect Graph Theorem. In this talk, we introduce perfect graphs and motivate their study, and we give a brief sketch of the proof of the Strong Perfect Graph Theorem.

10:45 - 11:45 - Pavel Hubacek: 

On Zero-Knowledge Proof Systems or How to Prove a Theorem Without Giving Away the Proof

In this talk, I present the basics of zero-knowledge proof systems which were introduced by Goldwasser, Micali, and Rackoff and became a central tool for modern theoretical cryptography in the past three decades. Zero-knowledge proofs give a prover the remarkable ability to efficiently convince a verifier about the veracity of a statement (e.g. 3-colorability of a graph) without revealing anything more (i.e., the 3-coloring). Even formalising the notion of zero-knowledge was a highly nontrivial task and, to this day, there remain various interesting open problems about efficient constructions of zero-knowledge proof systems that would enable stronger user privacy in practical systems such as in decentralised cryptographic currencies.