Data e hora: sexta, 20 de outubro de 2023, às 11h.
Local: sala 2077 (ICEx)
Palestrante: Jeroen van de Graaf (DCC, UFMG)
Título: Why the algebra of polynomials over finite fields is causing a gold rush in the blockchain world
Polynomials over finite fields play a tremendously important role in communication and computation.
The simple property that N+1 points define one unique polynomial of degree N can be applied in several important settings. One classical example is the class of Reed-Solomon codes, which are used in every-day objects such as CDs, DVDs and QR codes for error correction purposes.
A very recent development is the use of polynomials in verifiable computation. In this scenario a weak user wants to outsource a computationally intensive program to some cluster, who computes the result. However, since the user has no reason to trust the cluster, they agree that the cluster will also provide a proof that the result was computed correctly. Moreover, this proof is succinct, meaning that it is short and that the user needs little computational resources to verify it. What happens is that a program execution is translated into a statement about polynomials of gigantic degree (1 million and more) which is easy to verify by the user.
Verifiable computation has many applications, including in blockchains such as Ethereum. This has led to a frenzy in competing projects each trying to develop and deploy this technology, attracting millions of dollars in venture capital investments. So this provides a clear example of the (increasing) importance of theoretical mathematics in computer science.
* A palestra será dada em português.