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

这个项目继续了PI在验证符号计算和多项式计算的结果方面的富有成效的工作。它的目标是在三个方面取得成果：1.对在高功率服务器上执行的大规模符号计算的输出进行低成本认证，可能是在计算云中。重点是高维线性代数和非线性优化中的问题。快速可检查的证据还可以暴露耗时和耗费空间的服务器计算中的错误/错误。2.医学图像处理需要从点采样值进行稳健内插；该项目将使用考虑噪声和离群值(即灾难性误差)的算法，将函数重建为几个指数或正交多项式的稀疏和，同时最小化样本点的数量。3.在代数计算复杂性的基本问题中，以全新的视角看待多项式乘法和最大公约数。PI继续培训本科生和硕士学生，并指导博士生和博士后学者，使他们在设计算法和计算机程序方面发展高级技能。将鼓励学生和博士后通过在国际会议上展示海报和演讲来采用先进的研究交流技能，特别是当他们的背景来自学科中代表不足的群体时。实现低成本认证目标的方法是为稀疏矩阵的Frobenius形式和与产生输出的算法无关的实数上的多项式方程的可解性开发证书。该方法基于交互证明协议和密码硬度假设，但该项目的目标是减少密码学在其协议中的使用，以便验证者即使在计算之后也可以任意增加正确的概率。PI使用代数纠错译码来定位稀疏内插和稠密有理向量恢复中的计算错误，后者具有提前终止的特点。目前的重点是基于切比雪夫的稀疏性，其中列表解码器缺失，以及使用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.