Groups and algebraic complexity

Andrew C. Yao

doi:10.1007/3-540-57155-8_233

Groups and algebraic complexity

Andrew C. Yao

Faculty of Electronic and Information Engineering

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

Abstract

In recent years, concepts from group theory have played an important role in the derivation of lower bounds for computational complexity. In this talk we present two new results in algebraic complexity obtained with group-theoretical arguments. We show that any algebraic computation tree for the membership question of a compact set S in Rⁿ must have height Ω(log(β_i(S)))- cn for all i, where β_i are the Betti numbers. We also show that, to compute the sum of n independent radicals using logarithms, exponentiations and root-takings, at least n operations are required. (The second result was obtained jointly with Dima Grigoriev and Mike Singer.) This talk will be self-contained.

Original language	English
Title of host publication	Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings
Editors	Frank Dehne, Jorg-Rudiger Sack, Nicola Santoro, Sue Whitesides
Publisher	Springer Verlag
ISBN (Print)	9783540571551
DOIs	https://doi.org/10.1007/3-540-57155-8_233
State	Published - 1993
Event	3rd Workshop on Algorithms and Data Structures, WADS 1993 - Montreal, Canada Duration: 11 Aug 1993 → 13 Aug 1993

Publication series

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

Conference

Conference	3rd Workshop on Algorithms and Data Structures, WADS 1993
Country/Territory	Canada
City	Montreal
Period	11/08/93 → 13/08/93

Access to Document

10.1007/3-540-57155-8_233

Cite this

Yao, A. C. (1993). Groups and algebraic complexity. In F. Dehne, J.-R. Sack, N. Santoro, & S. Whitesides (Eds.), Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 709 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-57155-8_233

@inproceedings{706b6573c5c44773b4089a71b91feef5,

title = "Groups and algebraic complexity",

abstract = "In recent years, concepts from group theory have played an important role in the derivation of lower bounds for computational complexity. In this talk we present two new results in algebraic complexity obtained with group-theoretical arguments. We show that any algebraic computation tree for the membership question of a compact set S in Rn must have height Ω(log(βi(S)))- cn for all i, where βi are the Betti numbers. We also show that, to compute the sum of n independent radicals using logarithms, exponentiations and root-takings, at least n operations are required. (The second result was obtained jointly with Dima Grigoriev and Mike Singer.) This talk will be self-contained.",

author = "Yao, \{Andrew C.\}",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1993.; 3rd Workshop on Algorithms and Data Structures, WADS 1993 ; Conference date: 11-08-1993 Through 13-08-1993",

year = "1993",

doi = "10.1007/3-540-57155-8\_233",

language = "英语",

isbn = "9783540571551",

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

publisher = "Springer Verlag",

editor = "Frank Dehne and Jorg-Rudiger Sack and Nicola Santoro and Sue Whitesides",

booktitle = "Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings",

}

Yao, AC 1993, Groups and algebraic complexity. in F Dehne, J-R Sack, N Santoro & S Whitesides (eds), Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 709 LNCS, Springer Verlag, 3rd Workshop on Algorithms and Data Structures, WADS 1993, Montreal, Canada, 11/08/93. https://doi.org/10.1007/3-540-57155-8_233

Groups and algebraic complexity. / Yao, Andrew C.
Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings. ed. / Frank Dehne; Jorg-Rudiger Sack; Nicola Santoro; Sue Whitesides. Springer Verlag, 1993. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 709 LNCS).

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

TY - GEN

T1 - Groups and algebraic complexity

AU - Yao, Andrew C.

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

PY - 1993

Y1 - 1993

N2 - In recent years, concepts from group theory have played an important role in the derivation of lower bounds for computational complexity. In this talk we present two new results in algebraic complexity obtained with group-theoretical arguments. We show that any algebraic computation tree for the membership question of a compact set S in Rn must have height Ω(log(βi(S)))- cn for all i, where βi are the Betti numbers. We also show that, to compute the sum of n independent radicals using logarithms, exponentiations and root-takings, at least n operations are required. (The second result was obtained jointly with Dima Grigoriev and Mike Singer.) This talk will be self-contained.

AB - In recent years, concepts from group theory have played an important role in the derivation of lower bounds for computational complexity. In this talk we present two new results in algebraic complexity obtained with group-theoretical arguments. We show that any algebraic computation tree for the membership question of a compact set S in Rn must have height Ω(log(βi(S)))- cn for all i, where βi are the Betti numbers. We also show that, to compute the sum of n independent radicals using logarithms, exponentiations and root-takings, at least n operations are required. (The second result was obtained jointly with Dima Grigoriev and Mike Singer.) This talk will be self-contained.

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

U2 - 10.1007/3-540-57155-8_233

DO - 10.1007/3-540-57155-8_233

M3 - 会议稿件

AN - SCOPUS:85029495749

SN - 9783540571551

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

BT - Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings

A2 - Dehne, Frank

A2 - Sack, Jorg-Rudiger

A2 - Santoro, Nicola

A2 - Whitesides, Sue

PB - Springer Verlag

T2 - 3rd Workshop on Algorithms and Data Structures, WADS 1993

Y2 - 11 August 1993 through 13 August 1993

ER -

Groups and algebraic complexity

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this