Helsinki CS Theory Seminar

In a prior work [Thejaswi et al. KDD 2022)], we showed that even satisfying fair-range constraints is NP-hard, thereby making the problem inapproximable to any polynomial factor. In this work, our first main result strengthens this by showing that inapproximability persists even when the fair-range constraints are trivially satisfiable, highlighting the computational complexity of the clustering task itself. These inapproximability results hold even on tree metrics and when the number of groups is logarithmic in the size of the facility set.

In light of strong inapproximability results, we focus on design of algorithms in a practical setting where the number of groups is constant. We give a polynomial-time $O(\log k)$- and $O(\log^2 k)$-approximation algorithm for $k$-median and $k$-means objectives, respectively, in this regime. Furthermore, we design constant factor approximation algorithms for these problems that run in fixed parameterized tractable time in $k$. All our approximation guarantees match the best bounds for capacitated clustering without fair-range constraints. Finally, we show that our polynomial-time algorithms are, to our knowledge, the first to have provable approximation guarantees that can practically solve problem instances of modest size. This is a joint work with Ameet Gadekar.

This is a joint work with Mohsen Amidzadeh, Teemu Kämäräinen, Matti Siekkinen, and Mario Di Francesco.

Joint work with Guillermo Esteban (Universidad de Alcala) and Tyler Tuttle (Carleton University).

Our algorithm is an Arora-style dynamic program based on a randomly shifted hierarchical decomposition. However, we introduce a new hierarchical decomposition called the hybrid hyperbolic quadtree to achieve the desired large-scale structure, which deviates significantly from the recently proposed hyperbolic quadtree of Kisfaludi-Bak and Van Wordragen (JoCG'25). Moreover, we have a new non-uniform portal placement, and our structure theorem employs a new weighted crossing analysis. We believe that these techniques could form the basis for further developments in geometric optimization in curved spaces.

In this talk I will present a hard CNF instance for IPS refutations computed by read-once algebraic branching programs. The proof is based on a monotone feasible interpolation property with respect to monotone span programs, and the existing exponential lower bounds of Robere et al. for this model of monotone computation.

This is joint work with Nutan Limaye and Iddo Tzameret.

In this talk, we will show both deterministic and randomized algorithms for GR that require a polylogarithmic number of CC queries in the number of vertices for bounded degree and more generally bounded degeneracy graphs as well as lower bounds for the query complexity.

Joint work with Pekka Parviainen.

1) We show that there is no distributed quantum advantage for any linear program. Put otherwise, if there is a quantum-LOCAL algorithm 𝒜 that finds an α-approximation of some linear optimization problem Π in T communication rounds, we can construct a classical, deterministic LOCAL algorithm 𝒜' that finds an α-approximation of Π in T rounds. As a corollary, all classical lower bounds for linear programs, including the KMW bound, hold verbatim in quantum-LOCAL.

2) Using the above result, we show that there exists a locally checkable labeling problem (LCL) for which quantum-LOCAL is strictly weaker than the classical deterministic SLOCAL model. Our results extend from quantum-LOCAL to finitely dependent and non-signaling distributions, and one of the corollaries of our work is that the non-signaling model and the SLOCAL model are incomparable in the context of LCL problems: By prior work, there exists an LCL problem for which SLOCAL is strictly weaker than the non-signaling model, and our work provides a separation in the opposite direction.

This is a joint work with Alkida Balliu, Corinna Coupette, Antonio Cruciani, Francesco d'Amore, Massimo Equi, Henrik Lievonen, Augusto Modanese, Dennis Olivetti, Jukka Suomela, and it has been published at DISC 2025.

In this talk, we will discuss $(\Delta - k)$-coloring algorithms in LOCAL with $\operatorname{poly}(\log\log n)$ round complexity, for all $k$ up to $\approx \sqrt{\Delta}$. The round complexity is nearly-optimal given the $\Omega( \log \log n )$ lower bound for $\Delta$-coloring. This is also best possible in terms of number of colors, in the sense that past the $k \approx \sqrt{\Delta}$ threshold, the $(\Delta-k)$-coloring problem becomes global.

