Improved construction for universality of determinant and permanent

Hong Liu; Kenneth W. Regan

doi:10.1016/j.ipl.2006.05.017

Improved construction for universality of determinant and permanent

Hong Liu
, Kenneth W. Regan

Department of Computer Science and Engineering

SUNY Buffalo

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

Valiant [L. Valiant, Completeness classes in algebra, in: Proc. 11th Annual ACM Symposium on the Theory of Computing, Atlanta, GA, 1979, pp. 249-261] proved that every polynomial of formula size e is a projection of the (e + 2) × (e + 2) determinant polynomial. We improve "e + 2" to "e + 1", also for a definition of formula size that does not count multiplications by constants as gates. Our proof imitates the "2 e + 2" proof of von zur Gathen [J. von zur Gathen, Feasible arithmetic computations: Valiant's hypothesis, Journal of Symbolic Computation 4 (1987) 137-172], but uses different invariants and a tighter set of base cases.

Original language	English
Pages (from-to)	233-237
Number of pages	5
Journal	Information Processing Letters
Volume	100
Issue number	6
DOIs	https://doi.org/10.1016/j.ipl.2006.05.017
State	Published - Dec 31 2006

Keywords

Algebraic formula size
Computational complexity
Determinant
Permanent

Access to Document

10.1016/j.ipl.2006.05.017

Cite this

@article{a02d50ae9193436688e3e7a9c41c06e8,

title = "Improved construction for universality of determinant and permanent",

abstract = "Valiant [L. Valiant, Completeness classes in algebra, in: Proc. 11th Annual ACM Symposium on the Theory of Computing, Atlanta, GA, 1979, pp. 249-261] proved that every polynomial of formula size e is a projection of the (e + 2) × (e + 2) determinant polynomial. We improve {"}e + 2{"} to {"}e + 1{"}, also for a definition of formula size that does not count multiplications by constants as gates. Our proof imitates the {"}2 e + 2{"} proof of von zur Gathen [J. von zur Gathen, Feasible arithmetic computations: Valiant's hypothesis, Journal of Symbolic Computation 4 (1987) 137-172], but uses different invariants and a tighter set of base cases.",

keywords = "Algebraic formula size, Computational complexity, Determinant, Permanent",

author = "Hong Liu and Regan, \{Kenneth W.\}",

year = "2006",

month = dec,

day = "31",

doi = "10.1016/j.ipl.2006.05.017",

language = "English",

volume = "100",

pages = "233--237",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "6",

}

TY - JOUR

T1 - Improved construction for universality of determinant and permanent

AU - Liu, Hong

AU - Regan, Kenneth W.

PY - 2006/12/31

Y1 - 2006/12/31

N2 - Valiant [L. Valiant, Completeness classes in algebra, in: Proc. 11th Annual ACM Symposium on the Theory of Computing, Atlanta, GA, 1979, pp. 249-261] proved that every polynomial of formula size e is a projection of the (e + 2) × (e + 2) determinant polynomial. We improve "e + 2" to "e + 1", also for a definition of formula size that does not count multiplications by constants as gates. Our proof imitates the "2 e + 2" proof of von zur Gathen [J. von zur Gathen, Feasible arithmetic computations: Valiant's hypothesis, Journal of Symbolic Computation 4 (1987) 137-172], but uses different invariants and a tighter set of base cases.

AB - Valiant [L. Valiant, Completeness classes in algebra, in: Proc. 11th Annual ACM Symposium on the Theory of Computing, Atlanta, GA, 1979, pp. 249-261] proved that every polynomial of formula size e is a projection of the (e + 2) × (e + 2) determinant polynomial. We improve "e + 2" to "e + 1", also for a definition of formula size that does not count multiplications by constants as gates. Our proof imitates the "2 e + 2" proof of von zur Gathen [J. von zur Gathen, Feasible arithmetic computations: Valiant's hypothesis, Journal of Symbolic Computation 4 (1987) 137-172], but uses different invariants and a tighter set of base cases.

KW - Algebraic formula size

KW - Computational complexity

KW - Determinant

KW - Permanent

UR - https://www.scopus.com/pages/publications/33750020892

U2 - 10.1016/j.ipl.2006.05.017

DO - 10.1016/j.ipl.2006.05.017

M3 - Article

AN - SCOPUS:33750020892

SN - 0020-0190

VL - 100

SP - 233

EP - 237

JO - Information Processing Letters

JF - Information Processing Letters

IS - 6

ER -

Improved construction for universality of determinant and permanent

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this