[DMO] Davi Castro-Silva: Noisy decoding and equidistribution of polynomial maps

17 februari 2023 14:00 t/m 15:00 - Locatie: Van Katwijkzaal, HB.08.150 | Zet in mijn agenda

A problem from theoretical computer science posed by Buhrman asks to show that a certain class of circuits (NC0[+]) is bad at decoding error-correcting codes under random noise. (This would be in contrast with an analogous class of quantum circuits.) These circuits can be modeled by constant-degree polynomial maps, which turns out to make the problem amenable to a structure-versus-randomness analysis based on a new notion of rank for polynomial maps.

In this talk I will aim to discuss a solution to Buhrman's problem along these lines as well as connections with other notions of rank for polynomials and tensors.

Based on joint work with Jop Briët.