Based on joint work with Magnus Halldórsson, Manuel Jakob, and Yannic Maus.

Based on joint work with Martin R. Albrecht and Eamonn W. Postlethwaite.

We obtain Steiner $(1+\epsilon)$-spanners of size $O_d(\epsilon^{(1-d)/2} \log(1/\epsilon) n)$ not only in d-dimensional Euclidean space, but also in d-dimensional spherical and hyperbolic space. For any fixed dimension d, the obtained edge count is optimal up to an $O(\log(1/\epsilon))$ factor in each of these spaces. Unlike earlier constructions, our Steiner spanners are based on simple quadtrees, and they can be dynamically maintained, leading to efficient data structures for dynamic approximate nearest neighbours and bichromatic closest pair.

In the hyperbolic setting, we also show that 2-spanners in the hyperbolic plane must have $\Omega(n\log n)$ edges, and we obtain a 2-spanner of size $O_d(n\log n)$ in d-dimensional hyperbolic space, matching our lower bound for any constant d. Finally, we give a Steiner spanner with additive error $\epsilon$ in hyperbolic space with $O_d(\epsilon^{(1-d)/2} \log(\alpha(n)/\epsilon) n)$ edges, where $\alpha(n)$ is the inverse Ackermann function.

Our techniques generalize to closed orientable surfaces of constant curvature as well as to some quotient spaces.

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

As a consequence, we obtain the same lower bounds for sinkless orientation and the distributed LLL also in a variety of other models studied across different research communities. Moreover, to obtain our results, we develop an entirely new lower bound technique for proving post-quantum lower bounds, with the potential to generalize to other important problems in the context of locality.

Joint work with Lasse Leskelä.

Joint work with Nils Froleyks, Emily Yu, Mathias Preiner, and Armin Biere.

This is joint work with Tuomo Lehtonen.

Based on joint work with Magnús M. Halldórsson.

This is a joint work with Prosenjit Bose, Vida Dujmović, Hussein Houdrouge, and Pat Morin.

We explore several real-world contexts where the data is, in fact, external to the network and accessible to all nodes through queries and API calls -- often at a cost that must be optimized. Inspired by these contexts, we will present a recent Byzantine resilient distributed computing model on external data. We will then focus on the download problem that requires all good nodes in the network to optimally learn all the external data (represented as an array of $n$ bits that can be individually queried) through careful collaboration despite $\beta$ fraction (out of the $k$ nodes) being Byzantine. The download problem is fundamental because all other conceivable problems can be solved locally after the download.

It is easy to see that $n/k$ is a lower bound for the average number of queries per node even when the fraction of Byzantine nodes $\beta$ is 0. Somewhat surprisingly, we will see that the download problem can be solved in the synchronous setting with at most a $\text{polylog}(n)$ factor overhead for any fixed $\beta < 1$. We will end with some discussion on what might be interesting directions that can be explored further.

Acknowledgement: This is based on joint works with Jeffin Biju, Soumyottam Chatterjee, Valerie King, Manish Kumar, Shachar Meir, David Peleg, Srikkanth Ramachandran, and Aishwarya Thiruvengadam.

Bio. Bo Zhao is a tenure-track assistant professor in the Department of Computer Science at Aalto University, leading the Aalto Data-Intensive System group. He is also affiliated with the Finnish Center for Artificial Intelligence and Helsinki Institute for Information Technology. Bo’s research focuses on efficient machine learning systems at the intersection of scalable reinforcement learning systems and distributed data management systems, as well as compilation-based optimization techniques. He has published in top venues in the field (e.g., SOSP, USENIX ATC, EuroSys, SIGMOD, VLDB) and served in programme committees (e.g., EuroSys, SIGMOD, VLDB, ICDE) and reviewers of journals (e.g., JMLR, TPDS, VLDBJ, IEEE Transactions on Computers).

