#### Overview

The focus area on Foundations of Computing pursues fundamental research at the algorithmic and mathematical foundations of computing, integrating a broad range of expertise including multiple areas of algorithmics, artificial intelligence, computational complexity, cryptography, distributed computing, logic, and quantum computing.

**Interested in joining us? **

To participate in our activities, attend our open events described below. To get invited to email lists, chat channels, and so forth., please contact Petteri Kaski (Aalto University) or Mikko Koivisto (University of Helsinki). Our community is growing. See CS Theory at Aalto for a non-exhaustive list of researchers involved.

#### Activities

**Helsinki CS Theory Seminar**. A weekly series of talks on a broad scope of CS theory hosted by the Aalto University CS Theory Group. Link to seminar page.

**Helsinki Logic Seminar. **A weekly series of talks in mathematical logic hosted by the Helsinki Logic Group. Link to seminar page.

**Foundations Friday. **A monthly get-together event for the community typically consisting of a tutorial and lunch as well as follow-up activity and discussions. Link to seminar page.

#### Research Highlights

**Distributed Symmetry Breaking on Power Graphs via Sparsification**

*Maus, S. Peltonen, J. Uitto *

Ruling sets are a central tool in distributed graph algorithms, in particular, in the strong graph *shattering **
*framework. We provide new tools and efficient algorithms to compute rulings sets.

**PODC 2023 (to appear)**

**Locality in online, dynamic, sequential, and**** ****distributed graph algorithms**

*Akbari, N. Eslami, H. Lievonen, D. Melnyk, **J. Särkijärvi, J. Suomela*

We give a unifying view of the concept of *locality* in four settings: distributed algorithms, sequential greedy algorithms, dynamic algorithms,and online algorithms.

ICALP 2023 (to appear)

**Fast dynamic programming in trees in the MPC model **

*Gupta, R. Latypov, Y. Maus, S. Pai, S. Särkkä, **J. Studený, J. Suomela, J. Uitto, H. Vahidi *

If we have a tree of diameter *D*, it is easy to do dynamic programming with parallel algorithms in *O*(*D*) rounds:

start with the leaf nodes and propagate information upwards. In this work we show that we can dynamic

programming in the massively parallel computation model exponentially faster, in *O*(log *D*) rounds.

**
**SPAA 2023 (to appear)

**Optimal Deterministic Massively Parallel Connectivity on Forests**** **

*Balliu, R. Latypov, Y. Maus, D. Olivetti, J. Uitto*

A parallel algorithm that detects the connected components of an input forests in conditionally optimal time and space.

SODA’23 https://doi.org/10.1137/1.9781611977554.ch99

**Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomposition**

*Chalermsook, M. Gupta, W. Jiamjitrak, **N. O. Acosta, A. Pareek, S. Yingchareonthawornchai*

We improve the analysis of Greedy algorithm for online binary search tree, a candidate for dynamic optimality conjecture, for a variety of input sequences. Among various improvements with our new techniques, we also resolve a long-standing post-order traversal conjecture for Greedy.

SODA’23 https://doi.org/10.1137/1.9781611977554.ch22

**Efficient Laconic Cryptography from Learning With Errors**

*Döttling, D. Kolonelos, R. W. F. Lai, C. Lin, G. Malavolta, A. Rahimi*

Laconic cryptography is an emerging paradigm that studies secure two-party computation which is sender-optimised. Although this paradigm has led to tremendous progress in recent years, all existing constructions rely on highly impractical non-black-box cryptographic techniques, making them only of theoretical interest. We provide, for the first time, completely algebraic constructions of laconic primitives which can be proven secure under the standard Learning With Errors (LWE) assumption. We also provide the first proof-of-concept implementation for any laconic primitives, demonstrating that the construction is indeed practical.

EUROCRYPT’23 https://doi.org/10.1007/978-3-031-30620-4_14 https://ia.cr/2023/404

**Lattice-based Succinct Arguments from Vanishing Polynomials**

*Cini, R. W. F. Lai, G. Malavolta*

Succinct arguments allow a prover to convince a verifier of the validity of any statement in a language, with minimal communication and verifier’s work. We present some new approaches to constructing efficient lattice-based succinct arguments. Our main technical ingredient is a new commitment scheme based on vanishing polynomials, a notion borrowed from algebraic geometry. A few highlights:

(i) The first recursive folding protocol for linear relations with polylogarithmic verifier runtime. Traditionally, the verifier runtime has been the efficiency bottleneck for such protocols (regardless of the underlying assumptions).

(ii) The first verifiable delay function (VDF) based on lattices, building on a recently introduced sequential relation.

(iii) The first lattice-based linear-time prover succinct argument for NP, in the preprocessing model.

CRYPTO’23

**Lattice-Based Timed Cryptography**

*W. F. Lai, G. Malavolta*

