A theory of even functionals and their algorithmic applications

Jerzy W. Jaromczyk; Grzegorz Światek

doi:10.1007/3-540-56939-1_67

A theory of even functionals and their algorithmic applications

Jerzy W. Jaromczyk, Grzegorz Światek

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

We present a theory of even functionals of degree k. Even functionals 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 with matrices as operands. In particular, we show that any even functional of degree less than 7 can be computed in time O(n^ω), the time required to multiply two n × n matrices.

Original language	English
Title of host publication	Automata, Languages and Programming - 20th International Colloquium, ICALP 1993, Proceedings
Editors	Andrzej Lingas, Rolf Karlsson, Svante Carlsson
Pages	126-136
Number of pages	11
DOIs	https://doi.org/10.1007/3-540-56939-1_67
State	Published - 1993
Event	20th International Colloquium on Automata, Languages and Programming, ICALP 1993 - Lund, Sweden Duration: Jul 5 1993 → Jul 9 1993

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	700 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	20th International Colloquium on Automata, Languages and Programming, ICALP 1993
Country/Territory	Sweden
City	Lund
Period	7/5/93 → 7/9/93

Bibliographical note

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1993.

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-56939-1_67

Cite this

Jaromczyk, J. W., & Światek, G. (1993). A theory of even functionals and their algorithmic applications. In A. Lingas, R. Karlsson, & S. Carlsson (Eds.), Automata, Languages and Programming - 20th International Colloquium, ICALP 1993, Proceedings (pp. 126-136). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 700 LNCS). https://doi.org/10.1007/3-540-56939-1_67

Jaromczyk, Jerzy W. ; Światek, Grzegorz. / A theory of even functionals and their algorithmic applications. Automata, Languages and Programming - 20th International Colloquium, ICALP 1993, Proceedings. editor / Andrzej Lingas ; Rolf Karlsson ; Svante Carlsson. 1993. pp. 126-136 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{83a8299ed1a54ce6b6fa92d9fee13f29,

title = "A theory of even functionals and their algorithmic applications",

abstract = "We present a theory of even functionals of degree k. Even functionals 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 with matrices as operands. In particular, we show that any even functional of degree less than 7 can be computed in time O(nω), the time required to multiply two n × n matrices.",

author = "Jaromczyk, {Jerzy W.} and Grzegorz {\'S}wiatek",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1993.; 20th International Colloquium on Automata, Languages and Programming, ICALP 1993 ; Conference date: 05-07-1993 Through 09-07-1993",

year = "1993",

doi = "10.1007/3-540-56939-1_67",

language = "English",

isbn = "9783540569398",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "126--136",

editor = "Andrzej Lingas and Rolf Karlsson and Svante Carlsson",

booktitle = "Automata, Languages and Programming - 20th International Colloquium, ICALP 1993, Proceedings",

}

Jaromczyk, JW & Światek, G 1993, A theory of even functionals and their algorithmic applications. in A Lingas, R Karlsson & S Carlsson (eds), Automata, Languages and Programming - 20th International Colloquium, ICALP 1993, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 700 LNCS, pp. 126-136, 20th International Colloquium on Automata, Languages and Programming, ICALP 1993, Lund, Sweden, 7/5/93. https://doi.org/10.1007/3-540-56939-1_67

A theory of even functionals and their algorithmic applications. / Jaromczyk, Jerzy W.; Światek, Grzegorz.
Automata, Languages and Programming - 20th International Colloquium, ICALP 1993, Proceedings. ed. / Andrzej Lingas; Rolf Karlsson; Svante Carlsson. 1993. p. 126-136 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 700 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A theory of even functionals and their algorithmic applications

AU - Jaromczyk, Jerzy W.

AU - Światek, Grzegorz

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1993.

PY - 1993

Y1 - 1993

N2 - We present a theory of even functionals of degree k. Even functionals 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 with matrices as operands. In particular, we show that any even functional of degree less than 7 can be computed in time O(nω), the time required to multiply two n × n matrices.

AB - We present a theory of even functionals of degree k. Even functionals 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 with matrices as operands. In particular, we show that any even functional of degree less than 7 can be computed in time O(nω), the time required to multiply two n × n matrices.

UR - http://www.scopus.com/inward/record.url?scp=85028856391&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85028856391&partnerID=8YFLogxK

U2 - 10.1007/3-540-56939-1_67

DO - 10.1007/3-540-56939-1_67

M3 - Conference contribution

AN - SCOPUS:85028856391

SN - 9783540569398

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 126

EP - 136

BT - Automata, Languages and Programming - 20th International Colloquium, ICALP 1993, Proceedings

A2 - Lingas, Andrzej

A2 - Karlsson, Rolf

A2 - Carlsson, Svante

T2 - 20th International Colloquium on Automata, Languages and Programming, ICALP 1993

Y2 - 5 July 1993 through 9 July 1993

ER -

Jaromczyk JW, Światek G. A theory of even functionals and their algorithmic applications. In Lingas A, Karlsson R, Carlsson S, editors, Automata, Languages and Programming - 20th International Colloquium, ICALP 1993, Proceedings. 1993. p. 126-136. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-56939-1_67

A theory of even functionals and their algorithmic applications

Abstract

Publication series

Conference

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this