Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > MAX HOPKINS:
All reports by Author Max Hopkins:

TR24-082 | 17th April 2024
Yotam Dikstein, Max Hopkins

Chernoff Bounds and Reverse Hypercontractivity on HDX

Revisions: 1

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 >>>


TR22-077 | 13th May 2022
Max Hopkins, Ting-Chun Lin

Explicit Lower Bounds Against $\Omega(n)$-Rounds of Sum-of-Squares

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 >>>


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

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 >>>


TR20-170 | 9th November 2020
Max Hopkins, Tali Kaufman, Shachar Lovett

High Dimensional Expanders: Random Walks, Pseudorandomness, and Unique Games

Revisions: 1

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 >>>




ISSN 1433-8092 | Imprint