"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

• 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.).
• March 4 (2025): no seminar (Estonian Winter School in Computer Science)
• March 11 (2025) 12:15, in room 2049 by Raul Vicente to be confirmed
• (Original talk cancelled due to sickness -- postponed to the next free slot) February 18 (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. I will give a short overview of the state of the art.
  • 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

• 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