Here's a neat result I heard about at virtual Dagstuhl last week, a new lower bound on the number of hyperplanes that cuts all the edges of a hypercube.

A n-dimensional hypercube has 2^{n} vertices corresponding to the binary strings of length n. Edges are between two vertices that differ in exactly one bit, for a total of (n/2) 2^{n} edges. Hypercubes played a large role in Hao Huang's recent proof of the sensitivity conjecture.

A hyperplane is just a linear inequality in x_{1},…,x_{n} the bits of the string corresponding to a vertex. An edge is cut if the inequality is true for one vertex and false for the other.

With n hyperplanes you can cut all the edges in two very different ways.

- The hyperplanes x
_{i}> 0 for each i. These are n orthogonal hyperplanes. - The hyperplanes x
_{1}+…+x_{n}> i for each i from 0 to n-1. These are n parallel hyperplanes.

^{0.5}) fraction of the edges (sharp by the hyperplane x

_{1}+…+x

_{n}> n/2). Thus you need at least O(n

^{0.5}) hyperplanes which for 50 years was the best known bound.

^{0.57}). The paper gives a O(n

^{0.51}) bound but Yehudayoff said in a talk last week the bound has been improved.

^{1.57}wires in a depth-two threshold circuit for parity. But the main fun is the question itself, that we finally made progress and there is still a long way to go.