Andreas Björklund

Proceedings of the 2025 Symposium on Simplicity in Algorithms, 2025

Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture.

[BibT_eX]

[DOI]

Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 2025

2024

Chromatic number in 1.9999<sup>n</sup> time? Fast deterministic set partitioning under the asymptotic rank conjecture.

[BibT_eX]

[DOI]

CoRR, 2024

The Asymptotic Rank Conjecture and the Set Cover Conjecture Are Not Both True.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Another Hamiltonian Cycle in Bipartite Pfaffian Graphs.

[BibT_eX]

[DOI]

Jesper Nederlof

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

2022

The shortest even cycle problem is tractable.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

2021

Approximate Counting of <i>k</i>-Paths: Simpler, Deterministic, and in Polynomial Space.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2021

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

[BibT_eX]

[DOI]

Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021

The Fine-Grained Complexity of Computing the Tutte Polynomial of a Linear Matroid.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

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

[BibT_eX]

[DOI]

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2019

Shortest Two Disjoint Paths in Polynomial Time.

[BibT_eX]

[DOI]

SIAM J. Comput., 2019

A Faster Hafnian Formula for Complex Matrices and Its Benchmarking on a Supercomputer.

[BibT_eX]

[DOI]

Brajesh Gupt

Nicolás Quesada

ACM J. Exp. Algorithmics, 2019

Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants.

[BibT_eX]

[DOI]

Ryan Williams

Algorithmica, 2019

Approximate Counting of k-Paths: Deterministic and in Polynomial Space.

[BibT_eX]

[DOI]

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Solving Systems of Polynomial Equations over GF(2) by a Parity-Counting Self-Reduction.

[BibT_eX]

[DOI]

Ryan Williams

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Computing Permanents and Counting Hamiltonian Cycles by Listing Dissimilar Vectors.

[BibT_eX]

[DOI]

Ryan Williams

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018

A faster hafnian formula for complex matrices and its benchmarking on the Titan supercomputer.

[BibT_eX]

[DOI]

Brajesh Gupt

Nicolás Quesada

CoRR, 2018

Counting Connected Subgraphs with Maximum-Degree-Aware Sieving.

[BibT_eX]

[DOI]

Proceedings of the 29th International Symposium on Algorithms and Computation, 2018

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

[BibT_eX]

[DOI]

Proceedings of the 29th International Symposium on Algorithms and Computation, 2018

Exploiting Sparsity for Bipartite Hamiltonicity.

[BibT_eX]

[DOI]

Proceedings of the 29th International Symposium on Algorithms and Computation, 2018

2017

Counting Thin Subgraphs via Packings Faster than Meet-in-the-Middle Time.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2017

Spotting Trees with Few Leaves.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2017

Narrow sieves for parameterized paths and packings.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2017

Computing the permanent modulo a prime power.

[BibT_eX]

[DOI]

Isak Lyckberg

Inf. Process. Lett., 2017

Directed Hamiltonicity and Out-Branchings via Generalized Laplacians.

[BibT_eX]

[DOI]

Ioannis Koutis

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

Exact Graph Coloring Using Inclusion-Exclusion.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Fast Zeta Transforms for Lattices with Few Irreducibles.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

Modular Sieves for Directed Hamiltonian Cycles.

[BibT_eX]

[DOI]

Ioannis Koutis

CoRR, 2016

How proofs are prepared at Camelot.

[BibT_eX]

[DOI]

CoRR, 2016

Constrained Multilinear Detection and Generalized Graph Motifs.

[BibT_eX]

[DOI]

Algorithmica, 2016

Below All Subsets for Some Permutational Counting Problems .

[BibT_eX]

[DOI]

Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016

Coloring Graphs Having Few Colorings Over Path Decompositions.

[BibT_eX]

[DOI]

Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016

How Proofs are Prepared at Camelot: Extended Abstract.

[BibT_eX]

[DOI]

Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

Determinant Sums for Hamiltonicity (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 11th International Symposium on Parameterized and Exact Computation, 2016

2015

Uniquely Coloring Graphs over Path Decompositions.

[BibT_eX]

[DOI]

CoRR, 2015

The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems.

[BibT_eX]

[DOI]

Holger Dell

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Engineering Motif Search for Large Graphs.

[BibT_eX]

[DOI]

Proceedings of the Seventeenth Workshop on Algorithm Engineering and Experiments, 2015

2014

Determinant Sums for Undirected Hamiltonicity.

[BibT_eX]

[DOI]

SIAM J. Comput., 2014

Listing Triangles.

[BibT_eX]

[DOI]

Virginia Vassilevska Williams

Rasmus Pagh

Uri Zwick

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Fast Witness Extraction Using a Decision Oracle.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2014, 2014

2013

Counting closed trails.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2013

Probably Optimal Graph Motifs.

[BibT_eX]

[DOI]

Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

The Parity of Directed Hamiltonian Cycles.

[BibT_eX]

[DOI]

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012

The traveling salesman problem in bounded degree graphs.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2012

Below All Subsets for Permutational Counting Problems

[BibT_eX]

[DOI]

CoRR, 2012

Shortest cycle through specified elements.

[BibT_eX]

[DOI]

Nina Taslaman

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Counting perfect matchings as fast as Ryser.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

The Path Taken for k-Path.

[BibT_eX]

[DOI]

Proceedings of the Parameterized and Exact Computation - 7th International Symposium, 2012

2011

Covering and packing in linear space.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2011

2010

Trimmed Moebius Inversion and Graphs of Bounded Degree.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2010

Evaluation of permanents in rings and semirings.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2010

Exact Covers via Determinants.

[BibT_eX]

[DOI]

Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

2009

Set Partitioning via Inclusion-Exclusion.

[BibT_eX]

[DOI]

Mikko Koivisto

SIAM J. Comput., 2009

On evaluation of permanents

[BibT_eX]

[DOI]

CoRR, 2009

Counting Paths and Packings in Halves.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2009

2008

Exact Graph Coloring Using Inclusion-Exclusion.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

The fast intersection transform with applications to counting paths

[BibT_eX]

[DOI]

CoRR, 2008

Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings.

[BibT_eX]

[DOI]

Algorithmica, 2008

The Travelling Salesman Problem in Bounded Degree Graphs.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Computing the Tutte Polynomial in Vertex-Exponential Time.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

Algorithmic Bounds for Presumably Hard Combinatorial Problems.

[BibT_eX]

[DOI]

PhD thesis, 2007

Fourier meets möbius: fast subset convolution.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

2006

Inclusion-Exclusion Based Algorithms for Graph Colouring.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Inclusion--Exclusion Algorithms for Counting Set Partitions.

[BibT_eX]

[DOI]

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2005

Approximating Integer Quadratic Programs and MAXCUT in Subdense Graphs.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2005

2004

Approximating Longest Directed Paths and Cycles.

[BibT_eX]

[DOI]

Sanjeev Khanna

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

2003

Finding a Path of Superlogarithmic Length.

[BibT_eX]

[DOI]

SIAM J. Comput., 2003

Approximating Longest Directed Path

[BibT_eX]

[DOI]

Sanjeev Khanna

Electron. Colloquium Comput. Complex., 2003

2001

Fast Boolean Matrix Multiplication for Highly Clustered Data.

[BibT_eX]

[DOI]

Andrzej Lingas

Proceedings of the Algorithms and Data Structures, 7th International Workshop, 2001

2000

Optimal Adaptive Fault Diagnosis of Hypercubes.

[BibT_eX]

[DOI]