Helsinki Institute for Information
	Technology

HIIT Foundations Friday

HIIT Foundations Friday is a monthly get-together event for the community typically consisting of a tutorial and lunch as well as follow-up activity and discussions. This activity is part of the HIIT focus area on Foundations of Computing. On this page, you will find a brief overview of each talk, past and future as well as information about our current venue.

Venue

In the autumn season we will convene in Fabiankatu 24, Hall 532 on the downtown campus of the University of Helsinki. This is the same hall that was used during this season last year and also the very same as the Algorithms & Theory Days workshop.

Note the entrance to the seminar room (which used to be through the inner courtyard) has been changed. Now you can enter directly from Fabianinkatu 24A and take the elevator or the stairs to the 5th floor.


View Larger Map

Upcoming Talks

Date and Time Speaker and Title Abstract Reference
Friday, 13 Dec 2024, 11:15 Johannes Pekkilä (Aalto University): Graphics processors on exascale systems: performance and tuning strategies The majority of world's fastest supercomputers house either AMD- or Nvidia-based GPU partitions for accelerating data-parallel tasks. While built for the same goal, these platforms have key differences in both hardware architecture and software. In this tutorial, we'll review the key differences, recommend tuning strategies for large-scale computations, and look at stencil/convolution benchmarks on AMD MI100, MI250X, and Nvidia V100, A100, H100 graphics processors. We will also have a glimpse of the architecture of the upcoming Roihu and its implications to future programs.

Past Talks

Date and Time Speaker and Title Abstract Reference
Friday, 29 Nov 2024, 11:15 Jukka Suomela (Aalto University): Distributed Quantum Advantage So far, there are two known examples of graph problems that admit genuine distributed quantum advantage (in the sense that they can be solved asymptotically faster in the quantum-LOCAL model than the classical randomized LOCAL model). In this talk I will present both of them. Slides
Friday, 25 Oct 2024, 11:15 Dr. Tuomas Hakoniemi (University of Helsinki): Semialgebraic geometry and the decidability of the first order theory of reals In this tutorial we will present an introduction to semialgebraic geometry and its connections to the first order theory of reals. We will see that semialgebraic sets, the main objects of study in semialgebraic geometry, are quite tame with many nice structural properties. These properties imply a decision procedure for the first order theory of the reals, a result originally proved by Tarski in 1948. Time permitting, we will also discuss the computational complexity and some extensions of the problem.
Friday, 20 Sep 2024, 11:15 Prof. Petteri Kaski (Aalto University): A tutorial on Orlicz norms and quasinorms Orlicz norms and quasinorms consitute a useful tool across a range of applications beyond their origin in mathematical analysis and the study of function spaces that generalize Lp spaces. This tutorial will develop the basics of Orlicz norms in modern high-dimensional probability in the context of concentration analysis of polynomials of subexponential random variables—as well as, and time permitting—highlight recent applications of Orlicz norms in algorithm design proper.
Friday, 17 May 2024, 11:15 Prof. Jukka Suomela (Aalto University): Online Locality Meets Distributed Quantum Computing In our Foundations Friday in December 2022, we discussed locality in online, dynamic, and sequential graph algorithms. In December 2023, we discussed distributed quantum computing and causality. Today I will show all of this fits together into a single hierarchy of models of computing. It turns out that all of the models that we have seen so far can be sandwiched between the classical deterministic LOCAL model (weakest) and the randomized online-LOCAL model (strongest).

This is joint work with Amirreza Akbari, Xavier Coiteux-Roy, Francesco d'Amore, François Le Gall, Henrik Lievonen, Darya Melnyk, Augusto Modanese, Shreyas Pai, Marc-Olivier Renou, and Václav Rozhoň. For our recent manuscript on the topic, see https://arxiv.org/abs/2403.01903.

