research
∙
08/03/2023
Another Hamiltonian Cycle in Bipartite Pfaffian Graphs
We present a linear-time algorithm that, given as input (i) a bipartite ...
share
research
∙
11/04/2021
The Shortest Even Cycle Problem is Tractable
Given a directed graph, we show how to efficiently find a shortest (dire...
research
∙
07/28/2020
Counting Short Vector Pairs by Inner Product and Relations to the Permanent
Given as input two n-element sets 𝒜,ℬ⊆{0,1}^d with d=clog n≤(log n)^2/(l...
research
∙
03/07/2020
The Fine-Grained Complexity of Computing the Tutte Polynomial of a Linear Matroid
We show that computing the Tutte polynomial of a linear matroid of dimen...
research
∙
09/04/2019
Engineering Boolean Matrix Multiplication for Multiple-Accelerator Shared-Memory Architectures
We study the problem of multiplying two bit matrices with entries either...
research
∙
12/27/2017
Tensor network complexity of multilinear maps
We study tensor networks as a model of arithmetic computation for evalua...
research
∙
06/26/2017