@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",
}