For those that couldn't make it, we've uploaded our full STOC workshop on High Dimensional Expanders to Youtube!. Hopefully a useful resource for learning the basics of HDX and how they're applied in TCS. Talk 1: An introduction to HDX.

HMS instead keep the labels of S and run A across *all subsets* of the sample. Since (w.h.p) there's a large subset of S consistent with h_{OPT}, running A on this subset will output a good hypothesis. This completely sidesteps dependency on the label space -- Nice!.

Our reduction works as follows. Given a realizable learner A:. 1. Draw a sample S, and throw out its labels.2. Run A over all possible labelings of S.3. Learn the best hypothesis output in Step 2 (e.g. via ERM). This doesn't work when there are infinite possible labelings!.

Hanneke, Meng, and Shaeiri give a simple resolution to a core open question in our work "Realizable Learning is All You Need". We did not know how to adapt our algorithm to the infinite multiclass setting. They give a simple variant resolving this!.

See also our website, which contains extra information/helpful material! .

Talk 6: The Impact of HDX in Quantum Coding.

Talk 5: Coboundary Expansion and Agreement Testing.

Talk 4: Bounded-Degree HDX Constructions (for the Working Computer Scientist).

Talk 3: Lossless Vertex Expanders (from HDX).

Talk 2: Approximate Sampling, HDX, and Geometry of Polynomials.

RT @singerng_: my article (with some spanish language quotations) drawing parallels between some of Jorge Luis Borges' fiction and computat….

So in the end, I guess the take-away is there really isn't much algorithmic difference between approximate sampling a (dense enough) distribution mu efficiently, and "perfectly" sampling it efficiently in expectation. Obvious in hindsight but hadn't occurred to me at least :).

Of course one might say this is cheating:. I'm just running the chain and doing a "correction" by computing the real value of mu(s) with exponentially small probability. So in reality I'm pretty much always just running the chain and doing nothing else.

Set up correctly, this clearly has the right marginal probabilities. The point is just that while the second probability is very hard to compute, it is also extremely unlikely to occur (since the first coin accepts w.h.p), so the procedure is efficient in expectation :).

The trick is very simple. Run the Markov chain P for k steps from arbitrary t up to high accuracy (say to some state s). Now flip 2 coins: a Bernoulli w/ prob ~(1-eps), and 2nd scaling with mu(s)/P^k(t,s). Accept if first coin is 1, or if 0 and second coin is 1. Else restart.

Came across a cool result by Göbel and Pappik ( this morning. They show any (nice enough) distribution mu with an efficient MCMC approximate sampling scheme can be converted into an efficient *perfect* sampling scheme.

Thanks Tom :) -- this paper was inspired by an elegant proof of hypercontractivity due to Yu Zhao and @BooleanAnalysis appearing in Yu's PhD thesis. My hope is the techniques will eventually extend to weak HDX and beyond simplicial complexes -- still much to be done!.

That's a wrap! Couldn't have asked for a better group than @ucsd_cse theory to grow as a researcher. Next stop: Princeton-IAS.

This was a super fun project, in great part due to getting to work with two absolutely fantastic junior students, Sihan Liu and Chris Ye. They drove the project, did the lion's share of writing, and deserve most the credit! Excited to see what they come up with next :).