Proving lower bounds on the size of noncommutative arithmetic circuits is an important problem in arithmetic circuit complexity. For explicit $n$ variate polynomials of degree $\Theta(n)$, the best known general bound is $\Omega(n \log n)$. Recent work of Chatterjee and Hrubeš has provided stronger ($\Omega(n^2)$) bounds for the restricted class ... more >>>

Error correcting codes encode messages by codewords in such a way that even if some of the codeword is corrupted, the message can be decoded. Typical decoding algorithms for error correcting codes either use linear space or quadratic time. A natural question is whether codes can be decoded in near-linear ... more >>>

Hyperdeterminants are high dimensional analogues of determinants, associated with tensors of formats generalizing square matrices. First conceived for $2\times 2\times 2$ tensors by Cayley, they were developed in generality by Gelfand, Kapranov and Zelevinsky. Yet, hyperdeterminants in three or more dimensions are long conjectured to be VNP-Hard to compute, akin ... more >>>