AF: Small: Symbolic Computation with Certificates, Sparsity and Error Correction

该项目继续PI在验证符号计算和多项式计算结果方面的富有成效的工作。 它的目标是在三个领域取得成果：1.在高功率服务器上执行的大规模符号计算的输出的低成本认证，可能在计算云中。 重点是在高维线性代数和非线性优化问题。 快速可检查的证明还可以暴露耗时和占用空间的服务器计算中的错误/故障。 2. 医学图像处理需要从点采样的值进行稳健的插值;该项目将使用考虑噪声和异常值（即灾难性错误）的算法，同时最大限度地减少采样点的数量，将函数重建为几个指数或正交多项式的稀疏和。 3.在代数计算复杂性的基本问题中，它重新审视多项式乘法和最大公约数。PI继续培训本科生和硕士生，并指导博士生。学生和博士后学者，使他们发展先进的技能，设计算法和计算机程序做数学。 学生和博士后将被鼓励通过在国际会议上展示海报和演讲，特别是当他们的背景是来自学科中代表性不足的群体时。成本认证是为稀疏矩阵的Frobenius形式和独立于矩阵的真实的数上的多项式方程的可解性开发证书。产生输出的算法。 该方法基于交互式证明协议和密码学硬度假设，但该项目旨在减少其协议中密码学的使用，以便验证者可以任意增加正确性概率，即使在计算之后。 PI使用代数纠错解码来定位稀疏插值和密集有理向量恢复中的评估错误，后者具有提前终止。 目前的重点是稀疏在切比雪夫的基础上，列表解码器丢失，并在多变量稀疏插值使用Prony的算法结合Sakata的Berlekamp/Massey算法的推广。 最后，该项目研究了不使用常数的多项式相乘的代数复杂性，计算不带除法的西尔维斯特结果，并将多项式表示为矩阵的特征多项式。

This project continues the PI's productive work in certifying the results of symbolic computations and in polynomial computations. It aims for results in three areas: 1. Low-cost certification of the output of large-scale symbolic computations performed on high power servers, possibly in the computing cloud. The focus is on problems in high-dimensional linear algebra and non-linear optimization. Quickly checkable proofs can also expose bugs/faults in time- and space-consuming server computations. 2. Medical image processing needs robust interpolation from values sampled at points; The project will reconstruct functions as sparse sums of a few exponentials or orthogonal polynomials, using algorithms that account for noise and outliers (that is, catastrophic errors) while minimizing the number of sample points. 3. In fundamental problems in algebraic computational complexity, it takes a fresh look at polynomial multiplication and greatest common divisors.The PI continues to train undergraduate and Master students, and supervise Ph.D. students and a postdoctoral scholar, so that they develop advanced skills in designing algorithms and computer programs for doing mathematics. The students and postdoc will be encouraged to adopt advanced research communication skills by presenting posters and talks at international meetings, especially when their background is from under-represented groups in the discipline.The method to achieve the goal of low-cost certification is to develop certificates for the Frobenius form of sparse matrices and for the solvability of polynomial equations over the real numbers that are independent of the algorithms that produce the output. The approach is based on interactive proof protocols and crytographic hardness assumptions, but the project aims to reduce the use of cryptography in its protocols, so that the verifier can increase probability of correctness arbitrarily, even after the computation. The PI has used algebraic error correcting decoding to locate evaluation errors in sparse interpolation and dense rational vector recovery, the latter with early termination. The current focus is on sparseness in a Chebyshev basis, where list-decoders are missing, and on multivariate sparse interpolation using a generalization of Prony's Algorithm combined with Sakata's generalization of the Berlekamp/Massey Algorithm. Finally, the project studies the algebraic complexity of multiplying polynomials without the use of constants, computing the Sylvester resultant without divisions, and representing polynomials as the characteristic polynomial of matrices.