Andreas Björklund

activity

20242026

collaborators

3 papers

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

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 [Pr…