5 papers
Toward a KKL Theorem for any HDX
Max Hopkins
The KKL Theorem, a seminal result in boolean function analysis, characterizes the structure of low-influence (non-expanding) functions on the hypercube. While recent years have see…
A Simple Sub-Polynomial Degree Coboundary Expander
Max Hopkins, Arka Ray
High dimensional expanders simultaneously satisfying spectral and combinatorial (coboundary) expansion have recently played a major role in breakthroughs in PCP and coding theory,…
Hypercontractivity on HDX II: Symmetrization and q-Norms
Max Hopkins
Bourgain's symmetrization theorem is a powerful technique reducing boolean analysis on product spaces to the cube. It states that for any product , function $f: Î…
The Role of Randomness in Stability
Max Hopkins, Shay Moran
Stability is a central property in learning and statistics promising the output of an algorithm does not change substantially when applied to similar datasets and . It…
Chernoff Bounds and Reverse Hypercontractivity on HDX
Yotam Dikstein, Max Hopkins
We prove optimal concentration of measure for lifted functions on high dimensional expanders (HDX). Let be a -dimensional HDX. We show for any and $f:X(i)\to [0,1]…