Extensor-Coding

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

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 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.

Detaljer

Författare
Enheter & grupper
Externa organisationer
  • Saarland University
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Diskret matematik

Nyckelord

Originalspråkengelska
Titel på värdpublikationSTOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
FörlagAssociation for Computing Machinery (ACM)
Sidor535-544
Antal sidor10
ISBN (elektroniskt)9781450355599
StatusPublished - 2018
PublikationskategoriForskning
Peer review utfördJa
Evenemang50th Annual ACM Symposium on Theory of Computing, STOC 2018 - Los Angeles, USA
Varaktighet: 2018 jun 252018 jun 29

Konferens

Konferens50th Annual ACM Symposium on Theory of Computing, STOC 2018
LandUSA
OrtLos Angeles
Period2018/06/252018/06/29