A locally correctable code (LCC) is an error correcting code that allows correction of any arbitrary coordinate of a corrupted codeword by querying only a few coordinates.
We show that any zero-error $2$-query locally correctable code $\mathcal{C}: \{0,1\}^k \to \Sigma^n$ that can correct a constant fraction of corrupted symbols must ... more >>>

For a universal constant $\alpha > 0$, we prove size lower bounds of $2^{\alpha N}$ for computing an explicit monotone function in NP in the following models of computation: monotone formulas, monotone switching networks, monotone span programs, and monotone comparator circuits, where $N$ is the number of variables of the ... more >>>

In "An Almost Cubic Lower Bound for $\sum\prod\sum$ circuits in VP", [BLS16] present an infinite family of polynomials, $\{P_n\}_{n \in \mathbb{Z}^+}$, with $P_n$
on $N = \Theta(n polylog(n))$
variables with degree $N$ being in VP such that every
$\sum\prod\sum$ circuit computing $P_n$ is of size $\Omega\big(\frac{N^3}{2^{\sqrt{\log N}}}\big)$.
We ... more >>>