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

这个项目继续PI在证明符号计算和多项式计算结果方面的富有成效的工作。它的目标是在三个方面取得成果：1。在高性能服务器（可能在计算云中）上执行的大规模符号计算输出的低成本认证。重点研究高维线性代数和非线性优化问题。快速可检查的证明还可以暴露时间和空间消耗服务器计算中的错误/错误。2. 医学图像处理需要对采样点的值进行鲁棒插值；该项目将使用考虑噪声和异常值（即灾难性误差）的算法，将函数重构为几个指数或正交多项式的稀疏和，同时最小化样本点的数量。3. 在代数计算复杂性的基本问题中，它对多项式乘法和最大公约数有了新的认识。PI继续培养本科生和硕士研究生，并指导博士生和博士后学者，使他们在设计算法和计算机程序方面发展先进的技能。鼓励学生和博士后通过在国际会议上展示海报和演讲来采用先进的研究沟通技巧，特别是当他们的背景来自该学科中代表性不足的群体时。实现低成本认证目标的方法是为稀疏矩阵的Frobenius形式和多项式方程在实数上的可解性开发证书，这些实数与产生输出的算法无关。该方法基于交互式证明协议和加密硬度假设，但该项目旨在减少协议中密码学的使用，以便验证者可以任意增加正确性的概率，甚至在计算之后。PI采用代数纠错解码对稀疏插值和密集有理向量恢复中的求值误差进行定位，后者提前终止。目前的重点是Chebyshev基的稀疏性，其中缺少列表解码器，以及使用Prony算法的泛化与Sakata对Berlekamp/Massey算法的泛化相结合的多元稀疏插值。最后，本课题研究了不使用常数的多项式乘法、不使用除法的Sylvester结式的计算以及将多项式表示为矩阵的特征多项式的代数复杂性。

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.