Vikraman Arvind, Pushkar Joglekar

In this paper we study the problem of efficiently factorizing polynomials in the free noncommutative ring F of polynomials in noncommuting variables x_1,x_2,…,x_n over the field F. We obtain the following result:

Given a noncommutative arithmetic formula of size s computing a noncommutative polynomial f in F as input, where ... more >>>

Vikraman Arvind, Pushkar Joglekar

In continuation to our recent work on noncommutative

polynomial factorization, we consider the factorization problem for

matrices of polynomials and show the following results.

\begin{itemize}

\item Given as input a full rank $d\times d$ matrix $M$ whose entries

$M_{ij}$ are polynomials in the free noncommutative ring

more >>>

Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, Bhargav Thankey

We prove super-polynomial lower bounds for low-depth arithmetic circuits using the shifted partials measure [Gupta-Kamath-Kayal-Saptharishi, CCC 2013], [Kayal, ECCC 2012] and the affine projections of partials measure [Garg-Kayal-Saha, FOCS 2020], [Kayal-Nair-Saha, STACS 2016]. The recent breakthrough work of Limaye, Srinivasan and Tavenas [FOCS 2021] proved these lower bounds by proving ... more >>>