Andreas Björklund

102 papers A* 22A 8B 7Journal 51Unranked 11

Year	Rank	Type	Title / Venue / Authors
2025	A*	`conf`	Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture. SODA Andreas Björklund, Radu Curticapean, Thore Husfeldt, Petteri Kaski, Kevin Pratt
2025	—	`conf`	Finding longer cycles via shortest colourful cycle. SOSA Andreas Björklund, Thore Husfeldt
2025	J	`jnl`	Kronecker scaling of tensors with applications to arithmetic circuits and algorithms. CoRR Andreas Björklund, Petteri Kaski, Tomohiro Koana, Jesper Nederlof
2024	A*	`conf`	Another Hamiltonian Cycle in Bipartite Pfaffian Graphs. ICALP Andreas Björklund, Petteri Kaski, Jesper Nederlof
2024	J	`jnl`	Chromatic number in 1.9999 CoRR Andreas Björklund, Radu Curticapean, Thore Husfeldt, Petteri Kaski, Kevin Pratt
2024	J	`jnl`	Finding longer cycles via shortest colourful cycle. CoRR Andreas Björklund, Thore Husfeldt
2024	A*	`conf`	The Asymptotic Rank Conjecture and the Set Cover Conjecture Are Not Both True. STOC Andreas Björklund, Petteri Kaski
2023	J	`jnl`	Another Hamiltonian Cycle in Bipartite Pfaffian Graphs. CoRR Andreas Björklund, Petteri Kaski, Jesper Nederlof
2023	J	`jnl`	The Asymptotic Rank Conjecture and the Set Cover Conjecture are not Both True. CoRR Andreas Björklund, Petteri Kaski
2022	A*	`conf`	The shortest even cycle problem is tractable. STOC Andreas Björklund, Thore Husfeldt, Petteri Kaski
2021	A	`conf`	An Asymptotically Fast Polynomial Space Algorithm for Hamiltonicity Detection in Sparse Directed Graphs. STACS Andreas Björklund
2021	J	`jnl`	Approximate Counting of ACM Trans. Algorithms Daniel Lokshtanov, Andreas Björklund, Saket Saurabh, Meirav Zehavi
2021	A*	`conf`	Counting Short Vector Pairs by Inner Product and Relations to the Permanent. ICALP Andreas Björklund, Petteri Kaski
2021	A*	`conf`	The Fine-Grained Complexity of Computing the Tutte Polynomial of a Linear Matroid. SODA Andreas Björklund, Petteri Kaski
2021	J	`jnl`	The Shortest Even Cycle Problem is Tractable. CoRR Andreas Björklund, Thore Husfeldt, Petteri Kaski
2020	J	`jnl`	An Asymptotically Fast Polynomial Space Algorithm for Hamiltonicity Detection in Sparse Directed Graphs. CoRR Andreas Björklund
2020	J	`jnl`	Counting Short Vector Pairs by Inner Product and Relations to the Permanent. CoRR Andreas Björklund, Petteri Kaski
2020	J	`jnl`	The Fine-Grained Complexity of Computing the Tutte Polynomial of a Linear Matroid. CoRR Andreas Björklund, Petteri Kaski
2019	J	`jnl`	A Faster Hafnian Formula for Complex Matrices and Its Benchmarking on a Supercomputer. ACM J. Exp. Algorithmics Andreas Björklund, Brajesh Gupt, Nicolás Quesada
2019	A*	`conf`	Approximate Counting of k-Paths: Deterministic and in Polynomial Space. ICALP Andreas Björklund, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi
2019	A*	`conf`	Computing Permanents and Counting Hamiltonian Cycles by Listing Dissimilar Vectors. ICALP Andreas Björklund, Ryan Williams
2019	J	`jnl`	Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants. Algorithmica Andreas Björklund, Petteri Kaski, Ryan Williams
2019	J	`jnl`	Shortest Two Disjoint Paths in Polynomial Time. SIAM J. Comput. Andreas Björklund, Thore Husfeldt
2019	A*	`conf`	Solving Systems of Polynomial Equations over GF(2) by a Parity-Counting Self-Reduction. ICALP Andreas Björklund, Petteri Kaski, Ryan Williams
2018	J	`jnl`	A faster hafnian formula for complex matrices and its benchmarking on the Titan supercomputer. CoRR Andreas Björklund, Brajesh Gupt, Nicolás Quesada
2018	B	`conf`	Counting Connected Subgraphs with Maximum-Degree-Aware Sieving. ISAAC Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto
2018	B	`conf`	Counting Shortest Two Disjoint Paths in Cubic Planar Graphs with an NC Algorithm. ISAAC Andreas Björklund, Thore Husfeldt
2018	J	`jnl`	Counting Shortest Two Disjoint Paths in Cubic Planar Graphs with an NC Algorithm. CoRR Andreas Björklund, Thore Husfeldt
2018	B	`conf`	Exploiting Sparsity for Bipartite Hamiltonicity. ISAAC Andreas Björklund
2017	J	`jnl`	Computing the permanent modulo a prime power. Inf. Process. Lett. Andreas Björklund, Thore Husfeldt, Isak Lyckberg
2017	J	`jnl`	Counting Thin Subgraphs via Packings Faster than Meet-in-the-Middle Time. ACM Trans. Algorithms Andreas Björklund, Petteri Kaski, Lukasz Kowalik
2017	A*	`conf`	Directed Hamiltonicity and Out-Branchings via Generalized Laplacians. ICALP Andreas Björklund, Petteri Kaski, Ioannis Koutis
2017	B	`conf`	Generalized Kakeya Sets for Polynomial Evaluation and Faster Computation of Fermionants. IPEC Andreas Björklund, Petteri Kaski, R. Ryan Williams
2017	J	`jnl`	Narrow sieves for parameterized paths and packings. J. Comput. Syst. Sci. Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto
2017	J	`jnl`	Spotting Trees with Few Leaves. SIAM J. Discret. Math. Andreas Björklund, Vikram Kamat, Lukasz Kowalik, Meirav Zehavi
2016	—	`conf`	Below All Subsets for Some Permutational Counting Problems . SWAT Andreas Björklund
2016	—	`conf`	Coloring Graphs Having Few Colorings Over Path Decompositions. SWAT Andreas Björklund
2016	J	`jnl`	Constrained Multilinear Detection and Generalized Graph Motifs. Algorithmica Andreas Björklund, Petteri Kaski, Lukasz Kowalik
2016	B	`conf`	Determinant Sums for Hamiltonicity (Invited Talk). IPEC Andreas Björklund
2016	—	`ch.`	Exact Graph Coloring Using Inclusion-Exclusion. Encyclopedia of Algorithms Andreas Björklund, Thore Husfeldt
2016	J	`jnl`	Fast Zeta Transforms for Lattices with Few Irreducibles. ACM Trans. Algorithms Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto, Jesper Nederlof, Pekka Parviainen
2016	A*	`conf`	How Proofs are Prepared at Camelot: Extended Abstract. PODC Andreas Björklund, Petteri Kaski
2016	J	`jnl`	How proofs are prepared at Camelot. CoRR Andreas Björklund, Petteri Kaski
2016	J	`jnl`	Modular Sieves for Directed Hamiltonian Cycles. CoRR Andreas Björklund, Ioannis Koutis
2015	A	`conf`	Engineering Motif Search for Large Graphs. ALENEX Andreas Björklund, Petteri Kaski, Lukasz Kowalik, Juho Lauri
2015	J	`jnl`	Fast Witness Extraction Using a Decision Oracle. CoRR Andreas Björklund, Petteri Kaski, Lukasz Kowalik
2015	—	`conf`	Spotting Trees with Few Leaves. ICALP (1) Andreas Björklund, Vikram Kamat, Lukasz Kowalik, Meirav Zehavi
2015	J	`jnl`	Spotting Trees with Few Leaves. CoRR Andreas Björklund, Vikram Kamat, Lukasz Kowalik, Meirav Zehavi
2015	—	`conf`	The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems. ICALP (1) Andreas Björklund, Holger Dell, Thore Husfeldt
2015	J	`jnl`	Uniquely Coloring Graphs over Path Decompositions. CoRR Andreas Björklund
2014	A*	`conf`	Counting Thin Subgraphs via Packings Faster Than Meet-in-the-Middle Time. SODA Andreas Björklund, Petteri Kaski, Lukasz Kowalik
2014	J	`jnl`	Determinant Sums for Undirected Hamiltonicity. SIAM J. Comput. Andreas Björklund
2014	A	`conf`	Fast Witness Extraction Using a Decision Oracle. ESA Andreas Björklund, Petteri Kaski, Lukasz Kowalik
2014	—	`conf`	Listing Triangles. ICALP (1) Andreas Björklund, Rasmus Pagh, Virginia Vassilevska Williams, Uri Zwick
2014	—	`conf`	Shortest Two Disjoint Paths in Polynomial Time. ICALP (1) Andreas Björklund, Thore Husfeldt
2013	J	`jnl`	Counting closed trails. Inf. Process. Lett. Andreas Björklund, Petteri Kaski
2013	J	`jnl`	Counting thin subgraphs via packings faster than meet-in-the-middle time. CoRR Andreas Björklund, Petteri Kaski, Lukasz Kowalik
2013	A	`conf`	Probably Optimal Graph Motifs. STACS Andreas Björklund, Petteri Kaski, Lukasz Kowalik
2013	J	`jnl`	The Parity of Directed Hamiltonian Cycles CoRR Andreas Björklund, Thore Husfeldt
2013	A*	`conf`	The Parity of Directed Hamiltonian Cycles. FOCS Andreas Björklund, Thore Husfeldt
2012	J	`jnl`	Below All Subsets for Permutational Counting Problems CoRR Andreas Björklund
2012	A*	`conf`	Counting perfect matchings as fast as Ryser. SODA Andreas Björklund
2012	A*	`conf`	Fast zeta transforms for lattices with few irreducibles. SODA Andreas Björklund, Mikko Koivisto, Thore Husfeldt, Jesper Nederlof, Petteri Kaski, Pekka Parviainen
2012	J	`jnl`	Probably Optimal Graph Motifs CoRR Andreas Björklund, Petteri Kaski, Lukasz Kowalik
2012	A*	`conf`	Shortest cycle through specified elements. SODA Andreas Björklund, Thore Husfeldt, Nina Taslaman
2012	B	`conf`	The Path Taken for k-Path. IPEC Andreas Björklund
2012	J	`jnl`	The traveling salesman problem in bounded degree graphs. ACM Trans. Algorithms Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto
2011	J	`jnl`	Counting Perfect Matchings as Fast as Ryser CoRR Andreas Björklund
2011	J	`jnl`	Covering and packing in linear space. Inf. Process. Lett. Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto
2010	—	`conf`	Covering and Packing in Linear Space. ICALP (1) Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto
2010	J	`jnl`	Determinant Sums for Undirected Hamiltonicity CoRR Andreas Björklund
2010	A*	`conf`	Determinant Sums for Undirected Hamiltonicity. FOCS Andreas Björklund
2010	J	`jnl`	Evaluation of permanents in rings and semirings. Inf. Process. Lett. Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto
2010	A	`conf`	Exact Covers via Determinants. STACS Andreas Björklund
2010	J	`jnl`	Narrow sieves for parameterized paths and packings CoRR Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto
2010	J	`jnl`	Trimmed Moebius Inversion and Graphs of Bounded Degree. Theory Comput. Syst. Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto
2009	J	`jnl`	Counting Paths and Packings in Halves CoRR Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto
2009	A	`conf`	Counting Paths and Packings in Halves. ESA Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto
2009	J	`jnl`	Exact Covers via Determinants CoRR Andreas Björklund
2009	J	`jnl`	On evaluation of permanents CoRR Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto
2009	J	`jnl`	Set Partitioning via Inclusion-Exclusion. SIAM J. Comput. Andreas Björklund, Thore Husfeldt, Mikko Koivisto
2008	A*	`conf`	Computing the Tutte Polynomial in Vertex-Exponential Time. FOCS Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto
2008	J	`jnl`	Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings. Algorithmica Andreas Björklund, Thore Husfeldt
2008	—	`ch.`	Exact Graph Coloring Using Inclusion-Exclusion. Encyclopedia of Algorithms Andreas Björklund, Thore Husfeldt
2008	—	`conf`	The Travelling Salesman Problem in Bounded Degree Graphs. ICALP (1) Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto
2008	J	`jnl`	The fast intersection transform with applications to counting paths CoRR Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto
2008	J	`jnl`	Trimmed Moebius Inversion and Graphs of Bounded Degree CoRR Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto
2008	A	`conf`	Trimmed Moebius Inversion and Graphs of Bounded Degree. STACS Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto
2007	—	`—`	Algorithmic Bounds for Presumably Hard Combinatorial Problems. Andreas Björklund
2007	J	`jnl`	Computing the Tutte polynomial in vertex-exponential time CoRR Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto
2007	A*	`conf`	Fourier meets möbius: fast subset convolution. STOC Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto
2006	—	`conf`	Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings. ICALP (1) Andreas Björklund, Thore Husfeldt
2006	J	`jnl`	Fourier meets Möbius: fast subset convolution CoRR Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto
2006	A*	`conf`	Inclusion--Exclusion Algorithms for Counting Set Partitions. FOCS Andreas Björklund, Thore Husfeldt
2006	J	`jnl`	Inclusion-Exclusion Based Algorithms for Graph Colouring. Electron. Colloquium Comput. Complex. Andreas Björklund, Thore Husfeldt
2005	A	`conf`	Approximating Integer Quadratic Programs and MAXCUT in Subdense Graphs. ESA Andreas Björklund
2004	A*	`conf`	Approximating Longest Directed Paths and Cycles. ICALP Andreas Björklund, Thore Husfeldt, Sanjeev Khanna
2003	J	`jnl`	Approximating Longest Directed Path Electron. Colloquium Comput. Complex. Andreas Björklund, Thore Husfeldt, Sanjeev Khanna
2003	J	`jnl`	Finding a Path of Superlogarithmic Length. SIAM J. Comput. Andreas Björklund, Thore Husfeldt
2002	A*	`conf`	Finding a Path of Superlogarithmic Length. ICALP Andreas Björklund, Thore Husfeldt
2001	B	`conf`	Fast Boolean Matrix Multiplication for Highly Clustered Data. WADS Andreas Björklund, Andrzej Lingas
2000	—	`conf`	Optimal Adaptive Fault Diagnosis of Hypercubes. SWAT Andreas Björklund