Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Extensor-Coding

Brand, Cornelius ; Dell, Holger and Husfeldt, Thore LU (2018) 50th Annual ACM Symposium on Theory of Computing, STOC 2018 p.535-544
Abstract

We devise an algorithm that approximately computes the number of paths of length k in a given directed graph with n vertices up to a multiplicative error of 1 ± . Our algorithm runs in time −24k(n + m) poly(k). The algorithm is based on associating with each vertex an element in the exterior (or, Grassmann) algebra, called an extensor, and then performing computations in this algebra. This connection to exterior algebra generalizes a number of previous approaches for the longest path problem and is of independent conceptual interest. Using this approach, we also obtain a deterministic 2k · poly(n) time algorithm to find a k-path in a given directed graph that is promised to have few of them. Our results... (More)

We devise an algorithm that approximately computes the number of paths of length k in a given directed graph with n vertices up to a multiplicative error of 1 ± . Our algorithm runs in time −24k(n + m) poly(k). The algorithm is based on associating with each vertex an element in the exterior (or, Grassmann) algebra, called an extensor, and then performing computations in this algebra. This connection to exterior algebra generalizes a number of previous approaches for the longest path problem and is of independent conceptual interest. Using this approach, we also obtain a deterministic 2k · poly(n) time algorithm to find a k-path in a given directed graph that is promised to have few of them. Our results and techniques generalize to the subgraph isomorphism problem when the subgraphs we are looking for have bounded pathwidth. Finally, we also obtain a randomized algorithm to detect k-multilinear terms in a multivariate polynomial given as a general algebraic circuit. To the best of our knowledge, this was previously only known for algebraic circuits not involving negative constants.

(Less)
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
Approximate counting, Exterior algebra, K-path
host publication
STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
pages
10 pages
publisher
Association for Computing Machinery (ACM)
conference name
50th Annual ACM Symposium on Theory of Computing, STOC 2018
conference location
Los Angeles, United States
conference dates
2018-06-25 - 2018-06-29
external identifiers
  • scopus:85049880689
ISBN
9781450355599
DOI
10.1145/3188745.3188902
language
English
LU publication?
yes
id
36a0072b-d937-4de0-b92b-b7be7bb7ebb1
date added to LUP
2018-08-02 13:31:07
date last changed
2022-04-17 21:36:57
@inproceedings{36a0072b-d937-4de0-b92b-b7be7bb7ebb1,
  abstract     = {{<p>We devise an algorithm that approximately computes the number of paths of length k in a given directed graph with n vertices up to a multiplicative error of 1 ± . Our algorithm runs in time −<sup>2</sup>4<sup>k</sup>(n + m) poly(k). The algorithm is based on associating with each vertex an element in the exterior (or, Grassmann) algebra, called an extensor, and then performing computations in this algebra. This connection to exterior algebra generalizes a number of previous approaches for the longest path problem and is of independent conceptual interest. Using this approach, we also obtain a deterministic 2<sup>k</sup> · poly(n) time algorithm to find a k-path in a given directed graph that is promised to have few of them. Our results and techniques generalize to the subgraph isomorphism problem when the subgraphs we are looking for have bounded pathwidth. Finally, we also obtain a randomized algorithm to detect k-multilinear terms in a multivariate polynomial given as a general algebraic circuit. To the best of our knowledge, this was previously only known for algebraic circuits not involving negative constants.</p>}},
  author       = {{Brand, Cornelius and Dell, Holger and Husfeldt, Thore}},
  booktitle    = {{STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing}},
  isbn         = {{9781450355599}},
  keywords     = {{Approximate counting; Exterior algebra; K-path}},
  language     = {{eng}},
  pages        = {{535--544}},
  publisher    = {{Association for Computing Machinery (ACM)}},
  title        = {{Extensor-Coding}},
  url          = {{http://dx.doi.org/10.1145/3188745.3188902}},
  doi          = {{10.1145/3188745.3188902}},
  year         = {{2018}},
}