Timed cryptography studies primitives that retain their security only for a pre-determined amount of time, such as proofs of sequential work and time-lock puzzles. This feature has proven to be useful in a large number of practical applications, e.g., randomness generation, sealed-bid auctions, or fair multi-party computation. However, the current state of affairs in timed cryptography is unsatisfactory: Virtually all efficient constructions rely on a single sequentiality assumption, namely that repeated squaring in unknown order groups cannot be parallelized. This is a single point of failure in the classical setting and is even false against quantum adversaries.

We put forward a new sequentiality assumption, which essentially says that a repeated application of the standard lattice-based hash function cannot be parallelized. We provide concrete evidence of the validity of this assumption and, to substantiate its usefulness, we show how it enables a new proof of sequential work, with a stronger sequentiality guarantee than prior hash-based schemes.

CRYPTO’23

**Publicly Verifiable Zero-Knowledge and Post-Quantum Signatures From VOLE-in-the-Head**

*Baum, L. Braun, C. Delpech de Saint Guilhem, M. Klooß, E. Orsini, L. Roy, P. Scholl*

We present a new method for transforming zero-knowledge protocols in the designated verifier setting into public-coin protocols, which can be made non-interactive and publicly verifiable. Our transformation applies to a large class of ZK protocols based on oblivious transfer. Our resulting ZK protocols have linear proof size, and are simpler, smaller and faster than related approaches based on MPC-in-the-head.

As an application, we present FAEST, a post-quantum signature scheme based on AES. FAEST is the first AES-based signature scheme to be smaller than SPHINCS+, with signature sizes between 5.6 and 6.6kB at the 128-bit security level. Compared with the smallest version of SPHINCS+ (7.9kB), FAEST verification is slower, but the signing times are between 8x and 40x faster.

CRYPTO’23

**Sinkless orientation made simple**

*Balliu, J. H. Korhonen, F. Kuhn, H. Lievonen, **D. Olivetti, S. Pai, A. Paz, J. Rybicki, S. Schmid, **J. Studený, J. Suomela, J. Uitto*

The sinkless orientation problem plays a key role in understanding the foundations of distributed computing. Any deterministic algorithm for sinkless orientation requires Ω(log n) rounds, but all previously known proofs for this result take a complicated detour through randomized algorithms.

We present a new, much simpler proof that gives the result directly for deterministic algorithms.

SOSA’23 https://doi.org/10.1137/1.9781611977585.ch17

**On Inference and Learning With Probabilistic Generating Circuits**

*Harviainen, P. R. Vaidyanathan, M. Koivisto*

We give significantly faster inference algorithms for probabilistic generating circuits (PGCs). We also show that it is NP-hard to recognize whether a given circuit encodes a probability generating function, hampering efficient learning of PGCs from data.

UAI’23 (to appear)

#### Research Highlights

**The Shortest Even Cycle Problem is Tractable**

*A. Björklund, T. Husfeldt, P. Kaski.*

Given a directed graph as input, we show how to efficiently find a shortest (directed, simple) cycle on an even number of vertices.

STOC’22 https://doi.org/10.1145/3519935.3520030

**Deterministic (1+𝜀)-Approximate Maximum matching with poly(1/𝜀) Passes in the Semi-Streaming Model and Beyond **

*M. Fischer, S. Mitrović, J. Uitto.*

In the streaming setting, an input graph is given as a stream of edges and, at any time, the algorithm is allowed to keep a (roughly) linear amount of edges in memory. We give a streaming algorithm that makes a polynomial (in 𝜀) number of passes over the stream and finds an almost optimal matching.

STOC’22 https://doi.org/10.1145/3519935.3520039

**Sparse matrix multiplication in the low-bandwidth model**

*Gupta, J. Hirvonen, J. H. Korhonen, J. Studený, J. Suomela*

We study the multiplication of uniformly sparse matrices in a distributed setting. If each row and column has at most d nonzero elements, there is a simple algorithm that solves

the problem in O(d²) communication rounds. We show that it is possible to break this quadratic barrier.

SPAA’22 https://doi.org/10.1145/3490148.3538575

**Sparsifying, Shrinking and Splicing for Minimum Path Cover **** ****in Parameterized Linear Time**

*Cáceres, M. Cairo, B. Mumey, R. Rizzi, A. I. Tomescu*

The minimum path cover problem asks for a minimum-size set of paths covering all nodes of a directed acyclic graph. It has various applications in scheduling, distributed computing, databases, bioinformatics. We prove that the problem can be solved parameterized-linear time, namely in time O(k3n + m), where k is

the size of such set of paths, and n and m are the number of nodes and arcs of the graph, respectively.

SODA’22 https://doi.org/10.1137/1.9781611977073.18

**Online search for a hyperplane in high-dimensional Euclidean space**

*Antoniadis, R. Hoeksma, S. Kisfaludi-Bak, K. Schewior*

