Date and Time  Speaker and Title  Abstract  Reference 

Friday, 22 Sep 2023, 11:00  TBD  TBD  
Friday, 20 Oct 2023, 11:00  TBD  TBD  
Friday, 17 Nov 2023, 11:00  TBD  TBD  
Friday, 8 Dec 2023, 11:00  TBD  TBD 
Date and Time  Speaker and Title  Abstract  Reference 

Friday, 26 May 2023, 11:00 
Prof. Russell W. F. Lai (Aalto University): InformationTheoretic Proofs + Cryptographic Commitments = Succinct Arguments, or “How to verifiably delegate computation?” 
In cryptography, a succinct argument system allows a prover to convince a
verifier that certain NP relations hold with very little communication cost.
Succinct arguments are useful, for example, to delegate a costly computation
to a powerful server such that the correctness of the computation can be
verified efficiently.
Most existing constructions of succinct arguments can be seen as compilations of the following building blocks:
In this overview talk, we will look at selected examples of the above objects, highlight recent advances, and point out open research directions. 
Slides 
Friday, 21 April 2023, 11:00 am 
Dr. Melissa Antonelli (University of Helsinki): On Counting Propositional Logic and Wagner's Hierarchy 
We will introduce an extension of classical propositional logic with counting quantifiers, intuitively expressing that a formula is true in a certain portion of its possible interpretations. Beyond admitting a sound and complete proof system, this logic is shown to be related with counting complexity classes. In particular, we will consider the counting hierarchy  a hierarchy of complexity classes introduced by Wagner in 1984/86 as a generalization of Meyer and Stockmeyer's one and able to express the complexity of many natural problems in which counting is involved  and prove that the complexity of deciding the validity for our counting formulas in (a special) prenex normal form perfectly matches the corresponding level of Wagner's hierarchy. (Original results are all part of a joint work with Ugo Dal Lago and Paolo Pistone.)  Handout 
Friday, 24 March 2023, 11:00 am 
Prof. Chris Brzuska (Aalto University): Cryptographic (r)evolutions: From MiniCrypt to Obfustopia 
In 1995, Impagliazzo [1] conceived of several worlds to structure the
landscape of averagecase hardness. For cryptographers of biggest interest
were MiniCrypt and CryptoMania. MiniCrypt is a world, where oneway
functions (OWFs) exist, functions that are (1) easy to compute, but (2) hard
to invert, on the average over a random input, but more "fancy" cryptography
does not exist. CryptoMania is a world where one can generate a oneway
function even with a trapdoor so that (1) computing the public function is
easy, (2) inverting the function is hard on the average, but (3) inverting
is easy when knowing the trapdoor. While such trapdoor functions were
originally controversial, they soon became a solid building block of our
internet security infrastructure. Moreover, the cryptographic community
explored even more adventurous assumptions, first discovering the
possibility of fully homomorphic encryption in 2009 and then
indistinguishability obfuscation in 2013. Fully homomorphic encryption
allows computation on encrypted data without knowing the keyand
indistinguishability obfuscation allows to turn any program into an
unintellegible version of it. We start our talk with a discussion of
MiniCrypt. Oneway functions are far more powerful than one might think at
first sight and even allow us to build pseudorandom generators, pseudorandom
functions and symmetrickey encryption schemes. We then move to the very
adventurious world of obfustopia and explore the conceptual implications of
indistinguishability obfuscation (iO). Clickbait version: 5 odd facts about
indistinguishability obfuscationyou won't believe the 1st and the 5th.
:)
Preparation (optional): Section 2 of Impagliazzo's essay [1] is a very fun 6.5pages long introduction to averagecase hardness. I turned Section 2 into a popular science talk [2] a couple of years ago, where I explain P vs. NP, averagecase hardness, MiniCrypt and CryptoMania in 15 minutes.
[1]
https://www2.karlin.mff.cuni.cz/~krajicek/ri5svetu.pdf 
Slides Handout 
Friday, 17 February 2023, 11:00 am 
Prof. Nikolaj Tatti (University of Helsinki): The gentle art of submodular minimisation 
Submodular optimisation is a wellstudied topic. While there is a surfeit of works studying submodular maximisation problems, the counterpart problemsubmodular minimisationis often forgotten. In this talk we revisit a classic iterative algorithm, based on a minimum norm theorem, for solving a generic submodular minimisation problem. While not being, strictly speaking, a polynomial algorithm, it is a more approachable and a more practical algorithm. We will show how submodular minimisation is related to a certain quadratic program, and demonstrate how this problem can be solved with a greedy method.  Slides 
Friday, 20 January 2023, 11:00 am 
Prof. Antti Honkela (University of Helsinki): Privacy accounting: evaluating privacy of compositions of differential privacy 
Differential privacy (DP) provides a firm theoretical foundation for privacypreserving computation and is widely deployed (US Census 2020; Apple, Google, Meta, Microsoft and many other companies). One of the main strengths of DP is composability: releasing the outputs of multiple DP mechanisms, called composition, is also DP. In my talk I will address the question of privacy accounting: how private such compositions really are. The field has progressed from increasingly complex analytical bounds to numerical methods capable of evaluating the exact cumulative privacy loss. Further open problems remain in accurate accounting for fully adaptive compositions, i.e. when privacy parameters and execution of future mechanisms depend on outcomes of previous mechanisms.  
Friday, 9 Dezember 2022, 11:00 am 
Prof. Jukka Suomela (Aalto University): Locality in online, dynamic, sequential, and distributed graph algorithms 
I will discuss the notion of locality in the context of graph problems, from
four different perspectives: online graph algorithms, dynamic graph
algorithms, sequential distributed algorithms, and parallel distributed
algorithms. I will use the graph coloring problem as a running example, and
I will explore settings like this:
This talk is based on joint work with Amirreza Akbari, Navid Eslami, Henrik Lievonen, Darya Melnyk, and Joona Särkijärvi, and there is a manuscript available at https://arxiv.org/abs/2109.06593 

