Talk information
Date: Sunday, June 22, 2025
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Elad Aigner-Horev (Ariel University)
Title: Resilience of Rademacher chaos of low degree
Abstract:
The resilience of a Rademacher chaos is the maximum number of adversarial sign-flips that the chaos can sustain without having its largest atom probability significantly altered. Inspired by probabilistic lower-bound guarantees for the resilience of linear Rademacher chaos (aka. resilience of the Littlewood-Offord problem), obtained by Bandeira, Ferber, and Kwan (Advances in Mathematics, Vol. 319, 2017), we provide probabilistic lower-bound guarantees for the resilience of Rademacher chaos of arbitrary yet sufficiently low degree and thus pursuing a high-degree variant of the resilience of the Littlewood-Offord problem.
Our main results distinguish between Rademacher chaos of order two and those of higher order. In that, our first main result pertains to the resilience of decoupled bilinear Rademacher forms; in this venue, different asymptotic behaviour is observed for sparse and dense matrices in terms of their resilience. For our second main result, we bootstrap our first main result in order to provide probabilistic resilience guarantees for quadratic Rademacher chaos which are no longer decoupled. Our third, and last, main result, generalises the first and handles the resilience of decoupled Rademacher chaos of arbitrary yet sufficiently low order.
Our results for decoupled Rademacher chaos of order two and that of higher order whilst are established through the same conceptual framework, differ qualitatively and quantitatively. This difference is incurred due to the different tools utilised in order to implement the same conceptual argument. The order two result is established using Dudley’s maximal inequality for sub-Gaussian processes, the Hanson-Wright concentration inequality, as well as the Kolmogorov-Rogozin anti-concentration inequality. The result pertaining to higher orders is established using surrogate results replacing appeals to Dudley’s inequality as well as the Hanson-Wright inequality with tools suited for random tensors. In particular, appeals to the Hanson-Wright inequality are replaced with appeals to a concentration result for random tensors put forth by Adamczak and Wolff (Probability Theory and related fields, Vol. 162, 2015).
All of our results are instance-dependent and allow for the efficient computation of probabilistic lower-bound guarantees for the resilience of the aforementioned types of Rademacher chaos provided the order of the chaos is constant.