From univariate polynomials to probabilistically checkable and error-tolerant proofs
Санкт-Петербург, осень 2018
Polynomials in one variable are among the most elementary and most useful mathematical objects, with broad-ranging applications from signal processing to error-correcting codes and advanced applications such as probabilistically checkable proofs. One of the main reasons why polynomials are useful in a myriad of applications is that highly efficient algorithms are known for computing with polynomials. These lectures introduce you to this near-linear-time toolbox and its select applications, with some algorithmic ideas dating back millennia, and some introduced only in the last few years. In particular, we aim at giving an exposition of recent algorithm designs that (a) tolerate silent hardware errors and (b) prepare a correctness proof that can be checked probabilistically with substantially less resources than it takes to solve the problem with the asymptotically fastest known algorithms. Here our starting point is a framework of Williams [CCC'16] for noninteractive Merlin--Arthur proofs of batch evaluation, which Björklund and Kaski [PODC'16] extend with the observation that Merlin's magic is not needed: mere Knights can prepare the proof, in parallel, and with intrinsic error-correction. This design framework captures with multiplicative polylogarithmic overhead in the total running time the fastest known algorithms for a number of hard problems ranging from computing the chromatic polynomial of a graph to counting k-cliques. Time permitting, we will also discuss our recent proof-of-concept implementation of the framework on GPUs [ALENEX'18].