"Foundations" seminar

Within TEMTA119 and in collaboration with other research groups, we are organizing a "Foundations of CS and AI" seminar series. It is meant for people who like the foundations of computer science and CS's various subfields and/or who like the mathematical part of computer science.

Future Talks

  • Two seminars. April 1 and 8 (2025), 12:15, in room 2049 by Helger Lipmaa
    • Title: On Zero-Knowledge and Zk-SNARKs
    • Zero-knowledge proofs (ZK), and in particular zk-SNARKs (ZK succinct arguments of knowledge), have become popular in both industry and academia due to their core promise: they allow one to efficiently verify that a computation was done correctly without re-running the entire computation or revealing the prover's private data. Over the past five years, interest in zk-SNARKs has surged, largely thanks to blockchain applications that come with significant funding. Current zk-SNARKs can prove the correctness of arbitrary computations w and structured computations with a factor of overhead 100000 and 10, respectively. Importantly, verification of the correctness of an arbitrary computation usually takes just milliseconds. In the first seminar, I will give a short overview of the state of the art. In the second seminar, I will introduce some example protocols.
    • slides
    • Additional literature: Interested people can check the ZK MOOC at https://zk-learning.org/ or Justin Thaler's book https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.html

Past Talks

  • March 18 (2025) 12:15, in room 2049 by Raul Vicente
    • Title: On heads and tails
    • Continuation of the previous talk
    • slides Δ
  • March 11 (2025) 12:15, in room 2049 by Raul Vicente
    • Title: On heads and tails
    • Abstract: In this talk, I will introduce you to the puzzling geometrical patterns that are formed by some neurons in your brain. In particular, I will talk about grid cells, which are neurons that exhibit striking hexagonal firing patterns that provide a spatial metric for navigation. I will propose that mathematically these patterns can be viewed as eigenfunctions of certain operators that generalize the familiar Fourier transform. Hence, during the talk I will provide evidence that the grid cell phenomenon can be cast as a problem in pattern formation and show how the neural substrate can act as linear (or mildly nonlinear) operator whose eigenfunctions tile the plane with periodic structures. Connections to classical Fourier analysis, spectral geometry, and pattern formation will be highlighted. This talk will be accessible to graduate students in mathematics and researchers interested in the interface of analysis, geometry, and neuroscience. As for the title, it will hopefully make sense by the end of the talk :)
    • slides Δ
  • February 25 (2025), 12:15, in room 2049 by Dominique Unruh
    • Title: Quantum crypto and the difficulties of proving it
    • Abstract: Quantum cryptography differs from traditional cryptography in that either the adversary or the honest protocol participants use quantum computers or quantum communication. This can lead to many novel possibilities, but it also means that we need to revisit everything: what's possible, what's impossible, how to prove security. Especially on the "how to prove security" side, things tend to get a lot harder. I will give a small intro into quantum computing, explain some difficulties in quantum crypto on the example of zero-knowledge, and in conclusion also tell a bit about how we can formally check quantum security proofs on the computer (Hoare logics etc.).
    • Slides (pdf) Slides (pptx)
  • January 21 (2025), 12:15, in room 2049, by Miika Hannula
    • Title: Dependence logic (and consistent query answering)
    • Abstract: Dependence logic extends first-order logic by introducing novel dependence atoms which explicitly assert dependence relations between variables. The aim is to obtain a formal language for modeling and reasoning about phenomena involving complex dependence notions. In general, dependence and independence are concepts that become manifest only in the presence of multitudes. To capture this, dependence logic employs team semantics which evaluates formulas over sets of variable assignments instead of single assignments, as in classical logics. This talk surveys the basic ideas and results in this field, which was introduced in 2007. Time permitting, we will revisit the theme of query evaluation, with a focus on handling uncertainty. Specifically, we will consider consistent query answering, which is a query evaluation paradigm for databases with inconsistent information. Since its inception in 1999, this topic has remained a central research area in the database theory community.
    • Slides
  • December 16 (2024), 16:15, in room 2049, by Miika Hannula
    • Title: Query Evaluation: Basics and Recent Developments
    • Abstract: Query evaluation is perhaps the most central problem pertaining to databases. Given a query q, a value c, and a database D, this problem is to determine whether or not c belongs to the output q(D) of the query q on the database D. Unfortunately, this problem is NP-complete even if we restrict to conjunctive queries which correspond to the most basic kind of SQL queries. What explains, then, that databases are so successful in practice? In this talk we look how theoretical investigation has helped to tame the query evaluation problem leading to efficient algorithms. We also look into recent developments regarding (a) query evaluation over inconsistent databases, and (b) application of information theory to join queries.
    • Slides