Docenturföreläsning: Pedro Zuidberg dos Martires
25 mars 2026 10:00 – 11:00 Hörsal L2, Långhuset Öppet för alla
Pedro Zuidberg dos Martires håller sin docenturföreläsning vid institutionen för naturvetenskap och teknik.
Titel: "Counting Things in Computer Science: Logic, Probability, and a bit of Quantum Information".
Abstrakt
The most fundamental questions we can ask are whether things are true or not. Surprisingly, a large part of computer science can be understood as designing methods to answer such questions. In this lecture, I will start with a simple puzzle: can we color a map so that neighboring regions have different colors? This leads to satisfiability (SAT), a problem that sits at the center of modern computing and captures the difference between problems that are easy in principle and problems that remain hard even for the fastest computers. As a natural follow-up, we can ask not only whether a solution exists, but also how many solutions there are. This apparently simple yet powerful question of counting solutions opens the door to ideas at the core of modern artificial intelligence, through probability theory. Finally, I will end with a short glimpse of an unexpected generalization, where ideas from probability are replaced by concepts from quantum information theory.