We consider the online search problem in which a server starting at the origin of a d-dimensional Euclidean space has to find an arbitrary hyperplane. The best-possible competitive ratio and the length of the shortest curve from which each point on the d-dimensional unit sphere can be seen are within a constant

factor of each other. We show that this length is in Ω(d) ∩ O(d3/2).

*Inform. Process. Lett.* (2022)

https://doi.org/10.1016/j.ipl.2022.106262

**Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs**

*Bringmann, S. Kisfaludi-Bak, M. Künnemann, A. Nusser, Z. Parsaeian*

We initiate the study of diameter computation in geometric intersection graphs from the fine-grained complexity perspective. In this work we (conditionally) rule out sub-quadratic algorithms in several classes of intersection graphs, i.e., algorithms of running time O(n2-δ) for some

δ > 0. We show that the hardness of approximation may also depend on dimensionality: for axis-parallel unit hypercubes in ℝ12, distinguishing between diameter 2 and 3 needs quadratic time (ruling out (3/2 – ε)-approximations), whereas for axis-parallel unit squares, we give an algorithm that distinguishes between diameter 2 and 3 in near-linear time. Note that many of our lower bounds match the best known algorithms up to sub-polynomial factors.

SoCG’22 https://doi.org/10.1016/j.ipl.2022.106262

**Lattice-Based SNARKs: Publicly Verifiable, Preprocessing, and Recursively Composable**

*R. Albrecht, V. Cini, R. W. F. Lai, G. Malavolta, S. A. K. Thyagarajan*

A succinct non-interactive argument of knowledge (SNARK) allows a prover to produce a short proof that certifies the veracity of a certain NP-statement. We propose the first lattice-based SNARK that simultaneously satisfies many desirable properties: It (i) is tentatively post-quantum secure, (ii) is publicly-verifiable, (iii) has a logarithmic-time verifier and (iv) has a purely algebraic structure making it amenable to efficient recursive

composition. Our construction stems from a general technical toolkit that bridges pairing-based and lattice-based cryptography.

CRYPTO’22 https://doi.org/10.1007/978-3-031-15979-4_4 https://ia.cr/2022/941

**Security Analysis of the MLS Key Derivation**

* Brzuska, E. Cornelissen, K. Kohbrok*

Analysis of the tree-based key derivations in the new cryptographic group messaging protocol MLS.

Security & Privacy 2022

https://doi.org/10.1109/SP46214.2022.9833678

Suggested protocol modifications were integrated into the IETF standard.

https://github.com/mlswg/mls-protocol/pull/453

**On Building Fine-Grained One-Way Functions from ****Strong Average-Case Hardness**

* Brzuska, G. Couteau*

We show that building one-way functions from average-case hardness is impossible in a black-box way even when assuming self-amplifying, exponential average-case hardness and when trying to build a one-way function with polynomial security gap.

EUROCRYPT’22

https://doi.org/10.1007/978-3-031-07085-3\_20

**Trustworthy Monte Carlo**

*Harviainen, P. Kaski, M. Koivisto*

We extend Monte Carlo estimators so that the correctness of outsourced computations can be verified.

NeurIPS’22 (to appear, https://openreview.net/forum?id=jglXPY6gH-1)

**Deterministic Small Vertex Connectivity in Almost Linear Time**

*Saranurak, S. Yingchareonthawornchai*

We study vertex connectivity through the lens of derandomization. We provide an almost linear time algorithm for small connectivity using expanders and vertex cut sparsifiers, breaking the

quadratic-time barrier.

**Lower Bounds for Maximal Matchings and Maximal Independent Sets**

* A. Balliu, S. Brandt, J. Hirvonen, D. Olivetti, M. Rabie, J. Suomela.*

There is a simple distributed algorithm for finding a maximal matching in a bipartite graph: nodes on one side send proposals one by one to their neighbors, and nodes on the other side accept the first proposal they get. In a graph of maximum degree Δ this takes O(Δ) rounds. We show that this is optimal: any distributed algorithm requires Ω(Δ) rounds in large networks.

*J. ACM* (2021) https://doi.org/10.1145/3461458

**Approximating the Permanent with Deep Rejection Sampling**

* J. Harviainen, A. Röyskö, M. Koivisto.*

Our deep rejection sampling method yields the fastest known practical approximation scheme for the permanent of nonnegative matrices. The key idea is to compute tighter upper bounds for the permanent by exact evaluation of the permanent of appropriate rectangular matrices.

NeurIPS’21 [link to online proceedings]

**Exponential suppression of bit or phase errors with ****cyclic error correction**

*Chen, K.J. Satzinger, …., A. Paler, …, A. Megrant, J. Kelly*

We perform error detection with a small logical qubit and show that the results agree with numerical simulations.

These experimental demonstrations provide a foundation for building a scalable fault-tolerant quantum computer with superconducting qubits.

*Nature* 595 (2021)

https://www.nature.com/articles/s41586-021-03588-y