City: Saint Petersburg Novosibirsk Kazan Language: Русский English

From univariate polynomials to probabilistically checkable and error-tolerant proofs
Saint Petersburg / autumn 2018, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

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].

Date and time Class|Name Venue|short Materials
17 November
Лекция 1, Lecture ПОМИ РАН slides,  video
17 November
Лекция 2, Lecture ПОМИ РАН slides,  video
18 November
Лекция 3, Lecture ПОМИ РАН slides,  video
18 November
Лекция 4, Lecture ПОМИ РАН slides,  video
18 November
Лекция 5, Lecture ПОМИ РАН slides,  video