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

Consider symmetric deterministic tensors $T_1, \ldots, T_n \in (\mathbb{R}^d)^{\otimes r}$ and let $g_1, \ldots, g_n$ be i.i.d. standard gaussian random variables. We are interested in determining ...