Zero Testing and Sign Determination of Algebraic Numbers

点击翻译按钮获取中文摘要

In computational geometry and numerical analysis, after performing many algebraic operations and root-takings, one often needs to determine whether the result is zero, positive or negative. The zero testing problem and sign determination problem play an essential role in the robust geometric computation. They are also closely related to fundamental questions in computational complexity such as polynomial identity testing. While the zero testing problem can usually be tackled by randomized algorithms, our understanding of the sign determination problem is very limited. The project will study derandomization techniques for zero testing problems, their applications in polynomial identity testing and complexity issues of sign determination problems.Computational number theory and algebraic complexity theory often involve deep and abstract mathematical concepts, which are not covered in traditional computer science courses. However understanding these mathematical concepts is vital to information security workforce. The PI has taught cryptography for many years and he will continue working on issues of introducing number theory topics to computer science students. Many algorithmic problems on high degree algebraic numbers can be reduced to questions on integers represented by straight-line programs. Straight-line programs are procedures to build large integers by additions, subtractions and multiplications from small integers. The problems about straight line programs touch the core issues of complex theory in an intuitive manner. They can serve as an ideal vehicle to attract mathematically talented students to theoretical computer science. The PI will work on introductory materials on straight line programs that are suitable for high school students and undergraduate students.