Slides
Friday, 26 Apr 2024, 11:15 Dr. Massimo Equi (University of Helsinki): The Origins of Fine-Grained Complexity When we do not succeed in proving unconditional lower bounds, we often resort to condition our statements on some hypothesis. For example, if we find a polynomial reduction from SAT to problem A that belongs to NP, we prove that A is not in P unless P=NP. Our result holds as long as the hypothesis that P is different from NP is true. However, for proving conditional lower bounds for problems in P, some other hypothesis is needed, and this is when fine-grained complexity makes its appearance. This field has been rapidly developing in recent years as more and more lower bounds have been proven for polynomial problems, conditioned on the Strong Exponential Time Hypothesis (SETH). This hypothesis claims that no truly subexponential time algorithm exists for CNF-SAT, that is SAT when the formula is in conjunctive normal form. In this talk, we will take a closer look at the origins of this hypothesis and the main arguments in its favour. Then, we will see how SETH is connected to polynomial problems via a reduction to the Orthogonal vectors problem, and how assuming SETH opens the door for proving a large number of conditional lower bounds for other polynomial problems. Slides
Friday, 22 Mar 2024, 11:15 Prof. Alexandru Tomescu (University of Helsinki): Safe algorithms: dealing with multiple solutions in practice In some real-world problems we need to discover an unknown object from partial information about it. Computational formulations of this task may easily admit multiple solutions, with no way to telling which one corresponds to the unknown object that we need to discover. This setting is classically tackled by enumerating all solutions and deferring this choice to e.g. humans. A different approach, however, is to output only those partial solutions that are common to all solutions, thus also to the unknown object. In this talk I will review some notions that have been proposed in this context (persistency, robustness, backbones, essentiality, safety), and give some simple examples of "safe algorithms". Slides
Friday, 16 Feb 2024, 11:15 Prof. Sándor Kisfaludi-Bak (Aalto University): ER-completeness in geometric algorithms Geometric algorithms often run into precision difficulties: for example, computing the total length of n segments (even when the segments have integer-coordinate endpoints) is of unknown complexity. We have discovered that several problem flavors, such as incidence, packing, visibility where the optimum output "requires" exponential precision numbers in some manner, which intuitively places them outside NP. Recently the class ER or (ETR), the existential theory of the reals arose as the natural complexity class for such continuous geometric problems. ER consists of those problems that can in polynomial time be reduced to checking if a semi-algebraic set is empty, or equivalently, to an existentially quantified Boolean formula of polynomial inequalities over the reals with integer coefficients. Today we have a wealth of problems that are ER-complete, including prominent problems such as art gallery or low-rank matrix completion. During the tutorial I will introduce the complexity class and we will get an intuition about some of its complete problems. We will learn about how one can know (and attempt to prove) that a problem belongs there, as well as the state of the art for solving such problems. Slides
Friday, 26 Jan 2024, 11:15 Prof. Petteri Kaski (Aalto University): A primer to Strassen-preordered semirings and asymptotic spectra This talk is a short primer to Strassen-preordered semirings and their asymptotic spectra based on the recent exposition by Wigderson and Zuiddam (cf. https://staff.fnwi.uva.nl/j.zuiddam/papers/convexity.pdf). We aim to look at and motivate three examples: (i) real numbers at least one, (ii) restriction-preordered tensors, and (iii) cohomomorphism-preordered graphs; the tensor and graph examples in particular capture the asymptotic rank of a tensor and the Shannon capacity of a graph, respectively. We will also seek to sketch Strassen's duality between asymptotic rank and the asymptotic spectrum formed by the monotone homomorphisms. Slides
Friday, 8 Dec 2023, 11:15 Prof. Jukka Suomela (Aalto University): Causal limits of distributed quantum computation In this talk, I will explore the following research questions:
  1. Classical limits of distributed computation: what can be computed efficiently in a computer network that consists of classical computers, connected with classical communication channels?
  2. Limits of distributed quantum computation: what can be computed efficiently in a computer network that consists of quantum computers, connected with quantum communication channels?
  3. Causal limits of distributed computation: what could be computed efficiently in a magical computer network that can do anything as long as it does not violate physical causality (i.e., allow faster-than-light communication)?
Here question 1 is nowadays well-understood, while question 2 is wide open, and directly tackling question 2 seems to be very challenging. However, question 3 is much easier to approach: in particular, we do not need to understand anything about quantum physics. Yet as soon as we understand the causal limits, we also understand something about the limits of distributed quantum computation; after all, quantum networks cannot violate causality. In the best case, we can tightly sandwich quantum networks between classical and causal bounds, and this way also exclude any quantum advantage—all this without any need to directly deal with anything quantum.

This is joint work with Xavier Coiteux-Roy, Francesco d'Amore, Rishikesh Gajjala, Fabian Kuhn, François Le Gall, Henrik Lievonen, Augusto Modanese, Marc-Olivier Renou, Gustav Schmid, and many others. For our recent manuscript on the topic, see https://arxiv.org/abs/2307.09444

Slides
Friday, 17 Nov 2023, 11:15 Prof. Petteri Kaski (Aalto University): Bilinear algorithms and asymptotic tensor rank This talk is a short tutorial to bilinear (trilinear) algebraic algorithms and the study of asymptotic tensor rank of tensors. My intent is to review the elementary tools for fast evaluation of bilinear maps (trilinear forms) whose defining three-tensor decomposes into a Kronecker product of smaller tensors. A key example of this setting is the bilinear map that multiplies two n-by-n matrices (the trace of the product of three n-by-n matrices) for composite n. This starting point gives rise to a rich theory of asymptotic spectra of tensors developed by Strassen, with a recent exposition given by Wigderson and Zuiddam (cf. https://staff.fnwi.uva.nl/j.zuiddam/papers/convexity.pdf).
Friday, 27 Oct 2023, 11:15 Prof. Juho Hirvonen (Aalto University): Perspectives on mechanism design Mechanisms are optimisation algorithms with additional guarantees in game-theoretic settings. For example, the famous deferred acceptance algorithm of Gale and Shapley assigns matches truthfully: agents will alwaysd maximise their outcome by announcing their true preferences. In economics these “additional guarantees” are often more important than the computational aspects of mechanisms. In this tutorial I will review mechanism design from an economics perspective, as a computer scientist. I will present some of the most important results and focus on the additional algorithmic challenges posed by the strategic setting: What are the different goals in mechanism design? How do they translate to algorithmic problems? What can go wrong when they are implemented in practice? Slides
Friday, 22 Sep 2023, 11:00 Dr. Tuomas Hakoniemi (University of Helsinki): Pigeons! - Selected topics in Proof Complexity Proof complexity is a field that lives in the intersection of computational complexity theory and mathematical logic. It studies the computational resources needed to prove mathematical statements in formal proof systems with the main emphasis being in proof size lower bounds.In this presentations we discuss some selected themes in proof complexity through few representative results and proof methods. We try to give a broad overview of the field, and see how proof complexity relates to other fields of theoretical computer science and mathematical logic more generally. Slides
Friday, 26 May 2023, 11:00 Prof. Russell W. F. Lai (Aalto University): Information-Theoretic 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:

  1. an information-theoretic proof system, e.g. a probabilistically checkable proof (PCP), and
  2. a cryptographic commitment scheme with special openings, e.g. a vector commitment scheme.

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 average-case hardness. For cryptographers of biggest interest were MiniCrypt and CryptoMania. MiniCrypt is a world, where one-way 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 one-way 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 key---and indistinguishability obfuscation allows to turn any program into an unintellegible version of it. We start our talk with a discussion of MiniCrypt. One-way functions are far more powerful than one might think at first sight and even allow us to build pseudorandom generators, pseudorandom functions and symmetric-key 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 obfuscation---you won't believe the 1st and the 5th. :-)

Preparation (optional): Section 2 of Impagliazzo's essay [1] is a very fun 6.5-pages long introduction to average-case hardness. I turned Section 2 into a popular science talk [2] a couple of years ago, where I explain P vs. NP, average-case hardness, MiniCrypt and CryptoMania in 15 minutes.

[1] https://www2.karlin.mff.cuni.cz/~krajicek/ri5svetu.pdf
[2] The talk starts at min 2:30, the discussion of Impagliazzo's 5 worlds starts at 8:30 and ends at around 23:00 https://www.youtube.com/watch?v=7H4qN73Y36Q

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 well-studied topic. While there is a surfeit of works studying submodular maximisation problems, the counterpart problem---submodular minimisation---is 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 privacy-preserving 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 December 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:
  • Online graph algorithms: The adversary reveals the graph one node at a time. How far do you need to see around a node until it is safe to pick its color?
  • Dynamic graph algorithms: The adversary constructs the graph one edge at a time, and you need to maintain a valid coloring after each addition. How far around the new edge do you need to modify the solution?
  • Distributed graph algorithms: Each node has to choose its own color simultaneously in parallel based on its local neighborhood. How far does it need to see?
While these are different questions in general, we can show that there are families of graph problems for which all these notions are equal to each other.

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): Energy-efficient algorithms – theoretical perspectives I will briefly review approaches to energy-efficient computing, focusing on algorithms for power management and semi-reversible 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 long-term feasibility for practical quantum computations.
Friday, 9 September 2022, 11:00 am Prof. Kalle Kytölä (Aalto University): Formalization and interactive/automated theorem-proving 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 Kisfaludi-Bak (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 self-join 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 first-order 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.