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
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;
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
DOI :
10.1109/SYNASC.2010.73