Known algorithms rely heavily on dynamic programming, which leads to a space complexity of similar order of magnitude as the running time. In this paper, we present a polynomial space algorithm that solves integer linear programs in $(m\Delta)^{O(m (\log m + \log\log\Delta))} \text{poly}(I)$ time, that is, in almost the same time as previous dynamic programming algorithms.

This is joint work with Lars Rohwedder.

A major breakthrough came with the works of Umans and Kedlaya–Umans (2008), who developed near-linear time algorithms over small characteristic fields and over all finite fields respectively, provided the number of variables $n$ is at most $d^{o(1)}$, where $d$ is the individual degree of the given polynomial.

In this work, we show that there is a deterministic algorithm for multivariate multipoint evaluation over a finite field that runs in near-linear time in the input parameters under some mild field restrictions but without any limitation on the number of variables.

This talk is based on a joint work with Vishwas Bhargava, Sumanta Ghosh and Mrinal Kumar.

An LCP is correct if it satisfies completeness and soundness. Completeness means that, for any graph $G$ satisfying a property $Π$, there exists a certificate assignment accepted by all nodes. Soundness ensures that for every graph not satisfying $Π$, at least one node rejects any certificate assignment. We study how to certify that a graph is bipartite (i.e., $2$-colorable) with an LCP that hides the $2$-coloring from the verifier. An LCP is hiding if no local algorithm can reconstruct the coloring from a valid certificate. Motivated by promise-free separations in the LOCAL model and its variants, we also require strong soundness: in a no-instance, the subgraph induced by accepting nodes must be $2$-colorable. An LCP with completeness, soundness, hiding, and strong soundness is called strong and hiding.

We show that such LCPs for $2$-coloring exist in specific graph classes, using only $O(\log n)$-size certificates. If the input is a cycle or has a node of degree 1, these LCPs also work in anonymous networks with constant-size certificates.

We also prove that no strong and hiding LCP exists for general graphs unless node identifiers are available and certificates are of size $ω(1)$. In anonymous networks, this lower bound holds regardless of the certificate size. We also present a characterization of the hiding property for $k$-coloring, which plays a key role in future investigations.

This is joint work with Pedro Montealegre and Martín Ríos-Wilson.

[{[]}[]][][{[{}{}]}]{[{{}}]}{{}{}}.

