Zero Testing and Sign Determination of Algebraic Numbers

在计算几何和数值分析中，在执行许多代数运算和求根之后，经常需要确定结果是零、正还是负。零点检验问题和符号确定问题在稳健几何计算中起着至关重要的作用。它们也与计算复杂性中的基本问题密切相关，例如多项式恒等式检验。虽然零测试问题通常可以通过随机算法来解决，但我们对符号确定问题的理解非常有限。该项目将研究零测试问题的去随机化技术，它们在多项式恒等式测试中的应用，以及符号确定问题的复杂性问题。计算数论和代数复杂性理论经常涉及到传统计算机科学课程中没有涉及的深层次和抽象的数学概念。然而，理解这些数学概念对信息安全工作人员来说至关重要。PI教授密码学多年，他将继续致力于向计算机科学专业的学生介绍数论主题的问题。许多关于高次代数数的算法问题都可以归结为用直线规划表示的整数问题。直线程序是通过对小整数进行加法、减法和乘法来构建大整数的过程。直线规划问题直观地触及了复杂理论的核心问题。它们可以作为一个理想的工具，吸引有数学天赋的学生学习理论计算机科学。PI将编写适用于高中生和本科生的直线课程入门材料。

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.