Andreas Björklund

activity

20062026

most citedThe fast intersection transform with applications to counting paths

14 citations · 32 across the 19 of their papers we have counts for

collaborators

Showing cs.DSShow all

26 papers · 1 filter

cs.DS2026

The Arithmetic Circuit Combinatorial Nullstellensatz is NP-hard

Andreas Björklund

A multivariate polynomial on $n$ variables $x_{1}, \dots, x_{n}$ of total degree $n$ over $Z_{2}$ containing the multilinear monomial $\prod_{i = 1}^{n} x_{i}$ is by the combinatorial…

cs.DS2025

Kronecker scaling of tensors with applications to arithmetic circuits and algorithms

Andreas Björklund, Petteri Kaski, Tomohiro Koana +1

We show that sufficiently low tensor rank for the balanced tripartitioning tensor $P_{d} (x, y, z) = \sum_{A, B, C \in (d [ 3 d ]) : A \cup B \cup C = [3 d]} x_{A} y_{B} z_{C}$ for a large enough constan…

cs.DS2024

Finding longer cycles via shortest colourful cycle

Andreas Björklund, Thore Husfeldt

We consider the parameterised $k, e$ -Long Cycle problem, in which you are given an $n$ -vertex undirected graph $G$ , a specified edge $e$ in $G$ , and a positive integer $k$ , and are…

cs.DS2024★ 1 cited

Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture

Andreas Björklund, Radu Curticapean, Thore Husfeldt +2

In this paper we further explore the recently discovered connection by Björklund and Kaski [STOC 2024] and Pratt [STOC 2024] between the asymptotic rank conjecture of Strassen [Pro…

cs.DS2023

Another Hamiltonian Cycle in Bipartite Pfaffian Graphs

Andreas Björklund, Petteri Kaski, Jesper Nederlof

Finding a Hamiltonian cycle in a given graph is computationally challenging, and in general remains so even when one is further given one Hamiltonian cycle in the graph and asked t…

cs.DS2021★ 1 cited

The Shortest Even Cycle Problem is Tractable

Andreas Björklund, Thore Husfeldt, Petteri Kaski

Given a directed graph, we show how to efficiently find a shortest (directed, simple) cycle on an even number of vertices. As far as we know, no polynomial-time algorithm was previ…

cs.DS2020

An Asymptotically Fast Polynomial Space Algorithm for Hamiltonicity Detection in Sparse Directed Graphs

Andreas Björklund

We present a polynomial space Monte Carlo algorithm that given a directed graph on $n$ vertices and average outdegree $δ$ , detects if the graph has a Hamiltonian cycle in $2^{n-Ω(\…

cs.DS2020

Counting Short Vector Pairs by Inner Product and Relations to the Permanent

Andreas Björklund, Petteri Kaski

Given as input two $n$ -element sets $A, B \subseteq {0, 1}^{d}$ with $d = c lo g n \leq (lo g n)^{2} / (lo g lo g n)^{4}$ and a target $t \in {0, 1, \dots, d}$ , we show how to cou…

cs.DS2018★ 1 cited

Counting Shortest Two Disjoint Paths in Cubic Planar Graphs with an NC Algorithm

Andreas Björklund, Thore Husfeldt

Given an undirected graph and two disjoint vertex pairs $s_{1}, t_{1}$ and $s_{2}, t_{2}$ , the Shortest two disjoint paths problem (S2DP) asks for the minimum total length of two vertex disj…

cs.DS2018

A faster hafnian formula for complex matrices and its benchmarking on a supercomputer

Andreas Björklund, Brajesh Gupt, Nicolás Quesada

We introduce new and simple algorithms for the calculation of the number of perfect matchings of complex weighted, undirected graphs with and without loops. Our compact formulas fo…

cs.DS2016★ 2 cited

Directed Hamiltonicity and Out-Branchings via Generalized Laplacians

Andreas Björklund, Petteri Kaski, Ioannis Koutis

We are motivated by a tantalizing open question in exact algorithms: can we detect whether an $n$ -vertex directed graph $G$ has a Hamiltonian cycle in time significantly less than…

cs.DS2016★ 1 cited

How proofs are prepared at Camelot

Andreas Björklund, Petteri Kaski

We study a design framework for robust, independently verifiable, and workload-balanced distributed algorithms working on a common input. An algorithm based on the framework is ess…

cs.DS2015

Fast Witness Extraction Using a Decision Oracle

Andreas Björklund, Petteri Kaski, Łukasz Kowalik

The gist of many (NP-)hard combinatorial problems is to decide whether a universe of $n$ elements contains a witness consisting of $k$ elements that match some prescribed pattern.…

cs.DS2015

Coloring Graphs having Few Colorings over Path Decompositions

Andreas Björklund

Lokshtanov, Marx, and Saurabh SODA 2011 proved that there is no $(k - ε)^{pw (G)} poly (n)$ time algorithm for deciding if an $n$ -vertex graph $G$ with pat…

cs.DS2015

Spotting Trees with Few Leaves

Andreas Björklund, Vikram Kamat, Łukasz Kowalik +1

We show two results related to the Hamiltonicity and $k$ -Path algorithms in undirected graphs by Björklund [FOCS'10], and Björklund et al., [arXiv'10]. First, we demonstrate that t…

cs.DS2013

Counting thin subgraphs via packings faster than meet-in-the-middle time

Andreas Björklund, Petteri Kaski, Łukasz Kowalik

Vassilevska and Williams (STOC 2009) showed how to count simple paths on $k$ vertices and matchings on $k /2$ edges in an $n$ -vertex graph in time $n^{k /2 + O (1)}$ . In the same year,…

cs.DS2012

Below All Subsets for Some Permutational Counting Problems

Andreas Björklund

We show that the two problems of computing the permanent of an $n \times n$ matrix of $poly (n)$ -bit integers and counting the number of Hamiltonian cycles in a direct…

cs.DS2012★ 1 cited

Constrained Multilinear Detection and Generalized Graph Motifs

Andreas Bjorklund, Petteri Kaski, Lukasz Kowalik

We introduce a new algebraic sieving technique to detect constrained multilinear monomials in multivariate polynomial generating functions given by an evaluation oracle. As applica…

cs.DS2011

Counting Perfect Matchings as Fast as Ryser

Andreas Björklund

We show that there is a polynomial space algorithm that counts the number of perfect matchings in an $n$ -vertex graph in $O^{*} (2^{n /2}) \subset O (1.41 5^{n})$ time. ( $O^{*} (f (n))$ suppres…

cs.DS2010