With the incredible progress on Mathematical Open Problems this past Summer, we decided to broaden the scope of our blog and also include digestions and simplifications of solutions, keeping the ex...

The problem of finding the largest clique in an Erdős–Rényi random graph $G(n, 1/2)$ has a special place in the study of average-case algorithmic complexity. It is one of the well-known examples of...

Several alternative notions of convexity arise in different areas of mathematics. One particularly interesting and intricate example is rank-one convexity, or more generally directional convexity. ...

Let $G_d$ be a uniformly random $d$-regular graph on $n$, an even number of nodes. Throughout this post we will think of $d$ as a fixed constant and are interested in understanding the setting in w...

Given a computation problem on a random input, one natural question is whether there is some polynomial time algorithm solving it with high probability. To argue that such a problem is hard, we usu...

The isoperimetric problem dates back to the ancient Greeks who conjectured that in $\mathbb{R}^2$, the shape with fixed boundary length that maximizes is given by a circle. While this has been pro...

Given a prime number $p$ such that $p \equiv 1 \pmod{4}$ the Paley graph on $p$ nodes $G_p$ is the graph where nodes $i$ and $j$ are connected if $i-j$ is a quadratic residue modulo $p$. This graph...

Mutually Unbiased Bases Finite frame theory is the source of many beautiful questions. A remarkable example concerns the existence of Mutually Unbiased Bases, and object of interest in Quantum Phy...

Throughout this post $\mathbb{K}$ will stand for either $\mathbb{R}$ or $\mathbb{C}$. Given $A\in\mathbb{K}^{N\times M}$, the Phase Retrieval Problem aims to recover a vector $x\in\mathbb{K}^M$ fr...

For a graph $G = (V, E)$, the clique number $\omega(G)$ and the chromatic number $\chi(G)$ are fundamental properties studied in combinatorics and graph theory. It is known that computing these qua...