A theory of even functionals and their algorithmic applications

Jerzy W. Jaromczyk, Grzegorz Świa̧tek

Research output: Contribution to journalArticlepeer-review

Abstract

We present a theory of even functionals of degree k. Even functional are homogeneous polynomials which are invariant with respect to permutations and reflections. These are evaluated on real symmetric matrices. Important examples of even functionals include functions for enumerating embeddings of graphs with k edges into a weighted graph with arbitrary (positive or negative) weights, and computing kth moments (expected values of kth powers) of a binary form. This theory provides a uniform approach for evaluating even functionals and links their evaluation with expressions that have matrices as operands. In particular, we show that any even functional of degree less than 7 can be computed in time sufficient to multiply two n × n matrices.

Original languageEnglish
Pages (from-to)41-56
Number of pages16
JournalTheoretical Computer Science
Volume154
Issue number1
DOIs
StatePublished - Jan 22 1996

Bibliographical note

Copyright:
Copyright 2021 Elsevier B.V., All rights reserved.

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science (all)

Fingerprint

Dive into the research topics of 'A theory of even functionals and their algorithmic applications'. Together they form a unique fingerprint.

Cite this