All reports by Author Max Hopkins:

__
TR24-082
| 17th April 2024
__

Yotam Dikstein, Max Hopkins#### Chernoff Bounds and Reverse Hypercontractivity on HDX

Revisions: 1

__
TR22-077
| 13th May 2022
__

Max Hopkins, Ting-Chun Lin#### Explicit Lower Bounds Against $\Omega(n)$-Rounds of Sum-of-Squares

__
TR21-169
| 24th November 2021
__

Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett#### Hypercontractivity on High Dimensional Expanders: a Local-to-Global Approach for Higher Moments

__
TR20-170
| 9th November 2020
__

Max Hopkins, Tali Kaufman, Shachar Lovett#### High Dimensional Expanders: Random Walks, Pseudorandomness, and Unique Games

Revisions: 1

Yotam Dikstein, Max Hopkins

We prove optimal concentration of measure for lifted functions on high dimensional expanders (HDX). Let $X$ be a $k$-dimensional HDX. We show for any $i \leq k$ and function $f: X(i) \to [0,1]$:

\[

\Pr_{s \in X(k)}\left[\left|\underset{{t \subseteq s}}{\mathbb{E}}[f(t)] - \mu \right| \geq \varepsilon \right] \leq \exp\left(-\varepsilon^2 \frac{k}{i}\right).

\]

Using ...
more >>>

Max Hopkins, Ting-Chun Lin

We construct an explicit family of 3-XOR instances hard for $\Omega(n)$-levels of the Sum-of-Squares (SoS) semi-definite programming hierarchy. Not only is this the first explicit construction to beat brute force search (beyond low-order improvements (Tulsiani 2021, Pratt 2021)), combined with standard gap amplification techniques it also matches the (optimal) hardness ... more >>>

Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett

Hypercontractivity is one of the most powerful tools in Boolean function analysis. Originally studied over the discrete hypercube, recent years have seen increasing interest in extensions to settings like the $p$-biased cube, slice, or Grassmannian, where variants of hypercontractivity have found a number of breakthrough applications including the resolution of ... more >>>

Max Hopkins, Tali Kaufman, Shachar Lovett

Higher order random walks (HD-walks) on high dimensional expanders have played a crucial role in a number of recent breakthroughs in theoretical computer science, perhaps most famously in the recent resolution of the Mihail-Vazirani conjecture (Anari et al. STOC 2019), which focuses on HD-walks on one-sided local-spectral expanders. In this ... more >>>