Proving complexity lower bounds remains a challenging task: currently, we only know how to prove conditional uniform (algorithm) lower bounds and nonuniform (circuit) lower bounds in restricted circuit models. About a decade ago, Williams (STOC 2010) showed how to derive nonuniform lower bounds from uniform upper bounds: roughly, by designing ... more >>>

In this work, we explore a non-linear extension of the classical Sylvester-Gallai configuration. Let $\mathbb{K}$ be an algebraically closed field of characteristic zero, and let $\mathcal{F} = \{F_1, \ldots, F_m\} \subset \mathbb{K}[x_1, \ldots, x_N]$ denote a collection of irreducible homogeneous polynomials of degree at most $d$, where each $F_i$ is ... more >>>

We prove a sensitivity-to-communication lifting theorem for arbitrary gadgets. Given functions $f: \{0,1\}^n\to \{0,1\}$ and $g : \mathcal{X} \times \mathcal{Y}\to \{0,1\}$, denote $f\circ g(x,y) := f(g(x_1,y_1),\ldots,g(x_n,y_n))$. We show that for any $f$ with sensitivity $s$ and any $g$,
\[D(f\circ g) \geq s\cdot \bigg(\frac{\Omega(D(g))}{\log rk(g)} - \log rk(g)\bigg),\]
where ... more >>>