Helsinki CS Theory Seminar

Joint work with Arnaud Durand and Juha Kontinen.

In this talk, we explore algorithmic meta-theorems for distributed certification, which aim to efficiently certify all predicates expressible in specific logics, provided the input graph belongs to a specific graph class. We demonstrate how celebrated meta-theorems from centralized computing can be adapted to the distributed setting with two key examples. First, we present a distributed certification analog of Courcelle's theorem: every graph predicate expressible in Monadic Second-Order (MSO) logic can be efficiently certified on graphs of bounded treewidth. Second, we establish that every graph predicate expressible in First-Order (FO) logic can be efficiently certified on graphs of bounded expansion, offering a distributed certification counterpart to the celebrated results of Nešetřil and Ossona de Mendez.

This talk is based on ongoing work with Nutan Limaye and Iddo Tzameret.

Joint work with Frank Sommer, Manuel Sorge, and Stefan Szeider.

In this talk we overview the evasive LWE assumption, including why it appears useful to cryptographic proofs of advanced primitives, the different types of its variants, and recently discovered counterexamples against some of the stronger ones. We end the talk by restating the assumption in its simplest form as a lattice problem, and ask the question of whether it may be proven true, conditionally or unconditionally.

This talk is an episode of the talk "On the Expanding Zoo of Lattice Assumptions" by Russell Lai during the 2024 Helsinki Algorithms & Theory Days. Part of this talk is based on joint work with Chris Brzuska and Akin Ünal.

Joint work with Ari Conati and Matti Järvisalo.

What if, instead of preventing bad behavior by a malicious attacker, we guarantee “accountability,” i.e., we can provide irrefutable evidence of the bad behavior and the identity of the perpetrator of those illegal actions? Much in the way we prevent crime in the real world, we can prevent bad behavior in a distributed system: either the protocol succeeds, or alternatively we record sufficient information to catch the criminal and take remedial actions. Accountability has been increasingly discussed as a desirable property in blockchains like Ethereum, which “slashes” the stake of cheating users.

In this talk, I will give an overview of accountability in distributed systems, with a focus on decision problems like consensus. We begin with Polygraph, a (provably) accountable consensus protocol, and then describe the ABC transformation for making every consensus protocol accountable. Finally, we talk about the underlying theory of accountability and the necessary and sufficient conditions for achieving accountability.

This talk covers joint work with Pierre Civit, Vincent Gramoli, Rachid Guerraoui, Jovan Komatovic, Zarko Milosevic, and Adi Serendinschi.

We construct modular, verifier-succinct reductions of knowledge for the bounded-norm satisfiability of structured-linear relations, without any soundness gap, under the vanishing SIS assumption, while maintaining polynomial (and concretely small) modulus. Moreover, our construction works over any field $\mathcal{K}$ which admits polynomial-size subtractive sets.

Joint work with Michael Klooß, Russell W. F. Lai, and Ngoc Khanh Nguyen.

For EMDuT in $ℝ^1$, we present an $Õ(n^2)$-time algorithm. We also show that this algorithm is nearly optimal by presenting a matching conditional lower bound based on the Orthogonal Vectors Hypothesis. For EMDuT in $ℝ^d$, we present an $Õ(n^{2d+2})$-time algorithm for the $L_1$ and $L_\infty$ metric. We show that this dependence on $d$ is asymptotically tight, as an $n^{o(d)}$-time algorithm for $L_1$ or $L_\infty$ would contradict the Exponential Time Hypothesis (ETH). Prior to our work, only approximation algorithms were known for these problems.

Joint work with Karl Bringmann, Frank Staals and Karol Węgrzycki.

While the two techniques appear quite different at first glance, a closer inspection reveals that there are also striking similarities, suggesting that a simultaneous study of the techniques might reveal closer connections and ways how to use insights from either to improve the respectively other, in both distributed algorithms and descriptive combinatorics. Moreover, there are many open questions about either technique individually, making them primary targets of research on impossibility results.

In this talk, we will take a tour through the workings of both techniques in their current generalized forms (from the perspective of distributed algorithms), with an emphasis on Marks' technique as it might be much less known to researchers in algorithms.

Joint work with Esther Galby and Andrea Munaro.

In this talk, we focus on the second step of the sparsification framework. We discuss algorithms for graphs that are already sparse where the sparsification step becomes irrelevant and nevertheless, many problems remain hard. We pay particular attention to the total space used in the algorithms and give algorithmic techniques tailored for sparse graphs.

Joint work with L. Sunil Chandran and Kuldeep S. Meel.

