Zero Testing and Sign Determination of Algebraic Numbers

代数数的零检验和符号确定

• 批准号: 0830524
• 负责人: Qi Cheng
• 金额: $ 19.85万
• 依托单位: University of Oklahoma Norman Campus
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-09-01 至 2013-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0830524&HistoricalAwards=false
• 关键词: Zero; Testing; Sign; Determination; Algebraic

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.

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