Cf. my Laci Lovász anecdote: youtube.com/watch?v=t-lkFanf…

I gave a talk at Carnegie Mellon about the recent proof (by OpenAI) of the existence of a non-sofic group: youtu.be/uOQvzLjJK6c

To be fair, many people (e.g. Sivakanth Gopi) gave a simple n=5 counterexample to the similar 'Majority Is Least Stable' problem 10+ years ago...

Here's screencaps of excerpts of the other one...

Note that the answer is correct, but it has never given me a non-nonsensical proof. The proof always looks good until the key moment... A correct proof is the second paragraph of Theorem 4.1 here: cs.cmu.edu/~odonnell/papers/…

In case you're in Cambridge, MA on Tue. Dec. 10, I'll give a talk at 4pm (MIT 32-G449) about coboundary expansion in high-dimensional expanders. It's kind of about group theory, though. toc.csail.mit.edu/node/1671 Besides coauthor @singerng_, here's the cast of characters:

I don't know how to sell this any better than to say this is an extremely enjoyable video about Math + Halloween: youtube.com/watch?v=JlXUiqTi… So good!

In case you're in the Boston area, I'll talk about "Quartic quantum speedups for planted inference" tomorrow (Sep. 13) at Harvard at 4pm. This is at the Freedman CSMA Seminar. cmsa.fas.harvard.edu/event/f…

Probably the largest set of different home countries I've gotten the chance to lecture to. :) Thanks to Jan Hązła and the rest of @AIMS_Next for inviting me to participate!

(1/3) Quantum course tidbit #6: youtube.com/playlist?list=PL… Why is |EPR> = |00> + |11> special? Because when you draw it as a square, it's the 2x2 identity matrix.

(4/6) Now suppose Bob does "Add & Dif on C". (Nerds call this "Hadamard C" and get 1/sqrt(2)'s involved, yuck.) C is the front-back direction, so on each of the four front-back edges, we place the sum of the amplitudes on the |0> (front) side and the diff of the amplitudes on the |1> (back) side, yielding:

(3/6) Now say Bob does "If C then toggle B". (Nerds call this "CNOT C B".) Well, C is true (1) on the back face, and B is the horizontal direction, so we swap amplitudes on the back face's horizontal edges, getting to:

(2/6) If Charlie hands Bob a new qubit C initialized to x|0> + y|1>, the resulting 3-qubit state has x amount of |EPR> on the front face and y amount on the back face:

(1/6) Quantum course tidbit #5: youtube.com/playlist?list=PL… I really enjoy depicting 2- and 3-qubit states as labelings of the vertices of the square/cube by amplitudes. E.g., here is |EPR> = |00> + |11> (remember, we like unnormalized states):

Quantum course tidbit #4 youtube.com/watch?v=Wv83nzEh…: I often rename Hadamard to "Add & Dif". Applying it to qubit in state (x,y) takes you to (x+y,x-y). (Remember, we're cool with unnormalized states.) I feel this has somewhat more intuition / is more memorable. I *also* often rename it to "Avg & Dev". This takes (x,y) to the pair (avg{x,y}, "deviation of x,y from average"). (Remember, we're cool with unnormalized states.) To illustrate, if the amplitudes on |0> and |1> are 13 and 3, the new amplitudes are 8 and 5, reflecting that 13,3 = 8±5. "Add & Dif" and "Avg & Dev" are exact inverses. That's nice because almost every quantum algorithm does Hadamard an even number of times; moreover, it's almost always natural to replace half of the Hadamards with "Add & Dif" and half with "Avg & Dev". Then you don't even end up unnormalized at the end. Add & Difs are nice for preparing the uniform superposition (namely amplitude 1 on every basic state), starting from |00...0>. Avg & Devs are nice for the Hadamard transform; it becomes very clear that the final amplitude on |00...0>, e.g., is the *Average* of all the original amplitudes.