Our main result is an explicit construction of a sequence $\mathcal{U}_d$ of zero-one-valued tensors that is universal for the worst-case tensor exponent; more precisely, we show that $\sigma(\mathcal{U}_d)=\sigma(d)$ where $\sigma(d)=\sup_{T\in\mathbb{F}^d\otimes\mathbb{F}^d\otimes\mathbb{F}^d}\sigma(T)$. We also supply an explicit universal sequence $\mathcal{U}_\Delta$ localised to capture the worst-case exponent $\sigma(\Delta)$ of tensors with support contained in $\Delta\subseteq [d]\times[d]\times [d]$; by combining such sequences, we obtain a universal sequence $\mathcal{T}_d$ such that $\sigma(\mathcal{T}_d)=1$ holds if and only if Strassen's asymptotic rank conjecture [Progr. Math. 120 (1994)] holds for $d$. Finally, we show that the limit $\lim_{d\rightarrow\infty}\sigma(d)$ exists and can be captured as $\lim_{d\rightarrow\infty} \sigma(D_d)$ for an explicit sequence $(D_d)_{d=1}^\infty$ of tensors obtained by diagonalisation of the sequences $\mathcal{U}_d$. As our second result we relate the absence of polynomials of fixed degree vanishing on tensors of low rank, or more generally asymptotic rank, with upper bounds on the exponent $\sigma(d)$. Using this technique, one may bound asymptotic rank for all tensors of a given format, knowing enough specific tensors of low asymptotic rank.

Joint work with Mateusz Michałek.

This is joint work with David Karpuk and Camilla Hollanti.

Based on joint work with Daniel Dadush, Bento Natura, Neil Olver and László Végh.

As an application of our separator theorem, we will see that both Independent Set and TSP have near-linear time FPTASes in planar delta-hyperbolic graphs for any constant delta, running in Õ(n)* 2^{O(delta^2)} / eps^{O(delta)} time. For Independent Set this running time is essentially tight under the Exponential Time Hypothesis (ETH).

In his seminal work in 2005, McGregor presented a randomized (1 + epsilon)-approximation algorithm for matching that requires an exponential (in epsilon) number of passes. After McGregor's result, Eggert et al. presented a deterministic algorithm with polynomial number of passes for bipartite graphs. Later, Tirodkar gave an exponential deterministic algorithm for general graphs. However, McGregor's algorithm remained the fastest for general graphs. In our work, we discovered an algorithm that reaches a polynomial number of passes for general graphs yielding an exponential improvement over the previous work. Satisfyingly, our algorithm is also deterministic.

Joint work with Pekka Parviainen.

In this talk, I will describe a deterministic algorithm for checking $k$-vertex connectivity in time proportional to making $\min\{k^2, n\}$ max-flow calls, and, hence, in $\widehat{O}(m\min\{k^{2},n\})$ time using the deterministic max-flow algorithm by [Brand et al. FOCS'23]. Our algorithm gives the first almost-linear-time bound for all $k$ where $\sqrt{\log n}\le k\le n^{o(1)}$ and subsumes up to a sub-polynomial factor the long-standing state-of-the-art algorithm by [Even'75] which requires $O(n+k^{2})$ max-flow calls. For large $k$, the algorithm runs in $\widehat O(mn)$ time, which improves over the state-of-the-art deterministic $\widehat{O}(mn^{1.5})$-time algorithm [Gabow, FOCS'00]. Our key technique is based on Ramanujan expanders and derandomization of the kernelization technique of [Li et al. STOC'21] for which their kernel construction was randomized.

Joint work with Yonggang Jiang, Chaitanya Nalam, and Thatchaphol Saranurak.

Joint work with Konstantin Avrachenkov and Maximilien Dreveton.

The main technical contribution is a novel sampling procedure that returns a small subgraph such that almost all nodes in the input graph are adjacent to the sampled subgraph. An MIS on the sampled subgraph provides a 2-ruling set for a large fraction of the input graph. As a technical challenge, we must handle the remaining part of the graph, which might still be relatively large. We overcome this challenge by showing useful structural properties of the remaining graph and show that running our process twice yields a 2-ruling set of the original input graph with high probability.

The talk is based on a paper that appeared in DISC 2023 and is joint work with Mélanie Cambus, Fabian Kuhn, and Jara Uitto.

Using these quadtrees we build geometric spanners. Near-linear size (1+ϵ)-spanners do not exist in hyperbolic spaces, but we are able to create a Steiner spanner that achieves a spanning ratio of 1+ϵ with O(n) edges for constant d and ϵ, using a simple construction that can be maintained dynamically. As a corollary we also get a (2+ϵ)-spanner (in the classical sense) of the same size, where the spanning ratio 2+ϵ is almost optimal among spanners of subquadratic size.

Finally, we show that our Steiner spanner directly provides a solution to the approximate nearest neighbour problem: given a point set P in d-dimensional hyperbolic space we build the data structure in O(n log n) time, using O(n) space. Then for any query point q we can find a point p∈P that is at most 1+ϵ times farther from q than its nearest neighbour in P in O(log n) time. Moreover, the data structure is dynamic and can handle point insertions and deletions with update time O(log n).

This is joint work with Sándor Kisfaludi-Bak.

This is joint work with Yuichi Yoshida (NII).

This talk is based on joint works with Nashlen Govindasamy, Nutan Limaye and Iddo Tzameret.