If the string starts with [ and ends with }, then it must contain ]{ as a substring. I discuss the complexity of finding this substring and explain how this "Bracket Game" has allowed recent progress in proof and circuit complexity. Many questions remain open, such as how to classify the Bracket Game in the theory of total NP search problems (TFNP).

Joint work with Gilbert Maystre, Kilian Risse, and Dmitry Sokolov.

We improve on the prior work in two dimensions: First, we show that we can solve the same task faster, in only $O(d^{1.832})$ rounds. Second, we explore what happens when matrices are not uniformly sparse. We consider the following alternative notions of sparsity: row-sparse matrices (at most $d$ non-zeros per row), column-sparse matrices, matrices with bounded degeneracy (we can recursively delete a row or column with at most $d$ non-zeros), average-sparse matrices (at most $dn$ non-zeros in total), and general matrices.

We present a near-complete classification of the complexity of matrix multiplication for all combinations of these notions of sparsity. We show that almost all cases fall in one of these classes:

• We have an upper bound of $O(d^{1.832})$ rounds for computing $X = AB$. An example is the case where $X$ and $A$ are uniformly sparse but $B$ is average-sparse; this is a generalization of the prior work beyond the uniformly-sparse case.
• We have lower bounds $\Omega(d)$ and $\Omega(\log n)$ and an upper bound of $O(d^2 + \log n)$ rounds for computing $X = AB$. An example is the case where $X$, $A$, and $B$ have bounded degeneracy.
• We have a lower bound of $n^{\Omega(1)}$ rounds for computing $X = AB$. An example is the case where $X$ and $A$ have bounded degeneracy but $B$ is a general matrix.
• We have a conditional lower bound: a fast algorithm for computing $X = AB$ would imply major improvements in dense matrix multiplication. An example is the case where $X$, $A$, and $B$ are average-sparse matrices.

In this talk, we explore the concept of safety in De Bruijn graphs and present flowtigs, a characterisation of safety for graphs with flow. The addition of network flow permits us to get longer safe walks than in models that do not utilise it. Flowtigs is complete in our model, i.e., a walk is safe if and only if it is a flowtig.

This talk will be divided into two parts: first, a general theory of exact real arithmetic and computability of real numbers will be presented, discussing the most common approaches and implementations of exact real arithmetic. In the second part, DedekindCutArithmetic.jl, a Julia library for exact real arithmetic will be introduced. The presentation will cover the library's embedded domain-specific language (DSL) to represent real numbers at arbitrary precision, its type system, and the design choices made to balance expressiveness and performance.

We present a problem that we call iterated GHZ, which is defined using only local constraints. Formally, it is a family of locally checkable labeling problems [Naor and Stockmeyer 1995]; in particular, solutions can be verified with a constant-round distributed algorithm.

We show that in graphs of maximum degree Δ, any classical (deterministic or randomized) LOCAL model algorithm will require Ω(Δ) rounds to solve the iterated GHZ problem, while the problem can be solved in 1 round in quantum-LOCAL.

We use the round elimination technique to prove that the iterated GHZ problem requires Ω(Δ) rounds for classical algorithms. This is the first work that shows that round elimination is indeed able to separate the two models, and this also demonstrates that round elimination cannot be used to prove lower bounds for quantum-LOCAL. To apply round elimination, we introduce a new technique that allows us to discover appropriate problem relaxations in a mechanical way; it turns out that this new technique extends beyond the scope of the iterated GHZ problem and can be used to e.g. reproduce prior results on maximal matchings [FOCS 2019, PODC 2020] in a systematic manner.

Our research seeks to explore novel methods for generating complex Hadamard matrices, classifying them up to equivalence, and investigating their algebraic and geometric properties. In this work, we examine the basic properties of complex Hadamard matrices and their structure in different orders. We present an algorithm to recognise the equivalence of two complex Hadamard matrices and methods for constructing new ones. These techniques have already led to the discovery of multiple new families of 8×8 complex Hadamard matrices.

To remedy this,we translated and integrated the PTX and Vulkan models into the Dartagnan verification tool. This makes Dartagnan the first analysis tool for multiple GPU consistency models that can analyze real GPU code. During the validation of the translated models, we discovered two bugs in the original PTX and Vulkan consistency models.

This is joint work with Haining Tong, Hernán Ponce de León, and Natalia Gavrilenko.

Inspired by recent works on cryptography based on the lattice isomorphism problem, we propose an alternative way to update keys in lattice-based UPKE. Instead of shifting, we rotate them. As rotations do not induce norm growth, our construction supports an unbounded number of updates with a polynomial-size modulus. The security of our scheme is based on the LWE assumption over hollow matrices -- matrices which generate linear codes with non-trivial hull -- and the hardness of permutation code equivalence. Along the way, we also show that LWE over hollow matrices is as hard as LWE over uniform matrices, and that a leftover hash lemma holds for hollow matrices.

Based on joint work with Johannes P. Wallner, Matti Järvisalo and Daphne Odekerken.

Our approach is based on an unconventional view, where the time integration is performed as a chain of data tensor transformations resembling the forward pass of a convolutional neural network. We also highlight automated tuning and domain-specific languages as ways to achieve competitive performance with relatively little programming effort.

This is joint work with Massimo Equi, Paweł Gawrychowski, Veli Mäkinen, Jakub Radoszewski and Alexandru I. Tomescu.

Given a property P, a streaming certification scheme for P is a prover-verifier pair where the prover is a computationally unlimited but non-trustable oracle, and the verifier is a streaming algorithm. For any input, the prover provides the verifier with a certificate. The verifier then receives its input as a stream in an adversarial order and must check whether the certificate is indeed a proof that the input satisfies P. The main complexity measure for a streaming certification scheme is the sum of the size of the certificate provided by the oracle, and of the memory space required by the verifier. The problems typically considered in this model are ``hard'' in the classical semi-streaming setting. We will discuss a few upper and lower bounds for some graph problems in this model and also explore how some ideas and gadgets from distributed certification and CONGEST transfer to the setting of streaming certification.

This is joint work with Petteri Kaski and Heikki Mannila.

Based on joint work with Fedor Fomin and Tuukka Korhonen.

Faster Min-Plus Product for Monotone Instances and Applications

Min-plus product is a basic problem in theoretical computer science, and has many applications. For example, the min-plus product of two n × n matrices has essentially the same time complexity of the All Pair Shortest Path problem (APSP) in an n-node graph. The straightforward algorithm for the min-plus product on two n × n matrices runs in cubic time, and there is a major opening problem that whether there exists truly sub-cubic algorithm for min-plus product. However, if we know more structures of the matrices, truly sub-cubic algorithms are known. In this talk, we introduce a fast min-plus product algorithm for two n × n monotone matrices. That is, when A is an arbitrary integer matrix and B is either row-monotone or column-monotone with integer elements bounded by O(n), the min-plus product of A and B can be computed in time O˜(n^{(3+ω)/2}) = O˜(n^{2.687}), where ω < 2.3714 is the fast matrix multiplication exponent. Then by simple reductions, there are also O˜(n^{(3+ω)/2}) time algorithm for bounded-difference min-plus product. We also consider the problem of min-plus convolution between two integral sequences which are monotone and bounded by O(n), and achieve a running time upper bound of O˜(n^{1.5}). Furthermore, we also show how to apply these fast structured min-plus product algorithms on important problems in computer science, including the Knapsack problem and Language edit distance.

Shucheng Chi is currently a PhD student in Tsinghua, Institute for Interdisciplinary Information Sciences. His advisor is Andrew Chi-Chih Yao. He received his Bachelor's degree from Tsinghua, Yaoclass in 2021. His research focuses on data structures, approximate and randomized algorithms, and graph algorithms. The Yao Class at Tsinghua was founded by Andrew Chi-Chih Yao, the recipient of the 2000 Turing Award and a member of the Chinese Academy of Sciences. This program aims to nurture top-tier talent in Computer Science, Artificial Intelligence, and Quantum Computation. Many students in the Yao Class are medalists in International Mathematical, Physics, and Informatics Olympiads or are among the top-ranking freshmen at Tsinghua University.

This model was originally studied by Feuilloley et al. (2021), who considered certificates of size \(\mathcal{O}(\log n)\). Although many natural problems, such as spanning trees, leader election, and optimization problems (such as the maximum independent set), were captured by this model, the question of whether there exists a strict separation between the levels, or whether explicit problems exist outside the hierarchy, remains open.

Inspired by this work, we study the more restricted case in which the size of the certificates is constant. Surprisingly, we have found that this model is powerful enough to capture the leader election problem at the fourth level of the hierarchy. Furthermore, we show that, similarly to the case of the logarithmic hierarchy, any graph property expressible in monadic second-order logic (MSO) lies in some level of the hierarchy. Additionally, we show that there is a strict separation between the levels of the hierarchy, as a consequence of a separation result in the MSO quantifier alternation hierarchy restricted to bounded-degree graphs.

This is joint work with Pedro Montealegre and Guillaume Theyssier.

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.

Joint work with Arnaud Durand and Juha Kontinen.

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.