Workshop on Additive Combinatorics and Algebraic Connections

Polynomial Maps With Noisy Input-Distributions

Abstract: 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 Davi Castro-Silva

Date & Time

October 25, 2022 | 10:00am – 11:00am

Location

Simonyi 101 and Remote Access

Speakers

Jop Briet

Speaker Affiliation

Centrum Wiskunde & Informatica

Categories