DocumentCode
2537267
Title
On Lower Bounds for Algebraic Decision Trees over the Complex Numbers
Author
Scheiblechner, Peter
Author_Institution
Dept. of Math., Purdue Univ., West Lafayette, IN, USA
fYear
2010
fDate
23-26 Sept. 2010
Firstpage
362
Lastpage
365
Abstract
We prove a new lower bound for the decision complexity of a complex algebraic set in terms of the sum of its (compactly supported) Betti numbers, which is for the first time better than logarithmic. We apply this result to subspace arrangements including some well studied problems such as the knapsack and element distinctness problems.
Keywords
computational complexity; decision trees; set theory; Betti numbers; algebraic decision trees; algebraic set; complex numbers; decision complexity; element distinctness problem; knapsack problem; Complexity theory; Computer science; Decision trees; Polynomials; USA Councils; algebraic decision trees; lower bounds;
fLanguage
English
Publisher
ieee
Conference_Titel
Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), 2010 12th International Symposium on
Conference_Location
Timisoara
Print_ISBN
978-1-4244-9816-1
Type
conf
DOI
10.1109/SYNASC.2010.73
Filename
5715310
Link To Document