Friday, 17 November 2022, 11:00 am 
Prof. Mikko Koivisto (University of Helsinki): Energyefficient algorithms – theoretical perspectives 
I will briefly review approaches to energyefficient computing, focusing on algorithms for power management and semireversible computing.  
Friday, 14 October 2022, 11:00 am 
Prof. Alexandru Paler (Aalto University): QRAM: Functionality, Models and Feasibility Outlook 
Quantum algorithms and machine learning methods require access to data which has to be stored in the memory of the quantum computer. Assuming a von Neumann architecture for quantum computers, then the QRAM/QROM is the quantum version of a classical computer's RAM/ROM. QRAM is using quantum bits (qubits) for storing classical information (classical bits) and is, as a consequence, an expensive component of a quantum computation. In this talk, I review the different types of QRAM/QROM and discuss their short and longterm feasibility for practical quantum computations.  
Friday, 9 September 2022, 11:00 am 
Prof. Kalle Kytölä (Aalto University): Formalization and interactive/automated theoremproving in mathematics 
Short tutorial on using the Lean theorem prover.  
Friday, 1 April 2022, 12:15 am 
Janne H. Korhonen (Aalto University): Distributed matrix multiplication 
Tutorial.  
Friday, 4 March 2022, 11:00 am 
Sándor KisfaludiBak (Aalto University): Hyperbolic intersection graphs & (quasi)polynomial time 
Tutorial.  
Friday, 4 February 2022, 11:30 am 
Miika Hannula (University of Helsinki): On consistent query answering over primary and foreign keys 
A database is called consistent if it satisfies all of its integrity constraints, and otherwise inconsistent. In consistent query answering (CQA), one asks whether a Boolean query holds true in every repair of an inconsistent database instance. The data complexity of CQA over primary key constraints and selfjoin free Boolean conjunctive queries is known to exhibit a complete complexity trichotomy. In this talk we consider extending this problem with unary foreign keys, and present a complexity dichotomy concerning firstorder definability.  
Friday, 23 December 2021, 10:15 am 
Prof. Petteri Kaski (Aalto University): Equations 
Tutorial followed by an Open Problems corner.  
Friday, 12 November 2021, 12:00 am 
Prof. Petteri Kaski (Aalto University): Algebraic fingerprinting in algorithmics 
Short tutorial. 