"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

  • April 29 (2025), 12:15, in room 2049 by Ago-Erik Riet
    • Title: Distributed data storage, service and computation
    • Abstract: The amount of data in the world is growing at an exponential rate. It is important that the data be stored, e.g. in a cloud service such as Google, Amazon, Microsoft clouds, securely, so that its integrity is preserved, it is always available, and updates and computations on the data work well. Typically linear codes with special properties are applied in such distributed storage systems. I will introduce some requirements such a system might need to satisfy. I will introduce regenerating codes, locally repairable codes, codes allowing for efficient data updates, and give some examples. In the second part of the talk I will discuss distributed storage systems with a focus on data recovery, the so-called distributed service systems that need to serve hot data. An example is a system storing newspaper articles where the relative demands for different articles may change. I will introduce the service rate region, classical and asynchronous batch codes, and private information retrieval (PIR) codes. I will talk about a nice fundamental mathematical conjecture about batch codes and discuss its connections with some recent work in combinatorics.

Past Talks

  • April 22 (2025), 12:15, in room 2049 by Vitaly Skachek
    • Title: Achieving reliable communications and data storage using error-correcting codes
    • Abstract: In this survey talk, we discuss fundamental concepts in coding theory. We start with the Shannon-Weaver communications model and its main components. Then, we discuss error-correcting codes and their main parameters. We present Reed-Solomon codes, and their application to secret-sharing in cryptography. We also discuss low-density parity-check codes. Finally, we discuss some new applications of coding theory in flash memories and in distributed data storage.
    • slides
  • 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 (April 1)
    • slides (April 8)
    • 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
  • 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