14 citations · 32 across the 19 of their papers we have counts for
27 papers
The Arithmetic Circuit Combinatorial Nullstellensatz is NP-hard
Andreas Björklund
A multivariate polynomial on variables of total degree over containing the multilinear monomial is by the combinatorial…
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 for a large enough constan…
Finding longer cycles via shortest colourful cycle
Andreas Björklund, Thore Husfeldt
We consider the parameterised -Long Cycle problem, in which you are given an -vertex undirected graph , a specified edge in , and a positive integer , and are…
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…
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…
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…